定义
一颗二叉查找树（BST）是一个二叉树，树中的每一个结点都含有一个 Comparable 的键和值。二叉树的每个结点至多连接一颗左子树和一颗右子树，左子树中结点的键都小于根结点的键，右子树中结点的键都大于根结点的键。
基本实现
二叉树通过Node对象实现，每个Node对象包含了一个 key、一个 value、一条左链接、一条右链接和一个结点计数器。左链接指向结点的左子树，右链接指向结点的右子树。
结点计数器计算了根为该结点的所有子树中含有的结点数量，任意结点 x 总满足：size(x) = size(x.left) + size(x.right) + 1;
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
| public class BST<Key extends Comparable<Key>, Value> {
private Node root;
private class Node {
private Key key;
private Value val;
private Node left, right;
private int N;
public Node(Key key, Value val, int size) {
this.key = key;
this.val = val;
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)
public void put(Key key, Value val)
}
|
同一个集合可以使用多棵不同的二叉查找树表示，如果将二叉查找树的所有键映射到一条直线上，可以得到一条有序的键列。
查找
如果树是空的，则查找为命中；如果被查找的键和根结点的键相等，查找命中；否则就递归在子树中查找，如果被查找的键较小就选择左子树，如果被查找的键较大就选择右子树。
1
2
3
4
5
6
7
8
9
10
11
| public Value get(Key key) {
return (get(root, key));
}
private Value 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.value;
}
|
插入
如果树是空的，就返回一个含有该键值对的新结点；如果被查找的键小于根结点的键，继续在左子树插入该键，否则就在右子树中插入该键。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public void put(Key key, Value value) {
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);
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;
}
|
递归
递归调用前的代码可以当作沿着树向下走：它会将给定的键和每一个结点的键相比较并根据结果向左或者向右移动到下一个结点。
递归调用后的代码可以当作沿着树向上走：对于get()方法，对应这一系列的返回指令（return）；对于put()重置搜索路径上的每个父结点指向子结点的链接，并增加路径上每个结点中的计数器的值。
有序性相关的方法与删除操作
最大键和最小键
最小键：如果根结点的左链接为空，那么二叉查找树中的最小键就是根结点；如果左链接非空，那么最小键就是左子树中的最小键。
最大键：类似于最小键，右链接为空，那么二叉查找树中的最大键就是跟结点；如果右链接非空，那么最大键就是右子树中的最大键。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public Key max() {
return max(root).key;
}
public Key min() {
return min(root).key;
}
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);
}
|
向上取整和向下取整
向下取整：如果给定的键key小于二叉查找树的根结点的键，那么小于等于key的最大键floor(key)一定在根结点的左子树中；如果给定的键key大于二叉查找树的根结点，那么floor(key)要么存在于右子树中否在就是当前的根结点。
向上取整：和向下取整相反；
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 Key floor(Key key) {
Node x = floor(root, key);
if (x == null) return null;
return x.key;
}
public Key ceiling(Key key) {
Node x = ceiling(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;
}
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 的键（树中有 k 个小于它的键）。如果左子树中的结点数量 t 大于 k，在左子树中递归寻找排名为 k 的键；如果 t 等于 k，返回当前该根结点中的键；如果 t 小于 k，在右子树中递归寻找排名为（k-t-1）的键。
1
2
3
4
5
6
7
8
9
10
11
12
13
| 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;
}
|
排名操作
rank()是select()的逆方法；
1
2
3
4
5
6
7
8
9
10
11
12
13
| 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 rank(key, x.right) + size(x.left) + 1;
else return size(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
| 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;
}
|
删除操作
如果待删除的结点只有一个子树，那么直接将指向该待删除结点的链接指向唯一子树；否则，可以使用前趋结点或者后继结点替换待删除结点。
前趋结点：左子树中的最大结点；
后继结点：右子树中的最小结点。
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
| 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);
else 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.right) + size(x.left) + 1;
return x;
}
|
范围查找
利用二叉查找树中 key 遍历结果为递增的特点对其进行指定范围的查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public Iterable<Key> keys(Key start, Key end) {
Queue<Key> queue = new Queue<Key>();
keys(root, queue, start, end);
return queue;
}
private void keys(Node x, Queue<Key> queue, Key start, Key end) {
if (x == null) return;
int cmp_start = start.compareTo(x.key);
int cmp_end = end.compareTo(x.key);
if (cmp_start < 0) keys(x.left, queue, start, end);
if (cmp_start <= 0 && cmp_end >= 0) queue.enqueue(x.key);
if (cmp_end > 0) keys(x.right, queue, start, end);
}
|
为了确保在给定结点为根的子树中的所有在指定范围之内的键加入队列，keys()会不断递归查找根结点的左子树，直到左子树为空，然后查找此时的根结点，然后递归查找该根结点的右子树。
复杂度分析
1
| 命题 E 在一个二叉查找树中，所有操作在最坏的情况下所需要的时间都和树的高度成正比。
|
在最好的情况下，一颗含有 N 个结点的树是完全平衡的，每条空链接和根结点的距离都为 lgN，插入和查找的时间复杂度均为 O(1.39lgN)；在最坏的情况下，路径上可能会有 N 个结点，此时插入和查找的时间复杂度为 O(N)。
