|
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,V>
K
- the base type of the keys stored by each node.V
- the base type of the values stored by the BinaryNode.public class BalancedTree<K,V>
Balanced Tree, based on stripped down implementation of
TreeMap
which is itself an implementation of the
algorithm as described in Cormen, Leiserson, and Rivest's
Introduction to Algorithms (Cormen et al, 2001). The source code
for the original may be found in http://download.java.net/openjdk/jdk6
The original copyright notice from Sun Microsystems has been included within this class file even though we have only extracted several methods from that class.
Red-Black tree based implementation of binary tree. Ensures that the entries will be stored using the natural key order for the class K or by the comparator provided at creation time, depending on which constructor is used.
If special balanced trees require additional processing, then extend the rotateLeft and rotateRight trees.
An interesting on-line Applet describing Red/Black trees in action can be found here [http://gauss.ececs.uc.edu/RedBlack/redblack.html]. Verified URL August 2007.
IMPORTANT: This tree implementation by default assumes all keys are unique. When calling insert (K,V) on a key that is already present, the old value is replaced with the new V value (and that old value is returned as the return value of insert). To change this default behavior, set the "allowDuplicates" property to be true; this property can only be changed while the tree is empty (to avoid nasty trouble if the assumption were to change).
Field Summary | |
---|---|
protected boolean |
allowDuplicates
Allow duplicates? |
protected java.util.Comparator<? super K> |
comparator
Comparator used to maintain order in this BalancedTree. |
protected BalancedBinaryNode<K,V> |
root
Root node. |
protected int |
size
Number of entries in the tree. |
Constructor Summary | |
---|---|
BalancedTree()
Constructs an empty Balanced Tree. |
|
BalancedTree(java.util.Comparator<? super K> c)
Constructs a new, empty map, sorted according to the given comparator. |
Method Summary | |
---|---|
void |
accept(IBalancedVisitor<K,V> visitor)
Accept a visitor for a inorder traversal. |
boolean |
allowDuplicates()
Return whether tree allows entries with duplicate keys. |
void |
clear()
Empty out the tree. |
java.util.Comparator<? super K> |
comparator()
Returns the comparator used to order this map, or null if this map uses its keys' natural order. |
protected int |
compare(K k1,
K k2)
Compares two keys using the correct comparison method for this BalancedTree. |
protected BalancedBinaryNode<K,V> |
construct(K key,
V value,
BalancedBinaryNode<K,V> parent)
Construct a node in the tree. |
protected void |
deleteEntry(BalancedBinaryNode<K,V> p)
Delete node p, and then rebalance the tree. |
BalancedBinaryNode<K,V> |
firstNode()
Returns the first Entry in the BalancedTree (according to the BalancedTree key-sort function). |
protected void |
fixAfterInsertion(BalancedBinaryNode<K,V> x)
From CLR |
BalancedBinaryNode<K,V> |
getEntry(K k)
Returns this map's entry for the given key, or null if the map does not contain an entry for the key. |
BalancedBinaryNode<K,V> |
getPrecedingEntry(K key)
Returns the entry for the greatest key less than the specified key; if no such entry exists (i.e., the least key in the Tree is greater than the specified key), returns null. |
BalancedBinaryNode<K,V> |
getSuccessorEntry(K key)
Returns the entry for the smallest key greater than the specified key; if no such entry exists (i.e., the least key in the Tree is greater than the specified key), returns null. |
V |
insert(K key,
V value)
Associates the specified value with the specified key in this map. |
java.util.Iterator<V> |
iterator()
|
BalancedBinaryNode<K,V> |
lastNode()
Returns the last Entry in the tree. |
V |
minimum()
Removes and returns minimum value in tree. |
BalancedBinaryNode<K,V> |
pred(BalancedBinaryNode<K,V> n)
Return the predecessor node to the given entry. |
V |
remove(K key)
Removes the mapping for this key from this TreeMap if present. |
BalancedBinaryNode<K,V> |
root()
Returns the root of the tree (or null if empty). |
protected void |
rotateLeft(BalancedBinaryNode<K,V> p)
From CLR |
protected void |
rotateRight(BalancedBinaryNode<K,V> p)
From CLR |
V |
search(K k)
Returns value associated with given key, or null if the map does not contain an entry for the key. |
boolean |
setAllowDuplicates(boolean b)
Determine if this tree should allow entries with duplicate keys. |
int |
size()
Returns the number of key-value mappings in this map. |
BalancedBinaryNode<K,V> |
successor(BalancedBinaryNode<K,V> t)
Returns the successor of the specified Entry, or null if no such. |
java.lang.String |
toString()
Return parenthetical string of tree structure using inOrder traversal. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Field Detail |
---|
protected java.util.Comparator<? super K> comparator
protected BalancedBinaryNode<K,V> root
protected int size
protected boolean allowDuplicates
Constructor Detail |
---|
public BalancedTree()
public BalancedTree(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 int size()
public boolean setAllowDuplicates(boolean b)
b
- true if the tree should allow duplicates; false otherwise
public boolean allowDuplicates()
public BalancedBinaryNode<K,V> pred(BalancedBinaryNode<K,V> n)
n
- public java.util.Comparator<? super K> comparator()
public V search(K k)
If the tree allows duplicates, then the first one in the tree which matches is returned.
java.lang.NullPointerException
- key is null and this map uses
natural order, or its comparator does not tolerate
null keys.public BalancedBinaryNode<K,V> getEntry(K k)
If the tree allows duplicates, then the first one in the tree which matches is returned.
java.lang.NullPointerException
- key is null and this map uses
natural order, or its comparator does not tolerate *
null keys.public BalancedBinaryNode<K,V> getPrecedingEntry(K key)
public BalancedBinaryNode<K,V> getSuccessorEntry(K key)
public V insert(K key, V value)
key
- key with which the specified value is to be associated.value
- value to be associated with the specified key.
java.lang.ClassCastException
- key cannot be compared with the keys
currently in the map.
java.lang.NullPointerException
- key is null and this map uses
natural order, or its comparator does not tolerate
null keys.protected BalancedBinaryNode<K,V> construct(K key, V value, BalancedBinaryNode<K,V> parent)
key
- value
- parent
- public V remove(K key)
If tree allows duplicates, then the first one that maps to the key is returned.
key
- key for which mapping should be removed
java.lang.ClassCastException
- key cannot be compared with the keys
currently in the map.
java.lang.NullPointerException
- key is null and this map uses
natural order, or its comparator does not tolerate
null keys.public void clear()
protected int compare(K k1, K k2)
If no comparator set, attempt to use the Key's Comparable interface.
public BalancedBinaryNode<K,V> firstNode()
public V minimum()
public BalancedBinaryNode<K,V> root()
public BalancedBinaryNode<K,V> lastNode()
public BalancedBinaryNode<K,V> successor(BalancedBinaryNode<K,V> t)
protected void rotateLeft(BalancedBinaryNode<K,V> p)
protected void rotateRight(BalancedBinaryNode<K,V> p)
protected void fixAfterInsertion(BalancedBinaryNode<K,V> x)
protected void deleteEntry(BalancedBinaryNode<K,V> p)
public void accept(IBalancedVisitor<K,V> visitor)
public java.lang.String toString()
toString
in class java.lang.Object
public java.util.Iterator<V> iterator()
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |