java.lang.Object
- edu.princeton.cs.algs4.BinarySearchST<Key,Value>

```
public class BinarySearchST<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, 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.
This implementation uses a sorted array. 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 and remove operations each take linear time in the worst case; the contains, ceiling, floor, and rank operations take logarithmic time; the size, is-empty, minimum, maximum, and select operations take constant time. Construction takes constant time.
For additional documentation, see Section 3.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. For other implementations, see ST, BST, SequentialSearchST, RedBlackBST, SeparateChainingHashST, and LinearProbingHashST, Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

构造器概要

构造器
构造器说明

BinarySearchST()
Initializes an empty symbol table.

BinarySearchST(int capacity)
Initializes an empty symbol table with the specified initial capacity.

方法概要

修饰符和类型	方法	说明
`Key`	`ceiling(Key key)`	Returns the smallest key in this 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 associated value from this symbol table (if the key is in the symbol table).
`void`	`deleteMax()`	Removes the largest key and associated value from this symbol table.
`void`	`deleteMin()`	Removes the smallest key and associated value from this symbol table.
`Key`	`floor(Key key)`	Returns the largest key in this symbol table less than or equal to `key`.
`Value`	`get(Key key)`	Returns the value associated with the given key in this symbol table.
`boolean`	`isEmpty()`	Returns true if this symbol table is empty.
`java.lang.Iterable<Key>`	`keys()`	Returns all keys in this symbol table as an `Iterable`.
`java.lang.Iterable<Key>`	`keys(Key lo, Key hi)`	Returns all keys in this symbol table in the given range, as an `Iterable`.
`static void`	`main(java.lang.String[] args)`	Unit tests the `BinarySearchST` data type.
`Key`	`max()`	Returns the largest key in this symbol table.
`Key`	`min()`	Returns the smallest key in this 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)`	Returns the number of keys in this symbol table strictly less than `key`.
`Key`	`select(int k)`	Return the kth smallest key in this symbol table.
`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 in the specified range.

从类继承的方法 java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- 构造器详细资料
  - BinarySearchST
```
public BinarySearchST()
```
    Initializes an empty symbol table.
  - BinarySearchST
```
public BinarySearchST(int capacity)
```
    Initializes an empty symbol table with the specified initial capacity.
    
    参数:
    
    capacity - the maximum capacity
- 方法详细资料
  - 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
  - isEmpty
```
public boolean isEmpty()
```
    Returns true if this symbol table is empty.
    
    返回:
    
    true if this symbol table is empty; false otherwise
  - 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 in this symbol table.
    
    参数:
    
    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
  - rank
```
public int rank(Key key)
```
    Returns the number of keys in this 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
  - 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
  - delete
```
public void delete(Key key)
```
    Removes the specified key and associated value from this symbol table (if the key is in the symbol table).
    
    参数:
    
    key - the key
    
    抛出:
    
    java.lang.IllegalArgumentException - if key is null
  - deleteMin
```
public void deleteMin()
```
    Removes the smallest key and associated value from this symbol table.
    
    抛出:
    
    java.util.NoSuchElementException - if the symbol table is empty
  - deleteMax
```
public void deleteMax()
```
    Removes the largest key and associated value from this symbol table.
    
    抛出:
    
    java.util.NoSuchElementException - if the symbol table is empty
  - min
```
public Key min()
```
    Returns the smallest key in this symbol table.
    
    返回:
    
    the smallest key in this symbol table
    
    抛出:
    
    java.util.NoSuchElementException - if this symbol table is empty
  - max
```
public Key max()
```
    Returns the largest key in this symbol table.
    
    返回:
    
    the largest key in this symbol table
    
    抛出:
    
    java.util.NoSuchElementException - if this symbol table is empty
  - select
```
public Key select(int k)
```
    Return the kth smallest key in this symbol table.
    
    参数:
    
    k - the order statistic
    
    返回:
    
    the kth smallest key in this symbol table
    
    抛出:
    
    java.lang.IllegalArgumentException - unless k is between 0 and n–1
  - floor
```
public Key floor(Key key)
```
    Returns the largest key in this symbol table less than or equal to key.
    
    参数:
    
    key - the key
    
    返回:
    
    the largest key in this symbol table less than or equal to key
    
    抛出:
    
    java.util.NoSuchElementException - if there is no such key
    
    java.lang.IllegalArgumentException - if key is null
  - ceiling
```
public Key ceiling(Key key)
```
    Returns the smallest key in this symbol table greater than or equal to key.
    
    参数:
    
    key - the key
    
    返回:
    
    the smallest key in this symbol table greater than or equal to key
    
    抛出:
    
    java.util.NoSuchElementException - if there is no such key
    
    java.lang.IllegalArgumentException - if key is null
  - size
```
public int size(Key lo,
                Key hi)
```
    Returns the number of keys in this symbol table in the specified range.
    
    参数:
    
    lo - minimum endpoint
    
    hi - maximum endpoint
    
    返回:
    
    the number of keys in this symbol table between lo (inclusive) and hi (inclusive)
    
    抛出:
    
    java.lang.IllegalArgumentException - if either lo or hi is null
  - keys
```
public java.lang.Iterable<Key> keys()
```
    Returns all keys in this 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 this symbol table
  - keys
```
public java.lang.Iterable<Key> keys(Key lo,
                                    Key hi)
```
    Returns all keys in this symbol table in the given range, as an Iterable.
    
    参数:
    
    lo - minimum endpoint
    
    hi - maximum endpoint
    
    返回:
    
    all keys in this symbol table between lo (inclusive) and hi (inclusive)
    
    抛出:
    
    java.lang.IllegalArgumentException - if either lo or hi is null
  - main
```
public static void main(java.lang.String[] args)
```
    Unit tests the BinarySearchST data type.
    
    参数:
    
    args - the command-line arguments

构造器	说明
`BinarySearchST()`	Initializes an empty symbol table.
`BinarySearchST(int capacity)`	Initializes an empty symbol table with the specified initial capacity.

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

构造器概要

方法概要

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

构造器详细资料

BinarySearchST

BinarySearchST

方法详细资料

size

isEmpty

contains

get

rank

put

delete

deleteMin

deleteMax

min

max

select

floor

ceiling

size

keys

keys

main

类 BinarySearchST<Key extends java.lang.Comparable<Key>,Value>