Package dsa

Class RedBlackBinarySearchTreeST<K extends Comparable<K>,V>

java.lang.Object
dsa.RedBlackBinarySearchTreeST<K,V>
Type Parameters:
K - the type of keys in this symbol table.
V - the type of values in this symbol table.
All Implemented Interfaces:
OrderedST<K,V>
public class RedBlackBinarySearchTreeST<K extends Comparable<K>,V> extends Object implements OrderedST<K,V>
This data type provides an implementation of the ordered symbol table (OrderedST) API, using a red-black binary search tree (RBBST) as the underlying data structure.

  • Constructor Summary

    Constructors
    Constructor
    Description
    RedBlackBinarySearchTreeST()
    Constructs an empty symbol table.

  • Method Summary

    Modifier and Type
    Method
    Description
    K
    ceiling(K key)
    Returns the smallest key in this symbol table that is larger than or equal to key.
    boolean
    contains(K key)
    Returns true if this symbol table contains key, and false otherwise.
    void
    delete(K key)
    Deletes key and the associated value from this symbol table.
    void
    deleteMax()
    Deletes the largest key and the associated value from this symbol table.
    void
    deleteMin()
    Deletes the smallest key and the associated value from this symbol table.
    K
    floor(K key)
    Returns the largest key in this symbol table that is smaller than or equal to key.
    V
    get(K key)
    Returns the value associated with key in this symbol table, or null .
    Iterable<K>
    inOrder()
    Returns all the keys from this symbol table in "in" order.
    boolean
    isEmpty()
    Returns true if this symbol table is empty, and false otherwise.
    Iterable<K>
    keys()
    Returns all the keys in this symbol table in sorted order.
    Iterable<K>
    keys(K lo, K hi)
    Returns the keys in this symbol table that are in the interval [lo, hi] in sorted order.
    Iterable<K>
    levelOrder()
    Returns all the keys from this symbol table in "level" order.
    static void
    main(String[] args)
    Unit tests the data type.
    K
    max()
    Returns the largest key in this symbol table.
    K
    min()
    Returns the smallest key in this symbol table.
    Iterable<K>
    postOrder()
    Returns all the keys from this symbol table in "post" order.
    Iterable<K>
    preOrder()
    Returns all the keys from this symbol table in "pre" order.
    void
    put(K key, V value)
    Inserts the key and value pair into this symbol table.
    int
    rank(K key)
    Returns the number of keys in this symbol table that are strictly smaller than key.
    K
    select(int k)
    Returns the key in this symbol table with the rank k.
    int
    size()
    Returns the number of key-value pairs in this symbol table.
    int
    size(K lo, K hi)
    Returns the number of keys in this symbol table that are in the interval [lo, hi].
    String
    toString()
    Returns a string representation of this symbol table.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • RedBlackBinarySearchTreeST

      public RedBlackBinarySearchTreeST()
      Constructs an empty symbol table.

  • Method Details

    • isEmpty

      public boolean isEmpty()
      Returns true if this symbol table is empty, and false otherwise.
      Specified by:
      isEmpty in interface OrderedST<K extends Comparable<K>,V>
      Returns:
      true if this symbol table is empty, and false otherwise.

    • size

      public int size()
      Returns the number of key-value pairs in this symbol table.
      Specified by:
      size in interface OrderedST<K extends Comparable<K>,V>
      Returns:
      the number of key-value pairs in this symbol table.

    • put

      public void put(K key, V value)
      Inserts the key and value pair into this symbol table.
      Specified by:
      put in interface OrderedST<K extends Comparable<K>,V>
      Parameters:
      key - the key.
      value - the value.

    • get

      public V get(K key)
      Returns the value associated with key in this symbol table, or null .
      Specified by:
      get in interface OrderedST<K extends Comparable<K>,V>
      Parameters:
      key - the key.
      Returns:
      the value associated with key in this symbol table, or null .

    • contains

      public boolean contains(K key)
      Returns true if this symbol table contains key, and false otherwise.
      Specified by:
      contains in interface OrderedST<K extends Comparable<K>,V>
      Parameters:
      key - the key.
      Returns:
      true if this symbol table contains key, and false otherwise.

    • delete

      public void delete(K key)
      Deletes key and the associated value from this symbol table.
      Specified by:
      delete in interface OrderedST<K extends Comparable<K>,V>
      Parameters:
      key - the key.

    • keys

      public Iterable<K> keys()
      Returns all the keys in this symbol table in sorted order.
      Specified by:
      keys in interface OrderedST<K extends Comparable<K>,V>
      Returns:
      all the keys in this symbol table in sorted order.

    • min

      public K min()
      Returns the smallest key in this symbol table.
      Specified by:
      min in interface OrderedST<K extends Comparable<K>,V>
      Returns:
      the smallest key in this symbol table.

    • max

      public K max()
      Returns the largest key in this symbol table.
      Specified by:
      max in interface OrderedST<K extends Comparable<K>,V>
      Returns:
      the largest key in this symbol table.

    • deleteMin

      public void deleteMin()
      Deletes the smallest key and the associated value from this symbol table.
      Specified by:
      deleteMin in interface OrderedST<K extends Comparable<K>,V>

    • deleteMax

      public void deleteMax()
      Deletes the largest key and the associated value from this symbol table.
      Specified by:
      deleteMax in interface OrderedST<K extends Comparable<K>,V>

    • floor

      public K floor(K key)
      Returns the largest key in this symbol table that is smaller than or equal to key.
      Specified by:
      floor in interface OrderedST<K extends Comparable<K>,V>
      Parameters:
      key - the key.
      Returns:
      the largest key in this symbol table that is smaller than or equal to key.

    • ceiling

      public K ceiling(K key)
      Returns the smallest key in this symbol table that is larger than or equal to key.
      Specified by:
      ceiling in interface OrderedST<K extends Comparable<K>,V>
      Parameters:
      key - the key.
      Returns:
      the smallest key in this symbol table that is larger than or equal to key.

    • rank

      public int rank(K key)
      Returns the number of keys in this symbol table that are strictly smaller than key.
      Specified by:
      rank in interface OrderedST<K extends Comparable<K>,V>
      Parameters:
      key - the key.
      Returns:
      the number of keys in this symbol table that are strictly smaller than key.

    • select

      public K select(int k)
      Returns the key in this symbol table with the rank k.
      Specified by:
      select in interface OrderedST<K extends Comparable<K>,V>
      Parameters:
      k - the rank.
      Returns:
      the key in this symbol table with the rank k.

    • size

      public int size(K lo, K hi)
      Returns the number of keys in this symbol table that are in the interval [lo, hi].
      Specified by:
      size in interface OrderedST<K extends Comparable<K>,V>
      Parameters:
      lo - lower key.
      hi - higher key
      Returns:
      the number of keys in this symbol table that are in the interval [lo, hi].

    • keys

      public Iterable<K> keys(K lo, K hi)
      Returns the keys in this symbol table that are in the interval [lo, hi] in sorted order.
      Specified by:
      keys in interface OrderedST<K extends Comparable<K>,V>
      Parameters:
      lo - lower key.
      hi - higher key.
      Returns:
      the keys in this symbol table that are in the interval [lo, hi] in sorted order.

    • preOrder

      public Iterable<K> preOrder()
      Returns all the keys from this symbol table in "pre" order.
      Returns:
      all the keys from this symbol table in "pre" order.

    • inOrder

      public Iterable<K> inOrder()
      Returns all the keys from this symbol table in "in" order.
      Returns:
      all the keys from this symbol table in "in" order.

    • postOrder

      public Iterable<K> postOrder()
      Returns all the keys from this symbol table in "post" order.
      Returns:
      all the keys from this symbol table in "post" order.

    • levelOrder

      public Iterable<K> levelOrder()
      Returns all the keys from this symbol table in "level" order.
      Returns:
      all the keys from this symbol table in "level" order.

    • toString

      public String toString()
      Returns a string representation of this symbol table.
      Specified by:
      toString in interface OrderedST<K extends Comparable<K>,V>
      Overrides:
      toString in class Object
      Returns:
      a string representation of this symbol table.

    • main

      public static void main(String[] args)
      Unit tests the data type.
      Parameters:
      args - the command-line arguments.