avltree-avltree2.html
来自「经典的数据结构源代码（java 实现）」· HTML 代码 · 共 56 行
HTML
56 行
<html><head><title>Code Fragment</title></head><body text=#000000><center></center><br><br><dl><dd><pre> <font color = #ff0080>/** Returns a child of p with height no smaller than that of the other child */</font> <font color=#8000a0><font color=#8000a0>protected</font> </font>Position<Entry<K,V>> <font color=#0000ff>tallerChild</font>(Position<Entry<K,V>> p) { <font color=#ff8000>if</font><font color=#0000ff> </font>(<font color=#0000ff>height</font>(<font color=#0000ff>left</font>(p)) > <font color=#0000ff>height</font>(<font color=#0000ff>right</font>(p))) <font color=#8000a0><font color=#ff8000>return</font> </font><font color=#0000ff>left</font>(p); <font color=#8000a0><font color=#ff8000>else</font> </font><font color=#ff8000>if</font><font color=#0000ff> </font>(<font color=#0000ff>height</font>(<font color=#0000ff>left</font>(p)) < <font color=#0000ff>height</font>(<font color=#0000ff>right</font>(p))) <font color=#8000a0><font color=#ff8000>return</font> </font><font color=#0000ff>right</font>(p); <font color=#ff0080>// equal height children - break tie using parent's type</font> <font color=#ff8000>if</font><font color=#0000ff> </font>(<font color=#0000ff>isRoot</font>(p)) <font color=#8000a0><font color=#ff8000>return</font> </font><font color=#0000ff>left</font>(p); <font color=#ff8000>if</font><font color=#0000ff> </font>(p == <font color=#0000ff>left</font>(<font color=#0000ff>parent</font>(p))) <font color=#8000a0><font color=#ff8000>return</font> </font><font color=#0000ff>left</font>(p); <font color=#8000a0><font color=#ff8000>else</font> </font><font color=#ff8000>return</font> <font color=#0000ff>right</font>(p); } <font color=#ff0080>/** * Rebalance method called by insert and remove. Traverses the path from * zPos to the root. For each node encountered, we recompute its height * and perform a trinode restructuring if it's unbalanced. */</font> <font color=#8000a0><font color=#8000a0>protected</font> </font><font color=#8000a0>void</font> <font color=#0000ff>rebalance</font>(Position<Entry<K,V>> zPos) { <font color=#ff8000>if</font><font color=#0000ff></font>(<font color=#0000ff>isInternal</font>(zPos)) <font color=#0000ff>setHeight</font>(zPos); <font color=#ff8000>while</font><font color=#0000ff> </font>(!<font color=#0000ff>isRoot</font>(zPos)) { <font color=#ff0080>// traverse up the tree towards the root</font> zPos = <font color=#0000ff>parent</font>(zPos); <font color=#0000ff>setHeight</font>(zPos); <font color=#ff8000>if</font><font color=#0000ff> </font>(!<font color=#0000ff>isBalanced</font>(zPos)) { <font color=#ff0080>// perform a trinode restructuring at zPos's tallest grandchild</font> Position<Entry<K,V>> xPos = <font color=#0000ff>tallerChild</font>(<font color=#0000ff>tallerChild</font>(zPos)); zPos = <font color=#0000ff>restructure</font>(xPos); <font color=#ff0080>// tri-node restructure (from parent class)</font> <font color=#0000ff>setHeight</font>(<font color=#0000ff>left</font>(zPos)); <font color=#ff0080>// recompute heights</font> <font color=#0000ff>setHeight</font>(<font color=#0000ff>right</font>(zPos)); <font color=#0000ff>setHeight</font>(zPos); } } } <font color=#ff0080>// overridden methods of the dictionary ADT</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>v) <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, v); <font color=#ff0080>// calls our createNode method</font> <font color=#0000ff>rebalance</font>(actionPos); <font color=#ff0080>// rebalance up from the insertion position</font> <font color=#8000a0><font color=#ff8000>return</font> </font>toReturn; } <font color=#8000a0><font color=#8000a0>public</font> </font>Entry<K,V> <font color=#0000ff>remove</font>(Entry<K,V> ent) <font color=#8000a0><font color=#ff8000>throws</font> </font>InvalidEntryException { Entry<K,V> toReturn = <font color=#ff8000>super</font>.<font color=#0000ff>remove</font>(ent); <font color=#ff8000>if</font><font color=#0000ff> </font>(toReturn != null) <font color=#ff0080>// we actually removed something</font> <font color=#0000ff>rebalance</font>(actionPos); <font color=#ff0080>// rebalance up the tree</font> <font color=#8000a0><font color=#ff8000>return</font> </font>toReturn; }} <font color=#ff0080>// end of AVLTree class</font></dl></body></html>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?