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

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

构造器概要

构造器
构造器说明

AVLTreeST()
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)`	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.
`java.lang.Iterable<Key>`	`keys()`	Returns all keys in the symbol table.
`java.lang.Iterable<Key>`	`keys(Key lo, Key hi)`	Returns all keys in the symbol table in the given range.
`java.lang.Iterable<Key>`	`keysInOrder()`	Returns all keys in the symbol table following an in-order traversal.
`java.lang.Iterable<Key>`	`keysLevelOrder()`	Returns all keys in the symbol table following a level-order traversal.
`static void`	`main(java.lang.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.

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

- 构造器详细资料
  - AVLTreeST
```
public AVLTreeST()
```
    Initializes an empty symbol table.
- 方法详细资料
  - isEmpty
```
public boolean isEmpty()
```
    Checks if the symbol table is empty.
    
    返回:
    
    true if the symbol table is empty.
  - size
```
public int size()
```
    Returns the number key-value pairs in the symbol table.
    
    返回:
    
    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.
    
    返回:
    
    the height of the internal AVL tree
  - 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
  - contains
```
public boolean contains(Key key)
```
    Checks if the symbol table contains the given key.
    
    参数:
    
    key - the key
    
    返回:
    
    true if the symbol table contains key and false otherwise
    
    抛出:
    
    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 its associated value from the 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 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
  - 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 the symbol table is empty
    
    java.lang.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.
    
    参数:
    
    key - the key
    
    返回:
    
    the smallest key in the symbol table greater than or equal to key
    
    抛出:
    
    java.util.NoSuchElementException - if the symbol table is empty
    
    java.lang.IllegalArgumentException - if key is null
  - select
```
public Key select(int k)
```
    Returns the kth smallest key in the symbol table.
    
    参数:
    
    k - the order statistic
    
    返回:
    
    the kth smallest key in the symbol table
    
    抛出:
    
    java.lang.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.
    
    参数:
    
    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.
    
    返回:
    
    all keys in the symbol table
  - keysInOrder
```
public java.lang.Iterable<Key> keysInOrder()
```
    Returns all keys in the symbol table following an in-order traversal.
    
    返回:
    
    all keys in the symbol table following an in-order traversal
  - keysLevelOrder
```
public java.lang.Iterable<Key> keysLevelOrder()
```
    Returns all keys in the symbol table following a level-order traversal.
    
    返回:
    
    all keys in the symbol table following a level-order traversal.
  - keys
```
public java.lang.Iterable<Key> keys(Key lo,
                                    Key hi)
```
    Returns all keys in the symbol table in the given range.
    
    参数:
    
    lo - the lowest key
    
    hi - the highest key
    
    返回:
    
    all keys in the symbol table between lo (inclusive) and hi (exclusive)
    
    抛出:
    
    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 (exclusive)
    
    抛出:
    
    java.lang.IllegalArgumentException - if either lo or hi is null
  - main
```
public static void main(java.lang.String[] args)
```
    Unit tests the AVLTreeST data type.
    
    参数:
    
    args - the command-line arguments

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

构造器概要

方法概要

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

构造器详细资料

AVLTreeST

方法详细资料

isEmpty

size

height

get

contains

put

delete

deleteMin

deleteMax

min

max

floor

ceiling

select

rank

keys

keysInOrder

keysLevelOrder

keys

size

main

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