AVLTreeST (Algorithms 4/e)

Object
- edu.princeton.cs.algs4.AVLTreeST<Key,Value>

```
public class AVLTreeST<Key extends Comparable<Key>,Value>
extends Object
```
The 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.

Author:

Marcelo Silva

Constructor Summary

Constructors
Constructor and Description

AVLTreeST()
Initializes an empty symbol table.

Constructors
Constructor and Description
`AVLTreeST()` Initializes an empty symbol table.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
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.

Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - AVLTreeST
```
public AVLTreeST()
```
    Initializes an empty symbol table.
- Method Detail
  - isEmpty
```
public boolean isEmpty()
```
    Checks if the symbol table is empty.
    
    Returns:
    
    true if the symbol table is empty.
  - size
```
public int size()
```
    Returns the number key-value pairs in the symbol table.
    
    Returns:
    
    the number key-value pairs in the symbol table
  - height
```
public int height()
```
    Returns the height of the internal AVL tree. It is assumed that the height of an empty tree is -1 and the height of a tree with just one node is 0.
    
    Returns:
    
    the height of the internal AVL tree
  - get
```
public Value get(Key key)
```
    Returns the value associated with the given key.
    
    Parameters:
    
    key - the key
    
    Returns:
    
    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
    
    Throws:
    
    IllegalArgumentException - if key is null
  - contains
```
public boolean contains(Key key)
```
    Checks if the symbol table contains the given key.
    
    Parameters:
    
    key - the key
    
    Returns:
    
    true if the symbol table contains key and false otherwise
    
    Throws:
    
    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.
    
    Parameters:
    
    key - the key
    
    val - the value
    
    Throws:
    
    IllegalArgumentException - if key is null
  - delete
```
public void delete(Key key)
```
    Removes the specified key and its associated value from the symbol table (if the key is in the symbol table).
    
    Parameters:
    
    key - the key
    
    Throws:
    
    IllegalArgumentException - if key is null
  - deleteMin
```
public void deleteMin()
```
    Removes the smallest key and associated value from the symbol table.
    
    Throws:
    
    NoSuchElementException - if the symbol table is empty
  - deleteMax
```
public void deleteMax()
```
    Removes the largest key and associated value from the symbol table.
    
    Throws:
    
    NoSuchElementException - if the symbol table is empty
  - min
```
public Key min()
```
    Returns the smallest key in the symbol table.
    
    Returns:
    
    the smallest key in the symbol table
    
    Throws:
    
    NoSuchElementException - if the symbol table is empty
  - max
```
public Key max()
```
    Returns the largest key in the symbol table.
    
    Returns:
    
    the largest key in the symbol table
    
    Throws:
    
    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.
    
    Parameters:
    
    key - the key
    
    Returns:
    
    the largest key in the symbol table less than or equal to key
    
    Throws:
    
    NoSuchElementException - if the symbol table is empty
    
    IllegalArgumentException - if key is null
  - ceiling
```
public Key ceiling(Key key)
```
    Returns the smallest key in the symbol table greater than or equal to key.
    
    Parameters:
    
    key - the key
    
    Returns:
    
    the smallest key in the symbol table greater than or equal to key
    
    Throws:
    
    NoSuchElementException - if the symbol table is empty
    
    IllegalArgumentException - if key is null
  - select
```
public Key select(int k)
```
    Returns the kth smallest key in the symbol table.
    
    Parameters:
    
    k - the order statistic
    
    Returns:
    
    the kth smallest key in the symbol table
    
    Throws:
    
    IllegalArgumentException - unless k is between 0 and size() -1
  - rank
```
public int rank(Key key)
```
    Returns the number of keys in the symbol table strictly less than key.
    
    Parameters:
    
    key - the key
    
    Returns:
    
    the number of keys in the symbol table strictly less than key
    
    Throws:
    
    IllegalArgumentException - if key is null
  - keys
```
public Iterable<Key> keys()
```
    Returns all keys in the symbol table.
    
    Returns:
    
    all keys in the symbol table
  - keysInOrder
```
public Iterable<Key> keysInOrder()
```
    Returns all keys in the symbol table following an in-order traversal.
    
    Returns:
    
    all keys in the symbol table following an in-order traversal
  - keysLevelOrder
```
public Iterable<Key> keysLevelOrder()
```
    Returns all keys in the symbol table following a level-order traversal.
    
    Returns:
    
    all keys in the symbol table following a level-order traversal.
  - keys
```
public Iterable<Key> keys(Key lo,
                          Key hi)
```
    Returns all keys in the symbol table in the given range.
    
    Parameters:
    
    lo - the lowest key
    
    hi - the highest key
    
    Returns:
    
    all keys in the symbol table between lo (inclusive) and hi (exclusive)
    
    Throws:
    
    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.
    
    Parameters:
    
    lo - minimum endpoint
    
    hi - maximum endpoint
    
    Returns:
    
    the number of keys in the symbol table between lo (inclusive) and hi (exclusive)
    
    Throws:
    
    IllegalArgumentException - if either lo or hi is null
  - main
```
public static void main(String[] args)
```
    Unit tests the AVLTreeST data type.
    
    Parameters:
    
    args - the command-line arguments

Class AVLTreeST<Key extends Comparable<Key>,Value>

Constructor Summary

Method Summary

Methods inherited from class Object

Constructor Detail

AVLTreeST

Method Detail

isEmpty

size

height

get

contains

put

delete

deleteMin

deleteMax

min

max

floor

ceiling

select

rank

keys

keysInOrder

keysLevelOrder

keys

size

main