📄 rbtree-insertitem.html
字号:
<html><head><title>Code Fragment</title></head><body text=#000000><center></center><br><br><dl><dd><pre> <font color = #ff0080>/** Creates a new tree node. */</font> <font color=#8000a0><font color=#8000a0>protected</font> </font>BTPosition<Entry<K,V>> <font color=#0000ff>createNode</font>(Entry<K,V> element, BTPosition<Entry<K,V>> parent, BTPosition<Entry<K,V>> left, BTPosition<Entry<K,V>> right) { <font color=#8000a0><font color=#ff8000>return</font> </font><font color=#ff8000>new</font> RBNode<K,V><font color=#0000ff></font>(element,parent,left,right); <font color=#ff0080>// a red-black node</font> } <font color=#8000a0><font color=#8000a0>public</font> </font>Entry<K,V> <font color=#0000ff>insert</font>(K k, <font color=#8000a0>V </font>x) <font color=#8000a0><font color=#ff8000>throws</font> </font>InvalidKeyException { Entry<K,V> toReturn = <font color=#ff8000>super</font>.<font color=#0000ff>insert</font>(k, x); Position<Entry<K,V>> posZ = actionPos; <font color=#ff0080>// start at the insertion position</font> <font color=#0000ff>setRed</font>(posZ); <font color=#ff8000>if</font><font color=#0000ff> </font>(<font color=#0000ff>isRoot</font>(posZ)) <font color=#0000ff>setBlack</font>(posZ); <font color=#ff8000>else</font> <font color=#0000ff>remedyDoubleRed</font>(posZ); <font color=#ff0080>// fix a double-red color violation </font> <font color=#8000a0><font color=#ff8000>return</font> </font>toReturn; } <font color=#8000a0><font color=#8000a0>protected</font> </font><font color=#8000a0>void</font> <font color=#0000ff>remedyDoubleRed</font>(Position<Entry<K,V>> posZ) { Position<Entry<K,V>> posV = <font color=#0000ff>parent</font>(posZ); <font color=#ff8000>if</font><font color=#0000ff> </font>(<font color=#0000ff>isRoot</font>(posV)) <font color=#ff8000>return</font>; <font color=#ff8000>if</font><font color=#0000ff> </font>(!<font color=#0000ff>isPosRed</font>(posV)) <font color=#ff8000>return</font>; <font color=#ff0080>// we have a double red: posZ and posV</font> <font color=#ff8000>if</font><font color=#0000ff> </font>(!<font color=#0000ff>isPosRed</font>(<font color=#0000ff>sibling</font>(posV))) { <font color=#ff0080>// Case 1: trinode restructuring</font> posV = <font color=#0000ff>restructure</font>(posZ); <font color=#0000ff>setBlack</font>(posV); <font color=#0000ff>setRed</font>(<font color=#0000ff>left</font>(posV)); <font color=#0000ff>setRed</font>(<font color=#0000ff>right</font>(posV)); } <font color=#ff8000>else</font> { <font color=#ff0080>// Case 2: recoloring</font> <font color=#0000ff>setBlack</font>(posV); <font color=#0000ff>setBlack</font>(<font color=#0000ff>sibling</font>(posV)); Position<Entry<K,V>> posU = <font color=#0000ff>parent</font>(posV); <font color=#ff8000>if</font><font color=#0000ff> </font>(<font color=#0000ff>isRoot</font>(posU)) <font color=#ff8000>return</font>; <font color=#0000ff>setRed</font>(posU); <font color=#0000ff>remedyDoubleRed</font>(posU); } }</dl></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -