|
Algorithm Development Kit 1.0 |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectalgs.model.tree.BalancedTree<K,K>
algs.model.problems.segmentIntersection.AugmentedBalancedTree<K>
K
- The key to be used for the nodes in the tree. Note that both
the key and the value of the nodes will be of type K for simplicitypublic class AugmentedBalancedTree<K>
The Balanced Binary Tree for this algorithm required internal nodes to store (min, max) links to the leaf nodes, where actual segments are to be stored.
Field Summary |
---|
Fields inherited from class algs.model.tree.BalancedTree |
---|
allowDuplicates, comparator, root, size |
Constructor Summary | |
---|---|
AugmentedBalancedTree()
Constructs an empty Balanced Tree. |
|
AugmentedBalancedTree(java.util.Comparator<? super K> c)
Constructs a new, empty tree sorted according to the given comparator. |
Method Summary | |
---|---|
protected AugmentedNode<K> |
construct(K key,
K value,
AugmentedNode<K> parent)
Construct a node in the tree. |
protected void |
deleteEntry(BalancedBinaryNode<K,K> p)
Because we are using leaf nodes only to store the segments, we can be guaranteed that the node p is going to be a leaf node. |
protected void |
fixAfterInsertion(BalancedBinaryNode<K,K> p)
From CLR |
AugmentedNode<K> |
getEntry(K key)
Overrides locate by using interior nodes as guides. |
K |
insert(K key)
Must make sure that interior nodes contain no segments; rather, only the leaves do. |
K |
remove(K key)
Overrides deletion by finding the leaf node for this key. |
AugmentedNode<K> |
root()
Helps with type casting |
protected void |
rotateLeft(BalancedBinaryNode<K,K> p)
From CLR |
protected void |
rotateRight(BalancedBinaryNode<K,K> p)
From CLR |
Methods inherited from class algs.model.tree.BalancedTree |
---|
accept, allowDuplicates, clear, comparator, compare, construct, firstNode, getPrecedingEntry, getSuccessorEntry, insert, iterator, lastNode, minimum, pred, search, setAllowDuplicates, size, successor, toString |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Constructor Detail |
---|
public AugmentedBalancedTree()
public AugmentedBalancedTree(java.util.Comparator<? super K> c)
c
- the comparator that will be used to sort this map. A
null value indicates that the keys' natural
ordering should be used.Method Detail |
---|
public AugmentedNode<K> root()
root
in class BalancedTree<K,K>
protected AugmentedNode<K> construct(K key, K value, AugmentedNode<K> parent)
key
- value
- parent
- public AugmentedNode<K> getEntry(K key)
getEntry
in class BalancedTree<K,K>
public K remove(K key)
remove
in class BalancedTree<K,K>
key
- key for which mapping should be removed
public K insert(K key)
protected void deleteEntry(BalancedBinaryNode<K,K> p)
deleteEntry
in class BalancedTree<K,K>
protected void fixAfterInsertion(BalancedBinaryNode<K,K> p)
BalancedTree
fixAfterInsertion
in class BalancedTree<K,K>
protected void rotateLeft(BalancedBinaryNode<K,K> p)
BalancedTree
rotateLeft
in class BalancedTree<K,K>
protected void rotateRight(BalancedBinaryNode<K,K> p)
BalancedTree
rotateRight
in class BalancedTree<K,K>
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |