avltree-avltree.html
来自「经典的数据结构源代码（java 实现）」· HTML 代码 · 共 54 行
HTML
54 行
<html><head><title>Code Fragment</title></head><body text=#000000><center></center><br><br><dl><dd><pre><font color = #ff0080>/** Implementation of an AVL tree. */</font><font color=#8000a0>public</font> <font color=#8000a0><font color=#ff8000>class</font> </font>AVLTree<K,V> <font color=#8000a0><font color=#ff8000>extends</font> </font>BinarySearchTree<K,V> <font color=#8000a0><font color=#ff8000>implements</font> </font>Dictionary<K,V> { <font color=#8000a0><font color=#8000a0>public</font> </font><font color=#0000ff>AVLTree</font>(Comparator<K> c) { <font color=#ff8000>super</font><font color=#0000ff></font>(c); } <font color=#8000a0><font color=#8000a0>public</font> </font><font color=#0000ff>AVLTree</font>() { <font color=#ff8000>super</font><font color=#0000ff></font>(); } <font color = #ff0080>/** Nested class for the nodes of an AVL tree. */</font> <font color=#8000a0><font color=#8000a0>protected</font> </font><font color=#8000a0>static</font> <font color=#8000a0><font color=#ff8000>class</font> </font>AVLNode<K,V> <font color=#8000a0><font color=#ff8000>extends</font> </font>BTNode<Entry<K,V>> { <font color=#8000a0><font color=#8000a0>protected</font> </font><font color=#8000a0>int</font> height; <font color=#ff0080>// we add a height field to a BTNode</font> <font color=#0000ff>AVLNode</font>() {<font color = #ff0080>/* default constructor */</font>} <font color = #ff0080>/** Preferred constructor */</font> <font color=#0000ff>AVLNode</font>(Entry<K,V> element, BTPosition<Entry<K,V>> parent, BTPosition<Entry<K,V>> left, BTPosition<Entry<K,V>> right) { <font color=#ff8000>super</font><font color=#0000ff></font>(element, parent, left, right); height = 0; <font color=#ff8000>if</font><font color=#0000ff> </font>(left != null) height = Math.<font color=#0000ff>max</font>(height, 1 +<font color=#0000ff> </font>(<font color=#0000ff></font>(AVLNode<K,V>) left).<font color=#0000ff>getHeight</font>()); <font color=#ff8000>if</font><font color=#0000ff> </font>(right != null) height = Math.<font color=#0000ff>max</font>(height, 1 +<font color=#0000ff> </font>(<font color=#0000ff></font>(AVLNode<K,V>) right).<font color=#0000ff>getHeight</font>()); } <font color=#ff0080>// we assume that the parent will revise its height if needed</font> <font color=#8000a0><font color=#8000a0>public</font> </font><font color=#8000a0>void</font> <font color=#0000ff>setHeight</font>(<font color=#8000a0>int</font> h) { height = h; } <font color=#8000a0><font color=#8000a0>public</font> </font><font color=#8000a0>int</font> <font color=#0000ff>getHeight</font>() { <font color=#8000a0><font color=#ff8000>return</font> </font>height; } } <font color = #ff0080>/** Creates a new binary search tree node (overrides super's version). */</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> AVLNode<K,V><font color=#0000ff></font>(element,parent,left,right); <font color=#ff0080>// now use AVL nodes</font> } <font color = #ff0080>/** Returns the height of a node (call back to an AVLNode). */</font> <font color=#8000a0><font color=#8000a0>protected</font> </font><font color=#8000a0>int</font> <font color=#0000ff>height</font>(Position<Entry<K,V>> p) { <font color=#ff8000>return</font><font color=#0000ff> </font>(<font color=#0000ff></font>(AVLNode<K,V>) p).<font color=#0000ff>getHeight</font>(); } <font color = #ff0080>/** Sets the height of an internal node (call back to an AVLNode). */</font> <font color=#8000a0><font color=#8000a0>protected</font> </font><font color=#8000a0>void</font> <font color=#0000ff>setHeight</font>(Position<Entry<K,V>> p) { <font color=#0000ff> </font>(<font color=#0000ff></font>(AVLNode<K,V>) p).<font color=#0000ff>setHeight</font>(1+Math.<font color=#0000ff>max</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 = #ff0080>/** Returns whether a node has balance factor between -1 and 1. */</font> <font color=#8000a0><font color=#8000a0>protected</font> </font><font color=#8000a0>boolean</font> <font color=#0000ff>isBalanced</font>(Position<Entry<K,V>> p) { <font color=#8000a0><font color=#8000a0>int</font> </font>bf = <font color=#0000ff>height</font>(<font color=#0000ff>left</font>(p)) - <font color=#0000ff>height</font>(<font color=#0000ff>right</font>(p)); <font color=#ff8000>return</font><font color=#0000ff> </font>(<font color=#0000ff></font>(-1 <= bf) &&<font color=#0000ff> </font>(bf <= 1)); }</dl></body></html>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?