public class BinarySearchST<Key extends Comparable<Key>,Value> extends Object
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.
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 sorted array. The put and remove operations take Θ(n) time in the worst case. The contains, ceiling, floor, and rank operations take Θ(log n) time in the worst case. The size, is-empty, minimum, maximum, and select operations take Θ(1) time. Construction takes Θ(1) time.
For alternative implementations of the symbol table API,
see ST
, BST
, SequentialSearchST
, RedBlackBST
,
SeparateChainingHashST
, and LinearProbingHashST
,
For additional documentation,
see Section 3.1 of
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
BinarySearchST()
Initializes an empty symbol table.
|
BinarySearchST(int capacity)
Initializes an empty symbol table with the specified initial capacity.
|
Modifier and Type | Method and Description |
---|---|
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.
|
Iterable<Key> |
keys()
Returns all keys in this symbol table as an
Iterable . |
Iterable<Key> |
keys(Key lo,
Key hi)
Returns all keys in this symbol table in the given range,
as an
Iterable . |
static void |
main(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.
|
public BinarySearchST()
public BinarySearchST(int capacity)
capacity
- the maximum capacitypublic int size()
public boolean isEmpty()
true
if this symbol table is empty;
false
otherwisepublic boolean contains(Key key)
key
- the keytrue
if this symbol table contains key
and
false
otherwiseIllegalArgumentException
- if key
is null
public Value get(Key key)
key
- the keynull
if the key is not in the symbol tableIllegalArgumentException
- if key
is null
public int rank(Key key)
key
.key
- the keykey
IllegalArgumentException
- if key
is null
public void put(Key key, Value val)
null
.key
- the keyval
- the valueIllegalArgumentException
- if key
is null
public void delete(Key key)
key
- the keyIllegalArgumentException
- if key
is null
public void deleteMin()
NoSuchElementException
- if the symbol table is emptypublic void deleteMax()
NoSuchElementException
- if the symbol table is emptypublic Key min()
NoSuchElementException
- if this symbol table is emptypublic Key max()
NoSuchElementException
- if this symbol table is emptypublic Key select(int k)
k
- the order statistick
th smallest key in this symbol tableIllegalArgumentException
- unless k
is between 0 and
n–1public Key floor(Key key)
key
.key
- the keykey
NoSuchElementException
- if there is no such keyIllegalArgumentException
- if key
is null
public Key ceiling(Key key)
key
.key
- the keykey
NoSuchElementException
- if there is no such keyIllegalArgumentException
- if key
is null
public int size(Key lo, Key hi)
lo
- minimum endpointhi
- maximum endpointlo
(inclusive) and hi
(inclusive)IllegalArgumentException
- if either lo
or hi
is null
public Iterable<Key> keys()
Iterable
.
To iterate over all of the keys in the symbol table named st
,
use the foreach notation: for (Key key : st.keys())
.public Iterable<Key> keys(Key lo, Key hi)
Iterable
.lo
- minimum endpointhi
- maximum endpointlo
(inclusive) and hi
(inclusive)IllegalArgumentException
- if either lo
or hi
is null
public static void main(String[] args)
BinarySearchST
data type.args
- the command-line arguments