Package dsa

Class BinarySearchTreeST<Key extends Comparable<Key>,​Value>

  • All Implemented Interfaces:
    OrderedST<Key,​Value>
    public class BinarySearchTreeST<Key extends Comparable<Key>,​Value>
extends Object
implements OrderedST<Key,​Value>
    This data type provides an implementation of the ordered symbol table (OrderedST) API, using a binary search tree (BST) as the underlying data structure.

    • Constructor Summary

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

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      Key ceiling​(Key key)
      Returns the smallest key in this symbol table that is larger than or equal to key.
      boolean contains​(Key key)
      Returns true if this symbol table contains key, and false otherwise.
      void delete​(Key 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.
      Key floor​(Key key)
      Returns the largest key in this symbol table that is smaller than or equal to key.
      Value get​(Key key)
      Returns the value associated with key in this symbol table, or null .
      Iterable<Key> 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<Key> keys()
      Returns all the keys in this symbol table in sorted order.
      Iterable<Key> keys​(Key lo, Key hi)
      Returns the keys in this symbol table that are in the interval [lo, hi] in sorted order.
      static void main​(String[] args)
      Unit tests the data type.
      Key max()
      Returns the largest key in this symbol table.
      Key min()
      Returns the smallest key in this symbol table.
      Iterable<Key> postOrder()
      Returns all the keys from this symbol table in post-order.
      Iterable<Key> preOrder()
      Returns all the keys from this symbol table in pre-order.
      void put​(Key key, Value value)
      Inserts the key and value pair into this symbol table.
      int rank​(Key key)
      Returns the number of keys in this symbol table that are strictly smaller than key.
      Key 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​(Key lo, Key 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.

    • Constructor Detail

      • BinarySearchTreeST

        public BinarySearchTreeST()
        Constructs an empty symbol table.

    • Method Detail

      • isEmpty

        public boolean isEmpty()
        Description copied from interface: OrderedST
        Returns true if this symbol table is empty, and false otherwise.
        Specified by:
        isEmpty in interface OrderedST<Key extends Comparable<Key>,​Value>
        Returns:
        true if this symbol table is empty, and false otherwise.

      • size

        public int size()
        Description copied from interface: OrderedST
        Returns the number of key-value pairs in this symbol table.
        Specified by:
        size in interface OrderedST<Key extends Comparable<Key>,​Value>
        Returns:
        the number of key-value pairs in this symbol table.

      • put

        public void put​(Key key,
                Value value)
        Description copied from interface: OrderedST
        Inserts the key and value pair into this symbol table.
        Specified by:
        put in interface OrderedST<Key extends Comparable<Key>,​Value>
        Parameters:
        key - the key.
        value - the value.

      • get

        public Value get​(Key key)
        Description copied from interface: OrderedST
        Returns the value associated with key in this symbol table, or null .
        Specified by:
        get in interface OrderedST<Key extends Comparable<Key>,​Value>
        Parameters:
        key - the key.
        Returns:
        the value associated with key in this symbol table, or null .

      • contains

        public boolean contains​(Key key)
        Description copied from interface: OrderedST
        Returns true if this symbol table contains key, and false otherwise.
        Specified by:
        contains in interface OrderedST<Key extends Comparable<Key>,​Value>
        Parameters:
        key - the key.
        Returns:
        true if this symbol table contains key, and false otherwise.

      • delete

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

      • keys

        public Iterable<Key> keys()
        Description copied from interface: OrderedST
        Returns all the keys in this symbol table in sorted order.
        Specified by:
        keys in interface OrderedST<Key extends Comparable<Key>,​Value>
        Returns:
        all the keys in this symbol table in sorted order.

      • min

        public Key min()
        Description copied from interface: OrderedST
        Returns the smallest key in this symbol table.
        Specified by:
        min in interface OrderedST<Key extends Comparable<Key>,​Value>
        Returns:
        the smallest key in this symbol table.

      • max

        public Key max()
        Description copied from interface: OrderedST
        Returns the largest key in this symbol table.
        Specified by:
        max in interface OrderedST<Key extends Comparable<Key>,​Value>
        Returns:
        the largest key in this symbol table.

      • deleteMin

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

      • deleteMax

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

      • floor

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

      • ceiling

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

      • rank

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

      • select

        public Key select​(int k)
        Description copied from interface: OrderedST
        Returns the key in this symbol table with the rank k.
        Specified by:
        select in interface OrderedST<Key extends Comparable<Key>,​Value>
        Parameters:
        k - the rank.
        Returns:
        the key in this symbol table with the rank k.

      • size

        public int size​(Key lo,
                Key hi)
        Description copied from interface: OrderedST
        Returns the number of keys in this symbol table that are in the interval [lo, hi].
        Specified by:
        size in interface OrderedST<Key extends Comparable<Key>,​Value>
        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<Key> keys​(Key lo,
                          Key hi)
        Description copied from interface: OrderedST
        Returns the keys in this symbol table that are in the interval [lo, hi] in sorted order.
        Specified by:
        keys in interface OrderedST<Key extends Comparable<Key>,​Value>
        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<Key> 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<Key> 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<Key> postOrder()
        Returns all the keys from this symbol table in post-order.
        Returns:
        all the keys from this symbol table in post-order.

      • toString

        public String toString()
        Returns a string representation of this symbol table.
        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.