符號表
符號表最主要的一個目的就是將一個鍵和一個值關聯(lián)起來。用例能夠將一個鍵值對插入符號表并在之后能夠從符號表的所有鍵值對中按照鍵直接查找到相應的值竹捉。
定義：符號表是一種存儲鍵值對的數(shù)據(jù)結構瘫里，支持兩種操作：插入（put）型宝，即將一組鍵值對存入表中郑原；查找 （get），即根據(jù)給定的鍵得到相應的值。
典型的應用程序中，鍵都是Comparable對象纬霞，許多符號表的實現(xiàn)都利用了Comparable接口來保持鍵的有序性從而更好的實現(xiàn)put和get方法。更重要的是在這些實現(xiàn)中驱显，我們可以認為符號表都會保持鍵的有序并大大擴展它的API诗芜。
Symbol tables
實現(xiàn)這份API有很多種方式，兩種最為簡單直接的方式就是使用有序數(shù)組或者是鏈表埃疫，但是鏈表實現(xiàn)下查找和插入一個鍵所需要的時間都是線性的伏恐，有序數(shù)組實現(xiàn)下查找雖然可以用二分查找優(yōu)化，但插入的成本還是N栓霜，所以我們需要更加高效的實現(xiàn)方式翠桦，于是就有了接下來的樹及以后的哈希表。
定義:一棵二叉查找樹是一棵二叉樹胳蛮，其中每一個結點都含有一個Comparable的鍵(以及相關聯(lián)的值)销凑，且每個結點的鍵都大于左子樹的任意結點的鍵并小于右子樹的任意結點的鍵。
二叉樹由結點組成仅炊，節(jié)點包含有指向其他結點的鏈接斗幼，這個鏈接可以為空也可以指向其他結點。在二叉樹中茂洒，每個結點只能有一個父節(jié)點（根結點沒有父結點）孟岛，而且每個結點都只有左右兩個鏈接瓶竭，分別指向自己的左子結點和右子結點。盡管鏈接指向的是結點渠羞，但是我們可以將每個鏈接看作指向了另一棵二叉樹斤贰，而這棵樹的根結點就是被指向的結點。在二叉樹中每一個結點都包含了一個鍵和一個值次询，鍵之間也有順序之分以支持高效的查找荧恍。
二叉樹
基本實現(xiàn)
public class BST <Key extends Comparable<Key>, Value>{
private Node root; //二叉查找樹的根結點
private class Node{
private Key key; //鍵
private Value value;//值
private Node left, right;//指向子樹的鏈接
private int N; //以該結點為根的子樹中的結點總數(shù)
public Node(Key key, Value value, int N)
{this.key = key; this.value = value; this.N = N;}
}
public int size(){
return size(root);
}
private int size(Node x){
if (x == null) return 0;
else return x.N;
}
public Value get(Key key){
return get(root, key);
}
private Value get(Node x, Key key){
//在以x為根結點的子樹中查找并返回key所對應的值，如果找不到就返回null
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) return get(x.left, key);
else if (cmp > 0) return get(x.right, key);
else return x.value;
}
public void put(Key key, Value value){
//查找key,找到就更新它的值屯吊，否則為它創(chuàng)建一個新的結點
root = put(root, key, value);
}
private Node put(Node x, Key key, Value value){
if (x == null) return new Node(key, value, 1);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key,value);
else if (cmp > 0) x.right = put(x.right, key, value);
else x.value = value;
x.N = size(x.left) + size(x.right) + 1;
return x;
}
//查找最小鍵
public Key min(){
return min(root).key;
}
private Node min(Node x){
if (x.left == null) return x;
return min(x.left);
}
//查找最大鍵
public Key max(){
return max(root).key;
}
private Node max(Node x){
if (x.right == null) return x;
return max(x.right);
}
//查找小于等于key的最大鍵
public Key floor(Key key){
Node x = floor(root, key);
if (x == null) return null;
return x.key;
}
private Node floor(Node x, Key key){
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp == 0) return x;
if (cmp < 0) return floor(x.left, key);
Node t = floor(x.right, key);
if (t != null) return t;
else return x;
}
//查找大于等于key的最小鍵
public Key ceiling(Key key){
Node x = ceiling(root, key);
if (x == null) return null;
return x.key;
}
private Node ceiling(Node x, Key key){
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp == 0) return x;
if (cmp > 0) return ceiling(x.right, key);
Node t = ceiling(x.left, key);
if (t != null) return t;
else return x;
}
//查找排名為k的鍵
public Key select(int k){
return select(root, k).key;
}
private Node select(Node x, int k){
if (x == null) return null;
int t = size(x.left);
if (t > k) return select(x.left, k);
else if (t < k) return select(x.right, k-t-1);
else return x;
}
//小于key的鍵的數(shù)量
public int rank(Key key){
return rank(key, root);
}
private int rank(Key key, Node x){
if (x == null) return 0;
int cmp = key.compareTo(x.key);
if (cmp < 0) return rank(key, x.left);
else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right);
else return size(x.left);
}
//刪除最小鍵
public void deleteMin(){
root = deleteMin(root);
}
private Node deleteMin(Node x){
if (x.left == null) return x.right;
x.left = deleteMin(x.left);
x.N = size(x.left) + size(x.right) + 1;
return x;
}
//刪除最大鍵
public void deleteMax(){
root = deleteMax(root);
}
private Node deleteMax(Node x){
if (x.right == null) return x.left;
x.right = deleteMax(x.right);
x.N = size(x.left) + size(x.right) + 1;
return x;
}
//刪除任意鍵
public void delete(Key key){
root = delete(root, key);
}
private Node delete(Node x, Key key){
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = delete(x.left, key);
if (cmp > 0) x.right = delete(x.right, key);
else {
if (x.right == null) return x.left;
if (x.left == null) return x.right;
Node t = x;
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}
//二叉查找樹的范圍查找
public Iterable<Key> keys(){
return keys(min(), max());
}
public Iterable<Key> keys(Key lo, Key hi){
Queue<Key> queue = new Queue<key>();
keys(root, queue, lo, hi);
return queue;
}
private void keys(Node x, Queue<Key> queue,Key lo, Key hi){
if (x == null) return;
int cmplo = lo.compareTo(x.key);
int cmphi = hi.compareTo(x.key);
if (cmplo < 0) keys(x.left, queue, lo, hi);
if (cmphi <= 0 && cmphi >= 0) queue.equeue(x.key);
if (cmphi > 0) keys(x.right, queue, lo, hi);
}
}
上面的代碼實現(xiàn)了API中的所有方法送巡。
二叉查找樹構造的符號表的性能分析
在一棵二叉樹中，所有操作在最壞的情況下所需的時間都和樹的高度成正比盒卸，對于骗爆，如果鍵夠隨機，樹的高度將會是鍵的總數(shù)的對數(shù)蔽介，在這種情況下插入和查找的運行時間的增長數(shù)量級都會是lgN, 但是摘投，在一些特定的情況下（比如用例是按從小到大的順序輸入將鍵值對存入二叉樹的），二叉樹就會變得根鏈表一樣虹蓄，從二導致非常差的性能
二叉樹
于是我們需要尋找更好的數(shù)據(jù)結構來解決這個問題犀呼，或許我們能夠使用某種方法來控制樹的高度。
二叉樹的前序薇组，中序外臂，后序遍歷
前序遍歷
private void print(Node x){
if (x == null) return;
System.out.println(x.key);
print(x.left);
print(x.right);
}
中序遍歷
private void print(Node x){
if (x == null) return;
print(x.left);
System.out.println(x.key);
print(x.right);
}
后序遍歷
private void print(Node x){
if (x == null) return;
print(x.left);
print(x.right);
System.out.println(x.key);
}
