TreeMap.BalanceableBinaryTree<K,V>AbstractMap.MapEntry<K,V>| Constructor and Description |
|---|
AVLTreeMap()
Constructs an empty map using the natural ordering of keys.
|
AVLTreeMap(Comparator<K> comp)
Constructs an empty map using the given comparator to order keys.
|
| Modifier and Type | Method and Description |
|---|---|
protected int |
height(Position<Entry<K,V>> p)
Returns the height of the given tree position.
|
protected boolean |
isBalanced(Position<Entry<K,V>> p)
Returns whether a position has balance factor between -1 and 1 inclusive.
|
protected void |
rebalance(Position<Entry<K,V>> p)
Utility used to rebalance after an insert or removal operation.
|
protected void |
rebalanceDelete(Position<Entry<K,V>> p)
Overrides the TreeMap rebalancing hook that is called after a deletion.
|
protected void |
rebalanceInsert(Position<Entry<K,V>> p)
Overrides the TreeMap rebalancing hook that is called after an insertion.
|
protected void |
recomputeHeight(Position<Entry<K,V>> p)
Recomputes the height of the given position based on its children's heights.
|
protected Position<Entry<K,V>> |
tallerChild(Position<Entry<K,V>> p)
Returns a child of p with height no smaller than that of the other child.
|
ceilingEntry, dump, entrySet, firstEntry, floorEntry, get, higherEntry, isExternal, isInternal, isRoot, lastEntry, left, lowerEntry, parent, put, rebalanceAccess, remove, remove, restructure, right, root, rotate, set, sibling, size, subMap, treeMax, treeMincheckKey, compare, compare, compare, compareisEmpty, keySet, valuespublic AVLTreeMap()
public AVLTreeMap(Comparator<K> comp)
comp - comparator defining the order of keys in the mapprotected void recomputeHeight(Position<Entry<K,V>> p)
protected boolean isBalanced(Position<Entry<K,V>> p)
protected Position<Entry<K,V>> tallerChild(Position<Entry<K,V>> p)
protected void rebalance(Position<Entry<K,V>> p)
protected void rebalanceInsert(Position<Entry<K,V>> p)
rebalanceInsert in class TreeMap<K,V>p - the position which was recently inserted