符号表与二叉查找树

符号表

符号表用于存储键值对。通常符号表按功能提供了如下 API(由 API 可逐步深入到设计决策、测试用例、实现等):

  • get: 获取指定 key 键的值。
  • put: 将键值对存入符号表中。
  • delete: 删除指定的键值对。
  • contains: 判断符号表中是否包含指定的键。
  • isEmpty: 判断符号表是否为空。
  • size: 获取符号表中键值对的数量。
  • keys: 获取符号表中所有 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
public class SequentialSearchST<Key, Value>{
private Node<Key, Value> first;
private int N;// 键值对数量

// 链表节点模型
private static class Node<Key, Value> {
public Key key;
public Value val;
public Node<Key, Value> next;

public Node(Key key, Value val, Node<Key, Value> next) {
this.key = k;
this.val = val;
this.next = next;
}
}

public Value get(Key key) {
for (Node<Key, Value> x = first ; x != null; x = x.next) {
if (x.key.equals(key))
return x.val;
}
return null;
}
public void put(Key key, Value val) {
for (Node<Key, Value> x = first; x != null; x = x.next) {
if (x.key.equals(key)) {
x.val = val;
return;
}
}
first = new Node<Key, Value>(key, val, first);
N++;
}
}

有序符号表

有序符号表需要额外实现如下接口:

  • min, max: 获取最小键、最大键。
  • floor, ceiling: 向下取整、向上取整。
  • select: 获取指定排名的键。该操作可应用于搜索引擎的排名等。
  • rank: 获取小于指定 key 键的节点数量。该操作可应用于搜索引擎的排名等。
  • deleteMin: 删除最小键。
  • deleteMax: 删除最大键。

基于有序数组实现的有序符号表,可借助两分查找法快速插入和获取键值对,其核心方法为 rank。相比于链表,基于有序数组实现的符号表能保证查找的高效,但是在插入节点需要对后续节点执行额外的移位动作。以下为其实现:

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
42
43
44
public class BinarySearchST<Key extends Comparable<Key>, Value>{
private Key[] keys;
private Value[] vals;
private int N;// 键值对数量
public BinarySearchST(int capacity){
keys = (Key[]) new Comparable[capacity];
vals = (Value[]) new Object[capacity];
}

// 基于两分查找法,获取小于指定 key 键的节点数量
public int rank(Key key){
int lo = 0, hi = N - 1;
while(lo <= hi){
int mid = lo + (hi - lo) / 2;
int cmp = key.compareTo(keys[mid]);
if (cmp < 0) hi = mid - 1;
else if (cmp > 0) lo = mid + 1;
else return mid;
}
return lo;
}

public Value get(Key key){
if (isEmpty()) return null;
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0) return vals[i];
else return null;
}
public void put(Key key, Value val){
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0){// 有则替换
vals[i] = val;
return;
}
// 后续键值对移位
for (int j = N; j > i; j--){
keys[j] = keys[j - 1];
vals[j] = vals[j - 1];
}
keys[i] = key;
vals[i] = val;
N++;
}
}

二叉查找树

二叉查找树 Binary Search Tree(BST) 是有序符号表的一种。在二叉树中,每个父节点下的左右子节点按 key 键有序排列,这样在查找和插入节点时就能保证如快速排序的高效。二叉树的设计原则包含:私有方法提供抽象,公共方法提供接口;二叉树基于节点建模,节点保有子节点和子树的信息,私有方法须实现可递归性。二叉查找树的 API 如有序符号表,包含基本的查找、插入、删除操作:

  • size: 获取节点数量。
  • get: 向下递归查找节点。
  • put: 插入节点。基于向下递归插入节点,向上递归更新节点数量。
  • min, max: 获取最小键、最大键。
  • floor, ceiling: 向下取整、向上取整。
  • select: 获取指定排名的键。
  • rank: 获取小于指定 key 键的节点数量。
  • delete: 删除节点。当被删除节点为父节点时,使用前驱或后继节点与该节点换位的方式删除。
  • deleteMin: 删除最小键,该方法可用于后继节点替换模式的删除操作。
  • deleteMax: 删除最大键,该方法可用于前驱节点替换模式的删除操作。
  • keys: 借助于中序遍历,获取二叉树中或指定范围内所有键的集合。
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
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 N){
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){
return get(root, key);
}
private Value get(Node x, Key key){
if (x == null) return null;
int cmp = key.compateTo(x.key);
if (cmp < 0) return get(x.left, key);
else if (cmp > 0) return get(x.right, key);
else return x.val;
}

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;
x.N = size(x.left) + size(x.right) + 1;
return x;
}

// 获取最小键;max 方法与之相类
public Key min(){
return min(root).key;
}
private Node min(Node x){
if (x.left == null) return x;
return min(x.left);
}

// 向下取整;ceiling 向上取整与之相类
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;// 返回左子树中的节点,以便向上递归
}

// 获取排名为 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 键的数量,入参 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);// 右子树中会包含大于 key 的键
else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right);
else return size(x.left);// 父节点与 key 键相同,统计左子树的节点数量
}

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 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.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 comlo = lo.compareTo(x.key);
int comhi = hi.compareTo(x.key);
if (comlo < 0) keys(x.left, queue, lo, hi);// 收集左子树中的 key
if (comlo <= 0 && comhi >= 0) queue.enqueue(x.key);// 在指定范围内,收集 key 键
if (comhi > 0) keys(x.right, queue, lo, hi);// 收集右子树中的 key
}
}