Package generic.stl

Class RedBlackTree<K,​V>


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

      • EOL

        public static final java.lang.String EOL
    • Constructor Detail

      • RedBlackTree

        public RedBlackTree​(java.util.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 Detail

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.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>,​java.lang.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.
      • 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.