public class AVLTreeST<Key extends Comparable<Key>,Value> extends Object
AVLTreeST
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, 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 symbol table implementation uses internally an AVL tree (Georgy Adelson-Velsky and Evgenii Landis' tree) which is a self-balancing BST. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.
This implementation 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, get, contains,
delete, minimum, maximum, ceiling, and
floor operations each take logarithmic time in the worst case. The
size, and is-empty operations take constant time.
Construction also takes constant time.
For other implementations of the same API, see ST
, BinarySearchST
,
SequentialSearchST
, BST
, RedBlackBST
,
SeparateChainingHashST
, and LinearProbingHashST
.
Constructor and Description |
---|
AVLTreeST()
Initializes an empty symbol table.
|
Modifier and Type | Method and Description |
---|---|
Key |
ceiling(Key key)
Returns the smallest key in the symbol table greater than or equal to
key . |
boolean |
contains(Key key)
Checks if the symbol table contains the given key.
|
void |
delete(Key key)
Removes the specified key and its associated value from the symbol table
(if the key is in the 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 . |
Value |
get(Key key)
Returns the value associated with the given key.
|
int |
height()
Returns the height of the internal AVL tree.
|
boolean |
isEmpty()
Checks if the symbol table is empty.
|
Iterable<Key> |
keys()
Returns all keys in the symbol table.
|
Iterable<Key> |
keys(Key lo,
Key hi)
Returns all keys in the symbol table in the given range.
|
Iterable<Key> |
keysInOrder()
Returns all keys in the symbol table following an in-order traversal.
|
Iterable<Key> |
keysLevelOrder()
Returns all keys in the symbol table following a level-order traversal.
|
static void |
main(String[] args)
Unit tests the
AVLTreeST 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)
Returns the number of keys in the symbol table strictly less than
key . |
Key |
select(int k)
Returns the kth smallest key in the symbol table.
|
int |
size()
Returns the number key-value pairs in the symbol table.
|
int |
size(Key lo,
Key hi)
Returns the number of keys in the symbol table in the given range.
|
public boolean isEmpty()
true
if the symbol table is empty.public int size()
public int height()
public Value get(Key key)
key
- the keynull
if the key is not in the
symbol tableIllegalArgumentException
- if key
is null
public boolean contains(Key key)
key
- the keytrue
if the symbol table contains key
and false
otherwiseIllegalArgumentException
- 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 the symbol table is emptypublic Key max()
NoSuchElementException
- if the symbol table is emptypublic Key floor(Key key)
key
.key
- the keykey
NoSuchElementException
- if the symbol table is emptyIllegalArgumentException
- if key
is null
public Key ceiling(Key key)
key
.key
- the keykey
NoSuchElementException
- if the symbol table is emptyIllegalArgumentException
- if key
is null
public Key select(int k)
k
- the order statisticIllegalArgumentException
- unless k
is between 0 and
size() -1
public int rank(Key key)
key
.key
- the keykey
IllegalArgumentException
- if key
is null
public Iterable<Key> keys()
public Iterable<Key> keysInOrder()
public Iterable<Key> keysLevelOrder()
public Iterable<Key> keys(Key lo, Key hi)
lo
- the lowest keyhi
- the highest keylo
(inclusive)
and hi
(exclusive)IllegalArgumentException
- if either lo
or hi
is null
public int size(Key lo, Key hi)
lo
- minimum endpointhi
- maximum endpointlo
(inclusive) and hi
(exclusive)IllegalArgumentException
- if either lo
or hi
is null
public static void main(String[] args)
AVLTreeST
data type.args
- the command-line arguments