RedBlackBST (Algorithms 4/e)

Object
- edu.princeton.cs.algs4.RedBlackBST<Key,Value>

```
public class RedBlackBST<Key extends Comparable<Key>,Value>
extends Object
```
The BST class represents an ordered symbol table of generic key-value pairs. It supports the usual put, get, contains, delete, size, and is-empty methods. It also provides ordered methods for finding the minimum, maximum, floor, and ceiling. It also provides a keys method for iterating over all of the keys. A symbol table implements the associative array abstraction: when associating a value with a key that is already in the symbol table, the convention is to replace the old value with the new value. Unlike Map, this class uses the convention that values cannot be null—setting the value associated with a key to null is equivalent to deleting the key from the symbol table.
It requires that the key type implements the Comparable interface and calls the compareTo() and method to compare two keys. It does not call either equals() or hashCode().
This implementation uses a left-leaning red-black BST. The put, get, contains, remove, minimum, maximum, ceiling, floor, rank, and select operations each take Θ(log n) time in the worst case, where n is the number of key-value pairs in the symbol table. The size, and is-empty operations take Θ(1) time. The keys methods take O(log n + m) time, where m is the number of keys returned by the iterator. Construction takes Θ(1) time.
For alternative implementations of the symbol table API, see ST, BinarySearchST, SequentialSearchST, BST, SeparateChainingHashST, LinearProbingHashST, and AVLTreeST. For additional documentation, see Section 3.3 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors
Constructor and Description

RedBlackBST()
Initializes an empty symbol table.

Constructors
Constructor and Description
`RedBlackBST()` Initializes an empty symbol table.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`Key`	`ceiling(Key key)` Returns the smallest key in the symbol table greater than or equal to `key`.
`boolean`	`contains(Key key)` Does this symbol table contain the given key?
`void`	`delete(Key key)` Removes the specified key and its associated value from this symbol table (if the key is in this symbol table).
`void`	`deleteMax()` Removes the largest key and associated value from the symbol table.
`void`	`deleteMin()` Removes the smallest key and associated value from the symbol table.
`Key`	`floor(Key key)` Returns the largest key in the symbol table less than or equal to `key`.
`Value`	`get(Key key)` Returns the value associated with the given key.
`int`	`height()` Returns the height of the BST (for debugging).
`boolean`	`isEmpty()` Is this symbol table empty?
`Iterable<Key>`	`keys()` Returns all keys in the symbol table in ascending order as an `Iterable`.
`Iterable<Key>`	`keys(Key lo, Key hi)` Returns all keys in the symbol table in the given range in ascending order, as an `Iterable`.
`static void`	`main(String[] args)` Unit tests the `RedBlackBST` data type.
`Key`	`max()` Returns the largest key in the symbol table.
`Key`	`min()` Returns the smallest key in the symbol table.
`void`	`put(Key key, Value val)` Inserts the specified key-value pair into the symbol table, overwriting the old value with the new value if the symbol table already contains the specified key.
`int`	`rank(Key key)` Return the number of keys in the symbol table strictly less than `key`.
`Key`	`select(int rank)` Return the key in the symbol table of a given `rank`.
`int`	`size()` Returns the number of key-value pairs in this symbol table.
`int`	`size(Key lo, Key hi)` Returns the number of keys in the symbol table in the given range.

Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - RedBlackBST
```
public RedBlackBST()
```
    Initializes an empty symbol table.
- Method Detail
  - size
```
public int size()
```
    Returns the number of key-value pairs in this symbol table.
    
    Returns:
    
    the number of key-value pairs in this symbol table
  - isEmpty
```
public boolean isEmpty()
```
    Is this symbol table empty?
    
    Returns:
    
    true if this symbol table is empty and false otherwise
  - get
```
public Value get(Key key)
```
    Returns the value associated with the given key.
    
    Parameters:
    
    key - the key
    
    Returns:
    
    the value associated with the given key if the key is in the symbol table and null if the key is not in the symbol table
    
    Throws:
    
    IllegalArgumentException - if key is null
  - contains
```
public boolean contains(Key key)
```
    Does this symbol table contain the given key?
    
    Parameters:
    
    key - the key
    
    Returns:
    
    true if this symbol table contains key and false otherwise
    
    Throws:
    
    IllegalArgumentException - if key is null
  - put
```
public void put(Key key,
                Value val)
```
    Inserts the specified key-value pair into the symbol table, overwriting the old value with the new value if the symbol table already contains the specified key. Deletes the specified key (and its associated value) from this symbol table if the specified value is null.
    
    Parameters:
    
    key - the key
    
    val - the value
    
    Throws:
    
    IllegalArgumentException - if key is null
  - deleteMin
```
public void deleteMin()
```
    Removes the smallest key and associated value from the symbol table.
    
    Throws:
    
    NoSuchElementException - if the symbol table is empty
  - deleteMax
```
public void deleteMax()
```
    Removes the largest key and associated value from the symbol table.
    
    Throws:
    
    NoSuchElementException - if the symbol table is empty
  - delete
```
public void delete(Key key)
```
    Removes the specified key and its associated value from this symbol table (if the key is in this symbol table).
    
    Parameters:
    
    key - the key
    
    Throws:
    
    IllegalArgumentException - if key is null
  - height
```
public int height()
```
    Returns the height of the BST (for debugging).
    
    Returns:
    
    the height of the BST (a 1-node tree has height 0)
  - min
```
public Key min()
```
    Returns the smallest key in the symbol table.
    
    Returns:
    
    the smallest key in the symbol table
    
    Throws:
    
    NoSuchElementException - if the symbol table is empty
  - max
```
public Key max()
```
    Returns the largest key in the symbol table.
    
    Returns:
    
    the largest key in the symbol table
    
    Throws:
    
    NoSuchElementException - if the symbol table is empty
  - floor
```
public Key floor(Key key)
```
    Returns the largest key in the symbol table less than or equal to key.
    
    Parameters:
    
    key - the key
    
    Returns:
    
    the largest key in the symbol table less than or equal to key
    
    Throws:
    
    NoSuchElementException - if there is no such key
    
    IllegalArgumentException - if key is null
  - ceiling
```
public Key ceiling(Key key)
```
    Returns the smallest key in the symbol table greater than or equal to key.
    
    Parameters:
    
    key - the key
    
    Returns:
    
    the smallest key in the symbol table greater than or equal to key
    
    Throws:
    
    NoSuchElementException - if there is no such key
    
    IllegalArgumentException - if key is null
  - select
```
public Key select(int rank)
```
    Return the key in the symbol table of a given rank. This key has the property that there are rank keys in the symbol table that are smaller. In other words, this key is the (rank+1)st smallest key in the symbol table.
    
    Parameters:
    
    rank - the order statistic
    
    Returns:
    
    the key in the symbol table of given rank
    
    Throws:
    
    IllegalArgumentException - unless rank is between 0 and n–1
  - rank
```
public int rank(Key key)
```
    Return the number of keys in the symbol table strictly less than key.
    
    Parameters:
    
    key - the key
    
    Returns:
    
    the number of keys in the symbol table strictly less than key
    
    Throws:
    
    IllegalArgumentException - if key is null
  - keys
```
public Iterable<Key> keys()
```
    Returns all keys in the symbol table in ascending order as an Iterable. To iterate over all of the keys in the symbol table named st, use the foreach notation: for (Key key : st.keys()).
    
    Returns:
    
    all keys in the symbol table in ascending order
  - keys
```
public Iterable<Key> keys(Key lo,
                          Key hi)
```
    Returns all keys in the symbol table in the given range in ascending order, as an Iterable.
    
    Parameters:
    
    lo - minimum endpoint
    
    hi - maximum endpoint
    
    Returns:
    
    all keys in the symbol table between lo (inclusive) and hi (inclusive) in ascending order
    
    Throws:
    
    IllegalArgumentException - if either lo or hi is null
  - size
```
public int size(Key lo,
                Key hi)
```
    Returns the number of keys in the symbol table in the given range.
    
    Parameters:
    
    lo - minimum endpoint
    
    hi - maximum endpoint
    
    Returns:
    
    the number of keys in the symbol table between lo (inclusive) and hi (inclusive)
    
    Throws:
    
    IllegalArgumentException - if either lo or hi is null
  - main
```
public static void main(String[] args)
```
    Unit tests the RedBlackBST data type.
    
    Parameters:
    
    args - the command-line arguments

Class RedBlackBST<Key extends Comparable<Key>,Value>

Constructor Summary

Method Summary

Methods inherited from class Object

Constructor Detail

RedBlackBST

Method Detail

size

isEmpty

get

contains

put

deleteMin

deleteMax

delete

height

min

max

floor

ceiling

select

rank

keys

keys

size

main