|class||RBTIterator< T >|
|final void||clear ()|
|final boolean||containsKey (int key)|
|final boolean||containsValue (T o)|
|final T||get (int key)|
|final T||getFirst ()|
|final boolean||isEmpty ()|
|Iterator< T >||iterator ()|
|final int||keySet ()|
|final boolean||put (int key, T el)|
|final T||remove (int key)|
|final int||size ()|
|static void||main (String args)|
|RBTNode< T >||root = null|
|int||size = 0|
|final RBTNode< T >||getFirstNode ()|
|final boolean||put (RBTNode< T > node)|
An implementation of Red-Black Trees. This implementation follows quite closely the algorithms described in Cormen, Leiserson and Rivest (1990): "Introduction to Algorithms" (henceforth CLR). The main difference between our implementation and CLR is that our implementation does not allow duplicate keys in a tree. Since we will generally use our implementation to represent sets, this is a sensible restriction.
The difference between this implementation and TreeMap is that we assume that keys are ints. This should provide for a constant factor speed-up. We also assume that we may copy this implementation to specialize for particular data element types.
This class implements most methods required for a Map. However, since we use ints as keys, we can't implement the interface, as ints are not Objects, and so for example RedBlackTree.containsKey(int key) does not specialize Map.containsKey(Object key).
Note that this implementation is not thread-safe. A thread-safe version could easily be provided, but would come with additional overhead.