Algorithm
Development Kit 1.0

algs.model.tree
Class BalancedTree<K,V>

java.lang.Object
  extended by algs.model.tree.BalancedTree<K,V>
Type Parameters:
K - the base type of the keys stored by each node.
V - the base type of the values stored by the BinaryNode.
Direct Known Subclasses:
AugmentedBalancedTree

public class BalancedTree<K,V>
extends java.lang.Object

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).

Since:
1.0
Version:
1.0, 6/15/08
Author:
Josh Bloch and Doug Lea [Original authors of java.util.TreeMap], George Heineman [Extended that class for use here]

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

comparator

protected java.util.Comparator<? super K> comparator
Comparator used to maintain order in this BalancedTree.


root

protected BalancedBinaryNode<K,V> root
Root node.


size

protected int size
Number of entries in the tree.


allowDuplicates

protected boolean allowDuplicates
Allow duplicates?

Constructor Detail

BalancedTree

public BalancedTree()
Constructs an empty Balanced Tree.


BalancedTree

public BalancedTree(java.util.Comparator<? super K> c)
Constructs a new, empty map, sorted according to the given comparator.

Parameters:
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

size

public int size()
Returns the number of key-value mappings in this map.

Returns:
the number of key-value mappings in this map.

setAllowDuplicates

public boolean setAllowDuplicates(boolean b)
Determine if this tree should allow entries with duplicate keys. The operation succeeds only if the tree is empty.

Parameters:
b - true if the tree should allow duplicates; false otherwise
Returns:
true if the operation is a success; false otherwise.

allowDuplicates

public boolean allowDuplicates()
Return whether tree allows entries with duplicate keys.


pred

public BalancedBinaryNode<K,V> pred(BalancedBinaryNode<K,V> n)
Return the predecessor node to the given entry. On an empty tree, returns null.

Parameters:
n -

comparator

public java.util.Comparator<? super K> comparator()
Returns the comparator used to order this map, or null if this map uses its keys' natural order.

Returns:
the comparator associated with this sorted map, or null if it uses its keys' natural sort method.

search

public V search(K k)
Returns value associated with given key, or null if the map does not contain an entry for the key.

If the tree allows duplicates, then the first one in the tree which matches is returned.

Returns:
value associated with the given key, or null if the map does not contain an entry for the key.
Throws:
java.lang.NullPointerException - key is null and this map uses natural order, or its comparator does not tolerate null keys.

getEntry

public 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.

If the tree allows duplicates, then the first one in the tree which matches is returned.

Returns:
this map's entry for the given key, or null if the map does not contain an entry for the key.
Throws:
java.lang.NullPointerException - key is null and this map uses natural order, or its comparator does not tolerate * null keys.

getPrecedingEntry

public 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.


getSuccessorEntry

public 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.


insert

public V insert(K key,
                V value)
Associates the specified value with the specified key in this map. If the map previously contained a mapping for this key, the old value is replaced and returned.

Parameters:
key - key with which the specified value is to be associated.
value - value to be associated with the specified key.
Returns:
previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the map previously associated null with the specified key.
Throws:
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.

construct

protected BalancedBinaryNode<K,V> construct(K key,
                                            V value,
                                            BalancedBinaryNode<K,V> parent)
Construct a node in the tree. Subclass extensions of BalancedTree must override this method to insert the appropriate node of the appropriate subclass.

Parameters:
key -
value -
parent -

remove

public V remove(K key)
Removes the mapping for this key from this TreeMap if present.

If tree allows duplicates, then the first one that maps to the key is returned.

Parameters:
key - key for which mapping should be removed
Returns:
previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the map previously associated null with the specified key.
Throws:
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.

clear

public void clear()
Empty out the tree.


compare

protected int compare(K k1,
                      K k2)
Compares two keys using the correct comparison method for this BalancedTree.

If no comparator set, attempt to use the Key's Comparable interface.


firstNode

public BalancedBinaryNode<K,V> firstNode()
Returns the first Entry in the BalancedTree (according to the BalancedTree key-sort function). Returns null if the BalancedTree is empty.


minimum

public V minimum()
Removes and returns minimum value in tree. Returs null if tree is empty.


root

public BalancedBinaryNode<K,V> root()
Returns the root of the tree (or null if empty).


lastNode

public BalancedBinaryNode<K,V> lastNode()
Returns the last Entry in the tree.


successor

public BalancedBinaryNode<K,V> successor(BalancedBinaryNode<K,V> t)
Returns the successor of the specified Entry, or null if no such.


rotateLeft

protected void rotateLeft(BalancedBinaryNode<K,V> p)
From CLR


rotateRight

protected void rotateRight(BalancedBinaryNode<K,V> p)
From CLR


fixAfterInsertion

protected void fixAfterInsertion(BalancedBinaryNode<K,V> x)
From CLR


deleteEntry

protected void deleteEntry(BalancedBinaryNode<K,V> p)
Delete node p, and then rebalance the tree.


accept

public void accept(IBalancedVisitor<K,V> visitor)
Accept a visitor for a inorder traversal.


toString

public java.lang.String toString()
Return parenthetical string of tree structure using inOrder traversal.

Overrides:
toString in class java.lang.Object

iterator

public java.util.Iterator<V> iterator()

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.