符号表
符号表最主要的一个目的就是将一个键和一个值关联起来。用例能够将一个键值对插入符号表并在之后能够从符号表的所有键值对中按照键直接查找到相应的值。
定义：符号表是一种存储键值对的数据结构，支持两种操作：插入（put），即将一组键值对存入表中；查找 （get），即根据给定的键得到相应的值。
典型的应用程序中，键都是Comparable对象，许多符号表的实现都利用了Comparable接口来保持键的有序性从而更好的实现put和get方法。更重要的是在这些实现中，我们可以认为符号表都会保持键的有序并大大扩展它的API。
Symbol tables
实现这份API有很多种方式，两种最为简单直接的方式就是使用有序数组或者是链表，但是链表实现下查找和插入一个键所需要的时间都是线性的，有序数组实现下查找虽然可以用二分查找优化，但插入的成本还是N，所以我们需要更加高效的实现方式，于是就有了接下来的树及以后的哈希表。
定义:一棵二叉查找树是一棵二叉树，其中每一个结点都含有一个Comparable的键(以及相关联的值)，且每个结点的键都大于左子树的任意结点的键并小于右子树的任意结点的键。
二叉树由结点组成，节点包含有指向其他结点的链接，这个链接可以为空也可以指向其他结点。在二叉树中，每个结点只能有一个父节点（根结点没有父结点），而且每个结点都只有左右两个链接，分别指向自己的左子结点和右子结点。尽管链接指向的是结点，但是我们可以将每个链接看作指向了另一棵二叉树，而这棵树的根结点就是被指向的结点。在二叉树中每一个结点都包含了一个键和一个值，键之间也有顺序之分以支持高效的查找。
二叉树
基本实现
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; //以该结点为根的子树中的结点总数
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,找到就更新它的值，否则为它创建一个新的结点
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的键的数量
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);
}
}
上面的代码实现了API中的所有方法。
二叉查找树构造的符号表的性能分析
在一棵二叉树中，所有操作在最坏的情况下所需的时间都和树的高度成正比，对于，如果键够随机，树的高度将会是键的总数的对数，在这种情况下插入和查找的运行时间的增长数量级都会是lgN, 但是，在一些特定的情况下（比如用例是按从小到大的顺序输入将键值对存入二叉树的），二叉树就会变得根链表一样，从二导致非常差的性能
二叉树
于是我们需要寻找更好的数据结构来解决这个问题，或许我们能够使用某种方法来控制树的高度。
二叉树的前序，中序，后序遍历
前序遍历
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);
}
