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.