📄 binarysearchtree-binarysearchtree3.html
字号:
<html><head><title>Code Fragment</title></head><body text=#000000><center></center><br><br><dl><dd><pre> <font color=#ff0080>// methods of the dictionary ADT</font> <font color=#8000a0><font color=#8000a0>public</font> </font><font color=#8000a0>int</font> <font color=#0000ff>size</font>() { <font color=#8000a0><font color=#ff8000>return</font> </font>numEntries; } <font color=#8000a0><font color=#8000a0>public</font> </font><font color=#8000a0>boolean</font> <font color=#0000ff>isEmpty</font>() { <font color=#8000a0><font color=#ff8000>return</font> </font><font color=#0000ff>size</font>() == 0; } <font color=#8000a0><font color=#8000a0>public</font> </font>Entry<K,V> <font color=#0000ff>find</font>(K key) <font color=#8000a0><font color=#ff8000>throws</font> </font>InvalidKeyException { <font color=#0000ff>checkKey</font>(key); <font color=#ff0080>// may throw an InvalidKeyException</font> Position<Entry<K,V>> curPos = <font color=#0000ff>treeSearch</font>(key, <font color=#0000ff>root</font>()); actionPos = curPos; <font color=#ff0080>// node where the search ended</font> <font color=#ff8000>if</font><font color=#0000ff> </font>(<font color=#0000ff>isInternal</font>(curPos)) <font color=#8000a0><font color=#ff8000>return</font> </font><font color=#0000ff>entry</font>(curPos); <font color=#8000a0><font color=#ff8000>return</font> </font>null; } <font color=#8000a0><font color=#8000a0>public</font> </font>Iterable<Entry<K,V>> <font color=#0000ff>findAll</font>(K key) <font color=#8000a0><font color=#ff8000>throws</font> </font>InvalidKeyException { <font color=#0000ff>checkKey</font>(key); <font color=#ff0080>// may throw an InvalidKeyException</font> PositionList<Entry<K,V>> L = <font color=#8000a0><font color=#ff8000>new</font> </font>NodePositionList<Entry<K,V>><font color=#0000ff></font>(); <font color=#0000ff>addAll</font>(L, <font color=#0000ff>root</font>(), key); <font color=#8000a0><font color=#ff8000>return</font> </font>L; } <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 { <font color=#0000ff>checkKey</font>(k); <font color=#ff0080>// may throw an InvalidKeyException</font> Position<Entry<K,V>> insPos = <font color=#0000ff>treeSearch</font>(k, <font color=#0000ff>root</font>()); <font color=#ff8000>while</font><font color=#0000ff> </font>(!<font color=#0000ff>isExternal</font>(insPos)) <font color=#ff0080>// iterative search for insertion position</font> insPos = <font color=#0000ff>treeSearch</font>(k, <font color=#0000ff>left</font>(insPos)); actionPos = insPos; <font color=#ff0080>// node where the new entry is being inserted</font> <font color=#8000a0><font color=#ff8000>return</font> </font><font color=#0000ff>insertAtExternal</font>(insPos, <font color=#8000a0><font color=#ff8000>new</font> </font>BSTEntry<K,V><font color=#0000ff></font>(k, x, insPos)); } <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 { <font color=#0000ff>checkEntry</font>(ent); <font color=#ff0080>// may throw an InvalidEntryException</font> Position<Entry<K,V>> remPos =<font color=#0000ff> </font>(<font color=#0000ff></font>(BSTEntry<K,V>) ent).<font color=#0000ff>position</font>(); Entry<K,V> toReturn = <font color=#0000ff>entry</font>(remPos); <font color=#ff0080>// entry to be returned</font> <font color=#ff8000>if</font><font color=#0000ff> </font>(<font color=#0000ff>isExternal</font>(<font color=#0000ff>left</font>(remPos))) remPos = <font color=#0000ff>left</font>(remPos); <font color=#ff0080>// left easy case</font> <font color=#8000a0><font color=#ff8000>else</font> </font><font color=#ff8000>if</font><font color=#0000ff> </font>(<font color=#0000ff>isExternal</font>(<font color=#0000ff>right</font>(remPos))) remPos = <font color=#0000ff>right</font>(remPos); <font color=#ff0080>// right easy case</font> <font color=#ff8000>else</font> { <font color=#ff0080>// entry is at a node with internal children</font> Position<Entry<K,V>> swapPos = remPos; <font color=#ff0080>// find node for moving entry</font> remPos = <font color=#0000ff>right</font>(swapPos); <font color=#ff8000>do</font> remPos = <font color=#0000ff>left</font>(remPos); <font color=#ff8000>while</font><font color=#0000ff> </font>(<font color=#0000ff>isInternal</font>(remPos)); <font color=#0000ff>replaceEntry</font>(swapPos,<font color=#0000ff> </font>(Entry<K,V>) <font color=#0000ff>parent</font>(remPos).<font color=#0000ff>element</font>()); } actionPos = <font color=#0000ff>sibling</font>(remPos); <font color=#ff0080>// sibling of the leaf to be removed</font> <font color=#0000ff>removeExternal</font>(remPos); <font color=#8000a0><font color=#ff8000>return</font> </font>toReturn; }} <font color=#ff0080>// entries() method is omitted here</font></dl></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -