符號(hào)表
符號(hào)表最主要的一個(gè)目的就是將一個(gè)鍵和一個(gè)值關(guān)聯(lián)起來。用例能夠?qū)⒁粋€(gè)鍵值對(duì)插入符號(hào)表并在之后能夠從符號(hào)表的所有鍵值對(duì)中按照鍵直接查找到相應(yīng)的值。
定義：符號(hào)表是一種存儲(chǔ)鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)，支持兩種操作：插入（put），即將一組鍵值對(duì)存入表中；查找 （get），即根據(jù)給定的鍵得到相應(yīng)的值。
典型的應(yīng)用程序中，鍵都是Comparable對(duì)象，許多符號(hào)表的實(shí)現(xiàn)都利用了Comparable接口來保持鍵的有序性從而更好的實(shí)現(xiàn)put和get方法。更重要的是在這些實(shí)現(xiàn)中，我們可以認(rèn)為符號(hào)表都會(huì)保持鍵的有序并大大擴(kuò)展它的API。
實(shí)現(xiàn)這份API有很多種方式，兩種最為簡單直接的方式就是使用有序數(shù)組或者是鏈表，但是鏈表實(shí)現(xiàn)下查找和插入一個(gè)鍵所需要的時(shí)間都是線性的，有序數(shù)組實(shí)現(xiàn)下查找雖然可以用二分查找優(yōu)化，但插入的成本還是N，所以我們需要更加高效的實(shí)現(xiàn)方式，于是就有了接下來的樹及以后的哈希表。
定義:一棵二叉查找樹是一棵二叉樹，其中每一個(gè)結(jié)點(diǎn)都含有一個(gè)Comparable的鍵(以及相關(guān)聯(lián)的值)，且每個(gè)結(jié)點(diǎn)的鍵都大于左子樹的任意結(jié)點(diǎn)的鍵并小于右子樹的任意結(jié)點(diǎn)的鍵。
二叉樹由結(jié)點(diǎn)組成，節(jié)點(diǎn)包含有指向其他結(jié)點(diǎn)的鏈接，這個(gè)鏈接可以為空也可以指向其他結(jié)點(diǎn)。在二叉樹中，每個(gè)結(jié)點(diǎn)只能有一個(gè)父節(jié)點(diǎn)（根結(jié)點(diǎn)沒有父結(jié)點(diǎn)），而且每個(gè)結(jié)點(diǎn)都只有左右兩個(gè)鏈接，分別指向自己的左子結(jié)點(diǎn)和右子結(jié)點(diǎn)。盡管鏈接指向的是結(jié)點(diǎn)，但是我們可以將每個(gè)鏈接看作指向了另一棵二叉樹，而這棵樹的根結(jié)點(diǎn)就是被指向的結(jié)點(diǎn)。在二叉樹中每一個(gè)結(jié)點(diǎn)都包含了一個(gè)鍵和一個(gè)值，鍵之間也有順序之分以支持高效的查找。
基本實(shí)現(xiàn)
public class BST <Key extends Comparable<Key>, Value>{
private Node root; //二叉查找樹的根結(jié)點(diǎn)
private class Node{
private Key key; //鍵
private Value value;//值
private Node left, right;//指向子樹的鏈接
private int N; //以該結(jié)點(diǎn)為根的子樹中的結(jié)點(diǎ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為根結(jié)點(diǎn)的子樹中查找并返回key所對(duì)應(yīng)的值，如果找不到就返回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)建一個(gè)新的結(jié)點(diǎn)
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);
}
}
上面的代碼實(shí)現(xiàn)了API中的所有方法。
二叉查找樹構(gòu)造的符號(hào)表的性能分析
在一棵二叉樹中，所有操作在最壞的情況下所需的時(shí)間都和樹的高度成正比，對(duì)于，如果鍵夠隨機(jī)，樹的高度將會(huì)是鍵的總數(shù)的對(duì)數(shù)，在這種情況下插入和查找的運(yùn)行時(shí)間的增長數(shù)量級(jí)都會(huì)是lgN, 但是，在一些特定的情況下（比如用例是按從小到大的順序輸入將鍵值對(duì)存入二叉樹的），二叉樹就會(huì)變得根鏈表一樣，從二導(dǎo)致非常差的性能
于是我們需要尋找更好的數(shù)據(jù)結(jié)構(gòu)來解決這個(gè)問題，或許我們能夠使用某種方法來控制樹的高度。
二叉樹的前序，中序，后序遍歷
前序遍歷
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);
}
