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 Summary

  Fields
  Modifier and Type
  Field
  Description
  `static final String`
  `EOL`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `RedBlackTree(RedBlackTree<K,V> tree)`
  Creates a copy of an existing RedBlackTree
  `RedBlackTree(Comparator<K> comparator, boolean allowDuplicateKeys)`
  Creates a new RedBlackTree

- ## Method Summary

  Modifier and Type
  Method
  Description
  `boolean`
  `containsKey(K key)`
  Returns true if the key is in the set.
  `void`
  `deleteEntry(RedBlackNode<K,V> p)`
  Delete node p, and then rebalance the tree.
  `RedBlackNode<K,V>`
  `findFirstNode(K key)`
  `RedBlackNode<K,V>`
  `findLastNode(K key)`
  `RedBlackNode<K,V>`
  `getFirst()`
  Returns the first entry in this set.
  `RedBlackNode<K,V>`
  `getLast()`
  Returns the last entry in this set.
  `boolean`
  `isEmpty()`
  Test if the set is empty.
  `RedBlackNode<K,V>`
  `lowerBound(K key)`
  Finds the node with the lowest key that is >= to the given key.
  `Pair<RedBlackNode<K,V>,Boolean>`
  `put(K key, V value)`
  Adds the given key,value to the map.
  `V`
  `remove(K key)`
  Removes the given key (first if duplicates are allowed) from the set.
  `void`
  `removeAll()`
  Removes all entrys from the set.
  `int`
  `size()`
  Returns the number keys in this set.
  `String`
  `toString()`
  `RedBlackNode<K,V>`
  `upperBound(K key)`
  Finds the node with the lowest key that is > the given key.

  ### Methods inherited from class java.lang.Object

  `clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait`

- ## 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.