Class RedBlackTree<T>

  • All Implemented Interfaces:
    java.lang.Iterable<T>
    Direct Known Subclasses:
    JsonCasSerializer.MapType2Subtypes

    public class RedBlackTree<T>
    extends java.lang.Object
    implements java.lang.Iterable<T>
    Map from int to T (Object) 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.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) RBTNode<T> root  
      (package private) int size  
    • Constructor Summary

      Constructors 
      Constructor Description
      RedBlackTree()
      Default constructor, does nothing.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()
      Remove all elements from the tree.
      boolean containsKey​(int key)
      Checks if the key is contained in the tree.
      boolean containsValue​(T o)
      Check if the value object is contained in the tree.
      T get​(int key)
      Get the object for a key.
      BinaryTree getBinaryTree()  
      T getFirst()  
      private RBTNode<T> getFirstNode()  
      boolean isEmpty()
      Check if the map is empty.
      java.util.Iterator<T> iterator()  
      int[] keySet()
      Return the set of keys as a sorted array.
      static void main​(java.lang.String[] args)  
      void printKeys()
      Debugging aid.
      boolean put​(int key, T el)
      Insert an object with a given key into the tree.
      private boolean put​(RBTNode<T> node)
      Insert a RBTNode into the tree.
      T remove​(int key)
      Delete the node with the given key from the tree, if it exists.
      int size()  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
      • Methods inherited from interface java.lang.Iterable

        forEach, spliterator
    • Constructor Detail

      • RedBlackTree

        public RedBlackTree()
        Default constructor, does nothing.
    • Method Detail

      • size

        public final int size()
        Returns:
        The number of key/value pairs in the tree.
      • clear

        public final void clear()
        Remove all elements from the tree.
      • containsKey

        public final boolean containsKey​(int key)
        Checks if the key is contained in the tree.
        Parameters:
        key - The key.
        Returns:
        true, if key is defined; false, else.
      • containsValue

        public final boolean containsValue​(T o)
        Check if the value object is contained in the tree. Inefficient, since it requires a traverse of the tree.
        Parameters:
        o - The value we want to check.
        Returns:
        true, if value is there; false, else.
      • put

        public final boolean put​(int key,
                                 T el)
        Insert an object with a given key into the tree.
        Parameters:
        key - The key under which the Object is to be inserted.
        el - The Object to be inserted.
        Returns:
        true, if the key was not in the tree; false, if an element with that key was already in the tree. The old element is overwritten with the new one.
      • remove

        public final T remove​(int key)
        Delete the node with the given key from the tree, if it exists.
        Parameters:
        key - The key to be deleted.
        Returns:
        -
      • get

        public final T get​(int key)
        Get the object for a key. If the key is not contained in the tree, returns null. Since null can also be a regular value, use containsKey() to check if a key is defined or not.
        Parameters:
        key - The key.
        Returns:
        The corresponding element, or null if key is not defined.
      • isEmpty

        public final boolean isEmpty()
        Check if the map is empty.
        Returns:
        true if map is empty; false, else.
      • keySet

        public final int[] keySet()
        Return the set of keys as a sorted array.
        Returns:
        A sorted array of the keys.
      • put

        private final boolean put​(RBTNode<T> node)
        Insert a RBTNode into the tree. Only used internally.
      • getFirst

        public final T getFirst()
        Returns:
        The object associated with the smallest key, or null if the tree is empty.
      • getFirstNode

        private final RBTNode<T> getFirstNode()
      • iterator

        public java.util.Iterator<T> iterator()
        Specified by:
        iterator in interface java.lang.Iterable<T>
        Returns:
        An iterator over the elements in the tree. The elements are returned in ascending order of the corresponding keys.
      • getBinaryTree

        public BinaryTree getBinaryTree()
        Returns:
        a copy of the red-black tree as a BinaryTree. The node values are key-value pairs (RBTKeyValuePair).
      • printKeys

        public void printKeys()
        Debugging aid.
      • main

        public static void main​(java.lang.String[] args)