符号表
符号表(Symbol table)是一种存储键值对的数据结构，用来将一个键和一个值联系起来。我们将信息存储在其中，然后按照指定的键来搜索并获取这些信息，可见，符号表必须支持高效的插入和查找操作。符号表应用广泛，经常可见其身影，如Python中的数据结构Dictionary，JavaScript的复杂数据类型Object也可以看成一组键值对。
二叉查找树
链式结构可以支持高效的插入操作，二分查找可以保证查找的高效率，但是单链表无法支持二分查找，将二者结合起来，就产生了更高效的数据结构，二叉查找树(Binary Search Tree)。
- 二叉树是一个空链接，或者是一个有左右两个链接的结点，并且每个链接都指向一棵独立的子二叉树。
- 二叉查找树是一棵二叉树，其中每个结点都含有一个键以及关联的值，并且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。
二叉查找树结合了二分查找的效率和链表的灵活性，不仅可以保证符号表插入与查找操作的效率，还保持了表中键的相对顺序，支持有序性操作。书中使用递归来操作二叉查找树以实现符号表的各个操作，每个实现都很简洁，了解其中的细节可以加深我们对树这种递归数据结构的认识。
插入和查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| public void put(Key key, Value val) {
root = put(root, key, val);
}
private Node put(Node x, Key key, Value val) {
if (x == null) {
return new Node(key, val, 1);
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = put(x.left, key, val);
} else if (cmp > 0) {
x.right = put(x.right, key, val);
} else {
x.val = val;
}
return x;
}
public Value get(Key key) {
Node d = get(root, key);
if (d == null) {
return null;
} else {
return d.val;
}
}
private Node get(Node x, Key key) {
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;
}
}
|
每个公有方法都对应着一个私有方法，私有方法额外接受一个指向结点的链接，并返回一个指向结点的链接，如此一来，我们可以使用返回的链接方便地改变树的结构。查找的过程利用了二分查找的高效率，如果树是空的，则未命中，返回null；如果键相等，则返回此结点；否则就递归地在子树中查找。插入的过程也类似，如果树是空的，就返回一个新结点；如果被查找的键小于根结点的键，就在左子树中插入该键；如果被查找的键大于根结点的键，就在右子树中插入该键；否则，就改变根结点绑定的值。
使用二叉查找树的算法的运行时间取决于树的形状。假设键的插入顺序是随机的，此时二叉查找树和快速排序是极为类似的，在由\(N\)个随机键构造的二叉查找树中，查找命中平均所需的比较次数为\(～2lnN\)，插入操作和查找未命中平均所需的比较次数也为\(～2lnN\)。
最大键与最小键
1
2
3
4
5
6
7
8
9
10
11
12
13
| private Node max(Node x) {
if (x.right == null) {
return x;
}
return max(x.right);
}
private Node min(Node x) {
if (x.left == null) {
return x;
}
return min(x.left);
}
|
如果根结点的右链接为空，那么这棵二叉查找树的最大的结点就是根结点；否则，就是右子树中的最大值。上面的代码和寻找一条单链表的尾结点是一样的，由此可见树和链表的渊源，从根结点到叶结点的每条路径，都可看成一条链表。树保持了结点的相对顺序，寻找最大键与最小键的过程，就是寻找’最右‘和’最左‘两条链表的尾结点。
向下取整和向上取整
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| 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 d = floor(x.right, key);
if (d != null) {
return d;
} else {
return x;
}
}
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 d = ceiling(x.left, key);
if (d != null) {
return d;
} else {
return x;
}
}
|
如果给定的键key等于二叉查找树的根结点的键，则返回根节点；如果给定的键key小于二叉查找树的根结点的键，那么小于等于key的最大键floor(key)一定在根结点的左子树中；如果给定的键key大于二叉查找树的根结点的键，那么只有当根结点右子树中存在小于等于key的结点时，小于等于key的最大键才会出现在右子树中，否则根结点就是小于等于key的最大键。向上取整ceiling()逻辑与向下取整相同，改变方向即可。
删除操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| private Node deleteMin(Node x) {
if (x.left == null) {
return x.right;
}
x.left = deleteMin(x.left);
return x;
}
private Node deleteMax(Node x) {
if (x.right == null) {
return x.left;
}
x.right = deleteMax(x.right);
return x;
}
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);
} else if (cmp > 0) {
x.right = delete(x.right, key);
} else {
if (x.left == null) {
return x.right;
} else if (x.right == null) {
return x.left;
} else {
Node t = x;
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
}
return x;
}
|
删除最大值和最小值的操作和查询操作类似，在一个方向上不断递归，直至遇到一个空链接，然后我们将指向该结点的链接指向该结点的另一个子树。删除任意结点时，考虑的情况更复杂些，如果待删除的结点只有一个子树时，我们将指向待删除结点的链接指向该结点的另一个子树即可；如果待删除的结点有两个子树时，此时将空出一条链接，但却又两棵子树需要处理，我们需要找出右子树的最小结点来作为待删除结点的后继结点，这个结点可以保证树的有序性，左子树都比它小，右子树都比他大，然后正确设置它的左右子树。
范围操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| private void keys(Node x, Queue<Key> q, 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, q, lo, hi);
}
if (cmplo <= 0 && cmphi >= 0) {
q.enqueue(x.key);
}
if (cmphi > 0) {
keys(x.right, q, lo, hi);
}
}
|
采用中序遍历的方式遍历整个查找树，将符合的结点加入至队列中。其中判断if (cmplo < 0)和if (cmphi > 0)不是必需的，不过如此可以减少一半的计算量，因为符合要求的结点不会出现在lo的左侧和hi的右侧。
在一棵二叉查找树中，所有操作在最坏情况下所需的时间都和树的高度成正比。如果插入的键是随机的话，概率可以保证树的平均高度为树中结点数的对数级别，和二叉查找树类似的快速排序可以通过事先打乱数据来保证性能，但二叉查找树却不可以，因为顺序是由用例控制的，顺序插入也不是不可能，因此我们需要更好的数据结构——平衡二叉查找树，平衡二叉查找树可以保证无论键的插入顺序如何，树的高度都将是总键数的对数。
参考资料
源码
相关习题解答