protected static class TreeMap.BalanceableBinaryTree<K,V> extends LinkedBinaryTree<Entry<K,V>>
| Modifier and Type | Class and Description |
|---|---|
protected static class |
TreeMap.BalanceableBinaryTree.BSTNode<E> |
LinkedBinaryTree.Node<E>root| Modifier | Constructor and Description |
|---|---|
protected |
TreeMap.BalanceableBinaryTree() |
| Modifier and Type | Method and Description |
|---|---|
protected LinkedBinaryTree.Node<Entry<K,V>> |
createNode(Entry<K,V> e,
LinkedBinaryTree.Node<Entry<K,V>> parent,
LinkedBinaryTree.Node<Entry<K,V>> left,
LinkedBinaryTree.Node<Entry<K,V>> right)
Factory function to create a new node storing element e.
|
int |
getAux(Position<Entry<K,V>> p) |
Position<Entry<K,V>> |
restructure(Position<Entry<K,V>> x)
Returns the Position that becomes the root of the restructured subtree.
|
void |
rotate(Position<Entry<K,V>> p)
Rotates Position p above its parent.
|
void |
setAux(Position<Entry<K,V>> p,
int value) |
addLeft, addRight, addRoot, attach, left, parent, remove, right, root, set, size, validatechildren, inorder, numChildren, positions, siblingbreadthfirst, depth, height, isEmpty, isExternal, isInternal, isRoot, iterator, postorder, preorderclone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, waitisEmpty, isExternal, isInternal, isRoot, iteratorprotected LinkedBinaryTree.Node<Entry<K,V>> createNode(Entry<K,V> e, LinkedBinaryTree.Node<Entry<K,V>> parent, LinkedBinaryTree.Node<Entry<K,V>> left, LinkedBinaryTree.Node<Entry<K,V>> right)
LinkedBinaryTreecreateNode in class LinkedBinaryTree<Entry<K,V>>public void rotate(Position<Entry<K,V>> p)
b a
/ \ / \
a t2 t0 b
/ \ / \
t0 t1 t1 t2
Caller should ensure that p is not the root.public Position<Entry<K,V>> restructure(Position<Entry<K,V>> x)
z=a z=c z=a z=c
/ \ / \ / \ / \
t0 y=b y=b t3 t0 y=c y=a t3
/ \ / \ / \ / \
t1 x=c x=a t2 x=b t3 t0 x=b
/ \ / \ / \ / \
t2 t3 t0 t1 t1 t2 t1 t2
The subtree will be restructured so that the node with key b becomes its root.
b
/ \
a c
/ \ / \
t0 t1 t2 t3
Caller should ensure that x has a grandparent.