Package generic.stl

Class RedBlackTree<K,V>

java.lang.Object
generic.stl.RedBlackTree<K,V>
public class RedBlackTree<K,V> extends Object
A RedBlack Tree implementation with K type keys and place to store V type values.

  • Field Details

    • EOL

      public static final String EOL

  • Constructor Details

    • RedBlackTree

      public RedBlackTree(Comparator<K> comparator, boolean allowDuplicateKeys)
      Creates a new RedBlackTree
      Parameters:
      comparator - the comparator for this tree
      allowDuplicateKeys - true to allow duplicate keys

    • RedBlackTree

      public RedBlackTree(RedBlackTree<K,V> tree)
      Creates a copy of an existing RedBlackTree
      Parameters:
      tree - the existing tree to copy

  • Method Details

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • size

      public int size()
      Returns the number keys in this set.

    • containsKey

      public boolean containsKey(K key)
      Returns true if the key is in the set.
      Parameters:
      key - the key whose presence is to be tested.

    • getFirst

      public RedBlackNode<K,V> getFirst()
      Returns the first entry in this set.

    • getLast

      public RedBlackNode<K,V> getLast()
      Returns the last entry in this set.

    • lowerBound

      public RedBlackNode<K,V> lowerBound(K key)
      Finds the node with the lowest key that is >= to the given key. Returns null if all nodes in the tree have keys less than the given key.
      Parameters:
      key - the key to search for.
      Returns:
      the node with the lowest key that is >= to the given key or null if no such key exists.

    • upperBound

      public RedBlackNode<K,V> upperBound(K key)
      Finds the node with the lowest key that is > the given key. Returns null if all nodes in the tree have keys less than or equal to the given key.
      Parameters:
      key - the key to search for.
      Returns:
      the node with the lowest key that is > to the given key or null if no such key exists.

    • put

      public Pair<RedBlackNode<K,V>,Boolean> put(K key, V value)
      Adds the given key,value to the map. If the map does not allow duplicate keys and a key already exists, the old value will be replaced by the new value and the old value will be returned.
      Parameters:
      key - the key to add to the set.
      value - the key's value.
      Returns:
      the old value associated with the key, or null if the key was not previously in the map.

    • findFirstNode

      public RedBlackNode<K,V> findFirstNode(K key)

    • findLastNode

      public RedBlackNode<K,V> findLastNode(K key)

    • remove

      public V remove(K key)
      Removes the given key (first if duplicates are allowed) from the set.
      Parameters:
      key - the key to remove from the set.
      Returns:
      the value associated with the key removed or null if the key not found.

    • removeAll

      public void removeAll()
      Removes all entrys from the set.

    • isEmpty

      public boolean isEmpty()
      Test if the set is empty.
      Returns:
      true if the set is empty.

    • deleteEntry

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