1. 定义
二叉搜索树(BST)又叫二叉查找树，二叉排序树。二叉搜索树就是一棵二叉树，但是它又具有搜索树的特征：
- 每个结点都比它的左结点大，比右结点小。
- 每个结点的左右子树都是一课二叉搜索树。
- 对一棵二叉搜索树进行中序遍历结果是从小到大排序的结果。
2. 时间复杂度
二叉搜索树结合了链表插入删除的灵活性和数组的查找的高效性。
- 最好情况：
最好情况下的二叉搜索树是一棵满二叉树，这时从根结点到所有叶子结点的长度都为lgN，对应树的高度也为lgN。此时无论查找，插入，删除都可以在O(lgN)时间内完成。
- 最坏情况：
最坏情况下的二叉搜索树的每个结点只有一个孩子，几乎是链表的形状了，对应树的高度为N。此时查找，插入，删除的时间复杂度为O(N)。
- 平均情况：
二叉搜索树的平均情况应该是介于最好和最好情况之间。
3. 实现
接下来我用二叉搜索树来实现一个符号表，符号表就是一个存储键值对的数据结构，其中键不可以重复，值可以重复。定义了如下操作：
- put(Key key, Value value) 将键key和值value插入符号表
- delete(Key key) 删除指定的键值对
- get(Key key) 获取键对应的值，如果不存在该键则返回null
- deleteMax() 删除最大的键对应的键值对
- deleteMin() 删除最小的键对应的键值对
- min() 获取最小的键
- max() 获取最大的键
- size() 获取符号表的大小
- isEmpty() 判断符号表否为空
代码用java描述，使用了泛型。因为需要进行比较操作，所以键都必须实现Comparable接口。在BST这个类中，使用了一个内部类Node来表示二叉搜索树的结点，同时也是一个键值对。所有操作都是采用迭代的方式。
代码实现
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
|
public class BST<Key extends Comparable<Key>, Value> {
private class Node {
Key key;
Value value;
Node left;
Node right;
public Node(Key key, Value value, Node left, Node right){
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
private Node root;
private int size;
public int size(){
return size;
}
public boolean isEmpty(){
return root == null;
}
public Value get(Key key){
Node node = root;
int cmp;
while(node != null){
cmp = key.compareTo(node.key);
if (cmp < 0)
node = node.left;
else if (cmp > 0)
node = node.right;
else
return node.value;
}
return null;
}
public void put(Key key, Value value){
if (root == null) {
root = new Node(key, value, null, null);
size = 1;
return;
}
Node node = root;
Node parent = null;
int cmp;
while (node != null){
parent = node;
cmp = key.compareTo(node.key);
if (cmp < 0)
node = node.left;
else if (cmp > 0)
node = node.right;
else {
node.value = value;
return;
}
}
if (key.compareTo(parent.key) < 0)
parent.left = new Node(key, value, null, null);
else
parent.right = new Node(key, value, null, null);
++size;
}
private Node max(Node node){
if (node == null)
return null;
while (node.right != null)
node = node.right;
return node;
}
private Node min(Node node){
if (node == null)
return null;
while (node.left != null)
node = node.left;
return node;
}
public Key max(){
Node node = max(root);
return node == null ? null : node.key;
}
public Key min(){
Node node = min(root);
return node == null ? null : node.key;
}
private Node deleteMax(Node node) {
Node x = node;
if (node == null)
return null;
Node parent = null;
while (node.right != null){
parent = node;
node = node.right;
}
--size;
if (parent == null)
return node.left;
else
parent.right = node.left;
return x;
}
private Node deleteMin(Node node) {
Node x = node;
if (node == null)
return null;
Node parent = null;
while (node.left != null){
parent = node;
node = node.left;
}
--size;
if (parent == null)
return node.right;
else
parent.left = node.right;
return x;
}
public void deleteMax(){
root = deleteMax(root);
}
public void deleteMin(){
root = deleteMin(root);
}
public void traverse(){
traverse(root);
}
private void traverse(Node node){
if (node == null)
return;
traverse(node.left);
System.out.println(node.key);
traverse(node.right);
}
public void delete(Key key) {
if (root == null)
return;
Node node = root;
Node parent = root;
int cmp;
while (node != null){
cmp = key.compareTo(node.key);
if (cmp == 0) {
--size;
cmp = key.compareTo(parent.key);
if (node.left == null){
if (cmp < 0)
parent.left = node.right;
else if (cmp > 0)
parent.right = node.right;
else
root = node.right;
return;
}
if (node.right == null){
if (cmp < 0)
parent.left = node.left;
else if (cmp > 0)
parent.right = node.left;
else
root = node.left;
return;
}
Node x = min(node.right);
node.key = x.key;
node.value = x.value;
node.right = deleteMax(node.right);
}
else {
parent = node;
if (cmp < 0)
node = node.left;
else
node = node.right;
}
}
}
public static void main(String[] args){
BST<Integer, String> bst = new BST<>();
bst.put(2, "qw");
bst.put(3, "fy");
bst.put(5, "naoko");
bst.put(1, "qw");
bst.put(4, "naoko");
bst.put(-3, "naoko");
bst.deleteMax();
bst.deleteMin();
bst.delete(10);
bst.traverse();
}
}
|
4. 最后
二叉搜索树虽然简单但在最坏情况下表现得并不好。不过它是其他树类型的数据结构的基础，二叉搜索树还有其他变种如AVL树，红黑树，Treap树等。在C++，Java的集合API中，符号表或是Set的实现一般都是用红黑树。
最后更新时间：