程序包 edu.princeton.cs.algs4

类 BST<Key extends java.lang.Comparable<Key>,​Value>

  • public class BST<Key extends java.lang.Comparable<Key>,​Value>
extends java.lang.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, select, 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.

    This implementation uses an (unbalanced) binary search tree. 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(). The put, contains, remove, minimum, maximum, ceiling, floor, select, and rank operations each take linear time in the worst case, if the tree becomes unbalanced. The size, and is-empty operations take constant time. Construction takes constant time.

    For additional documentation, see Section 3.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. For other implementations, see ST, BinarySearchST, SequentialSearchST, RedBlackBST, SeparateChainingHashST, and LinearProbingHashST,

    • 构造器概要

      构造器 
      构造器 说明
      BST()
      Initializes an empty symbol table.

    • 方法概要

      修饰符和类型 方法 说明
      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.
      Key floor2​(Key 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()
      Returns true if this symbol table is empty.
      java.lang.Iterable<Key> keys()
      Returns all keys in the symbol table as an Iterable.
      java.lang.Iterable<Key> keys​(Key lo, Key hi)
      Returns all keys in the symbol table in the given range, as an Iterable.
      java.lang.Iterable<Key> levelOrder()
      Returns the keys in the BST in level order (for debugging).
      static void main​(java.lang.String[] args)
      Unit tests the BST 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 k)
      Return the key in the symbol table whose rank is 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 the symbol table in the given range.

      • 从类继承的方法 java.lang.Object

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

    • 构造器详细资料

      • BST

        public BST()
        Initializes an empty symbol table.

    • 方法详细资料

      • isEmpty

        public boolean isEmpty()
        Returns true if this symbol table is empty.
        返回:
        true if this symbol table is empty; false otherwise

      • size

        public int size()
        Returns the number of key-value pairs in this symbol table.
        返回:
        the number of key-value pairs in this symbol table

      • contains

        public boolean contains​(Key key)
        Does this symbol table contain the given key?
        参数:
        key - the key
        返回:
        true if this symbol table contains key and false otherwise
        抛出:
        java.lang.IllegalArgumentException - if key is null

      • get

        public Value get​(Key key)
        Returns the value associated with the given key.
        参数:
        key - the key
        返回:
        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
        抛出:
        java.lang.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.
        参数:
        key - the key
        val - the value
        抛出:
        java.lang.IllegalArgumentException - if key is null

      • deleteMin

        public void deleteMin()
        Removes the smallest key and associated value from the symbol table.
        抛出:
        java.util.NoSuchElementException - if the symbol table is empty

      • deleteMax

        public void deleteMax()
        Removes the largest key and associated value from the symbol table.
        抛出:
        java.util.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).
        参数:
        key - the key
        抛出:
        java.lang.IllegalArgumentException - if key is null

      • min

        public Key min()
        Returns the smallest key in the symbol table.
        返回:
        the smallest key in the symbol table
        抛出:
        java.util.NoSuchElementException - if the symbol table is empty

      • max

        public Key max()
        Returns the largest key in the symbol table.
        返回:
        the largest key in the symbol table
        抛出:
        java.util.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.
        参数:
        key - the key
        返回:
        the largest key in the symbol table less than or equal to key
        抛出:
        java.util.NoSuchElementException - if there is no such key
        java.lang.IllegalArgumentException - if key is null

      • floor2

        public Key floor2​(Key key)

      • ceiling

        public Key ceiling​(Key key)
        Returns the smallest key in the symbol table greater than or equal to key.
        参数:
        key - the key
        返回:
        the smallest key in the symbol table greater than or equal to key
        抛出:
        java.util.NoSuchElementException - if there is no such key
        java.lang.IllegalArgumentException - if key is null

      • select

        public Key select​(int k)
        Return the key in the symbol table whose rank is k. This is the (k+1)st smallest key in the symbol table.
        参数:
        k - the order statistic
        返回:
        the key in the symbol table of rank k
        抛出:
        java.lang.IllegalArgumentException - unless k 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.
        参数:
        key - the key
        返回:
        the number of keys in the symbol table strictly less than key
        抛出:
        java.lang.IllegalArgumentException - if key is null

      • keys

        public java.lang.Iterable<Key> keys()
        Returns all keys in the symbol table 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()).
        返回:
        all keys in the symbol table

      • keys

        public java.lang.Iterable<Key> keys​(Key lo,
                                    Key hi)
        Returns all keys in the symbol table in the given range, as an Iterable.
        参数:
        lo - minimum endpoint
        hi - maximum endpoint
        返回:
        all keys in the symbol table between lo (inclusive) and hi (inclusive)
        抛出:
        java.lang.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.
        参数:
        lo - minimum endpoint
        hi - maximum endpoint
        返回:
        the number of keys in the symbol table between lo (inclusive) and hi (inclusive)
        抛出:
        java.lang.IllegalArgumentException - if either lo or hi is null

      • height

        public int height()
        Returns the height of the BST (for debugging).
        返回:
        the height of the BST (a 1-node tree has height 0)

      • levelOrder

        public java.lang.Iterable<Key> levelOrder()
        Returns the keys in the BST in level order (for debugging).
        返回:
        the keys in the BST in level order traversal

      • main

        public static void main​(java.lang.String[] args)
        Unit tests the BST data type.
        参数:
        args - the command-line arguments