二叉搜索树
二叉搜索树的原理与实现：插入、查找、删除操作。
一句话算法
二叉搜索树把小的数放左边、大的数放右边，于是每次比较都能丢掉一整棵子树。
问题模型
我们需要维护一个动态有序集合，支持：
- 插入一个数。
- 删除一个数。
- 判断一个数是否存在。
- 查询最小值、最大值。
- 查询一个节点的前驱和后继。
基础二叉搜索树不保证平衡，所以它更适合作为理解平衡树、Treap、Splay、红黑树的入门模型。
核心直觉
在有序数组中查找时，我们可以比较中间值，然后决定去左半边还是右半边。
二叉搜索树把这个思想变成一棵树：每个节点都是一个分岔口。
- 目标值小于当前节点：只可能在左子树。
- 目标值大于当前节点：只可能在右子树。
- 目标值等于当前节点：查找成功。
“BST 不变量”
对任意节点 u：
- 左子树所有节点的值都小于
u.key。 - 右子树所有节点的值都大于
u.key。 - 左右子树本身也都是二叉搜索树。
算法步骤
查找
从根节点开始：
- 当前节点为空，说明查找失败。
x == key，说明查找成功。x < key，进入左子树。x > key，进入右子树。
插入
插入和查找路径相同：
- 从根节点向下比较。
- 如果遇到相同值，本模板选择不重复插入。
- 如果走到空位置，就把新节点接到这里。
最小值与最大值
- 最小值：从根开始一直向左走，直到没有左儿子。
- 最大值：从根开始一直向右走，直到没有右儿子。
前驱与后继
前驱是小于当前值的最大节点，后继是大于当前值的最小节点。
后继有两种情况：
- 如果有右子树，后继就是右子树中的最小节点。
- 如果没有右子树，就不断向父亲走，直到第一次从某个父亲的左边上来，这个父亲就是后继。
前驱完全对称：
- 如果有左子树，前驱就是左子树中的最大节点。
- 如果没有左子树，就不断向父亲走，直到第一次从某个父亲的右边上来，这个父亲就是前驱。
删除
删除节点分三类：
- 叶子节点：直接断开它和父亲的连接。
- 只有一个孩子：用这个孩子顶替它的位置。
- 有两个孩子：用后继的值覆盖当前节点，再删除那个后继节点。
第三类可行的原因是：后继是右子树最小值，它替换当前节点后，仍然大于左子树所有值，也不大于右子树剩余值。
算法证明
查找正确性
关键不变量： 如果目标值 x 存在，它一定在当前正在搜索的子树中。
- 初始时当前子树是整棵树，不变量成立。
- 若
x < key，根据 BST 不变量，右子树所有值都大于key，因此x不可能在右子树，只需要进入左子树。 - 若
x > key，同理，x不可能在左子树，只需要进入右子树。 - 若走到空节点，当前候选子树为空，所以
x不存在。
因此查找过程不会漏掉可能位置，也不会走进不可能的位置。
插入正确性
插入时走的是查找失败的路径。走到空位置时，这个空位置的祖先已经通过比较确定了它应该处在哪个区间内。
把新节点接在这里：
- 对它的父亲来说，左右方向满足大小关系。
- 对它的所有祖先来说，它仍然落在之前比较确定的合法区间内。
- 新节点没有子树，自身也满足 BST 不变量。
所以插入后整棵树仍是二叉搜索树。
删除正确性
删除叶子或只有一个孩子的节点时，只是移除或上提一棵已经满足 BST 不变量的子树。
删除有两个孩子的节点时，用后继 s 的值替换它：
s是右子树最小值，所以s大于当前节点左子树中所有值。s在右子树中最小，所以右子树剩余节点都大于等于s。- 后继节点本身最多只有右孩子，删除它会落回前两种简单情况。
因此删除后 BST 不变量仍成立。
复杂度分析
设树高为
- 查找、插入、删除、最值、前驱、后继：
。 - 空间复杂度：
。
如果树接近平衡，
代码实现
cpp
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
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
#include <iostream>
#include <vector>
#include <optional>
#include <algorithm>
#include <memory>
// BST 节点定义
struct Node {
int key;
Node *left, *right, *parent;
Node(int key) : key(key), left(nullptr), right(nullptr), parent(nullptr) {}
};
// 查找操作 (递归实现)
bool find(int x, Node* t) {
if (t == nullptr) {
return false;
}
if (x < t->key) {
return find(x, t->left);
} else if (x > t->key) {
return find(x, t->right);
} else {
return true;
}
}
// 查找操作 (非递归实现)
bool find_iterative(int x, Node* t) {
while (t != nullptr) {
if( x < t->key)
t = t->left;
else if( x > t->key)
t = t->right;
else return true;
}
return false;
}
// 插入操作 (递归实现)
// 注意：这个实现没有处理 parent 指针，非递归版本更好
void insert_dfs(int x, Node*& t) {
if (t == nullptr) {
t = new Node(x);
return;
}
if (x < t->key) {
insert_dfs(x, t->left);
if(t->left) t->left->parent = t; // 设置父节点
} else if (x > t->key) {
insert_dfs(x, t->right);
if(t->right) t->right->parent = t; // 设置父节点
}
// 如果 x == t->key，不做任何操作
}
// 插入操作 (非递归实现，推荐)
void insert(int x, Node*& t) {
Node* p = t;
Node* parent = nullptr;
while (p != nullptr) {
parent = p; // 记录父节点
if( x < p->key)
p = p->left;
else if( x > p->key)
p = p->right;
else return; //do nothing, 元素已存在
}
Node* newNode = new Node(x);
newNode->parent = parent; // 设置新节点的父节点
if (parent == nullptr) {
t = newNode; // 树为空，新节点为根
} else if (x < parent->key) { // 根据 BST 不变量决定插入位置
parent->left = newNode;
} else {
parent->right = newNode;
}
}
// 查找最小节点 (返回指针)
Node* findMinNode(Node* t) {
if (t == nullptr) return nullptr;
while (t->left != nullptr) {
t = t->left;
}
return t;
}
// 查找最大节点 (返回指针)
Node* findMaxNode(Node* t) {
if (t == nullptr) return nullptr;
while (t->right != nullptr) {
t = t->right;
}
return t;
}
// 查找最小值 (返回键值)
std::optional<int> findMin(Node* t) {
Node* minNode = findMinNode(t);
if (minNode) {
return minNode->key;
}
return std::nullopt;
}
// 查找最大值 (返回键值)
std::optional<int> findMax(Node* t) {
Node* maxNode = findMaxNode(t);
if (maxNode) {
return maxNode->key;
}
return std::nullopt;
}
// 查找后继
Node* succ(Node* x) {
if (x == nullptr) return nullptr;
// 情况 1: 节点有右子树
if (x->right != nullptr) {
return findMinNode(x->right);
}
// 情况 2: 节点没有右子树
Node* p = x->parent;
while (p != nullptr && x == p->right) {
x = p;
p = p->parent;
}
return p; // p 是后继, 或者 p 是 nullptr (x是最大值)
}
// 查找前驱
Node* prev(Node* x) {
if (x == nullptr) return nullptr;
// 情况 1: 节点有左子树
if (x->left != nullptr) {
return findMaxNode(x->left);
}
// 情况 2: 节点没有左子树
Node* p = x->parent;
while (p != nullptr && x == p->left) {
x = p;
p = p->parent;
}
return p; // p 是前驱, 或者 p 是 nullptr (x是最小值)
}
// 删除最小值
void deleteMin(Node*& root) {
if (root == nullptr) return;
Node* minNode = findMinNode(root);
if (minNode == nullptr) return;
// 最小节点没有左孩子
if (minNode->parent == nullptr) { // 是根节点
root = minNode->right;
} else {
minNode->parent->left = minNode->right;
}
if (minNode->right) {
minNode->right->parent = minNode->parent;
}
delete minNode;
}
// 删除操作
void delete_node(int x, Node*& root) {
if (root == nullptr) return;
Node* current = root;
// 1. 先找到要删除的节点
while (current != nullptr && current->key != x) {
if (x < current->key) {
current = current->left;
} else {
current = current->right;
}
}
if (current == nullptr) return; // 没找到要删除的节点
Node* p = current->parent;
// 2. 处理删除的三种情况
// 情况 1: 删除叶子节点
if (current->left == nullptr && current->right == nullptr) {
if (p == nullptr) { // 删除的是根节点
root = nullptr;
} else if (p->left == current) {
p->left = nullptr;
} else {
p->right = nullptr;
}
delete current;
return;
}
// 情况 2: 删除只有一个孩子的节点
if (current->left == nullptr || current->right == nullptr) {
Node* child = (current->left != nullptr) ? current->left : current->right;
if (p == nullptr) { // 删除的是根节点
root = child;
child->parent = nullptr;
} else if (p->left == current) {
p->left = child;
child->parent = p;
} else {
p->right = child;
child->parent = p;
}
delete current;
return;
}
// 情况 3: 删除有两个孩子的节点
// 找到后继节点 (右子树的最小值)
Node* successor = findMinNode(current->right);
// 用后继节点的值替换当前节点的值
current->key = successor->key;
// 删除后继节点 (后继节点最多只有一个右孩子)
// 注意：后继节点的父节点不可能是 current
if (successor->parent->left == successor) {
successor->parent->left = successor->right;
} else {
successor->parent->right = successor->right;
}
if (successor->right) {
successor->right->parent = successor->parent;
}
delete successor;
}
// 辅助函数：释放树内存
void freeTree(Node* node) {
if (node == nullptr) return;
freeTree(node->left);
freeTree(node->right);
delete node;
}
// 辅助函数：中序遍历，用于验证
void inOrderTraversal(Node* node, std::vector<int>& result) {
if (node == nullptr) return;
inOrderTraversal(node->left, result);
result.push_back(node->key);
inOrderTraversal(node->right, result);
}
// 辅助函数：打印树的结构（简版）
void printTree(Node* node, std::string indent = "", bool isLeft = true) {
if (node != nullptr) {
std::cout << indent;
if (isLeft) {
std::cout << "L---";
indent += " ";
} else {
std::cout << "R---";
indent += "| ";
}
std::cout << node->key << std::endl;
printTree(node->left, indent, true);
printTree(node->right, indent, false);
}
}
// 测试主函数
int main() {
std::cout << "--- BST 测试 ---" << std::endl;
std::vector<int> nums = {5, 3, 8, 1, 4, 7, 9, 2};
std::cout << "原始数据: ";
for (int n : nums) std::cout << n << " ";
std::cout << std::endl;
Node* root = nullptr;
for (int n : nums) {
insert(n, root);
}
std::cout << "\n--- 构建的树 ---" << std::endl;
printTree(root);
std::vector<int> orderedList;
inOrderTraversal(root, orderedList);
std::cout << "\n--- 中序遍历 ---" << std::endl;
std::cout << "结果: ";
for (int n : orderedList) std::cout << n << " ";
std::cout << std::endl;
std::cout << "\n--- 查找 ---" << std::endl;
std::cout << "查找 4 (应为 1): " << find(4, root) << std::endl;
std::cout << "查找 6 (应为 0): " << find(6, root) << std::endl;
std::cout << "\n--- 最小值/最大值 ---" << std::endl;
auto minVal = findMin(root);
auto maxVal = findMax(root);
std::cout << "最小值 (应为 1): " << (minVal.has_value() ? std::to_string(minVal.value()) : "nullopt") << std::endl;
std::cout << "最大值 (应为 9): " << (maxVal.has_value() ? std::to_string(maxVal.value()) : "nullopt") << std::endl;
std::cout << "\n--- 后继/前驱 ---" << std::endl;
Node* node4 = root->left->right; // 节点 4
Node* node5 = root; // 节点 5
Node* node9 = root->right->right; // 节点 9
Node* node1 = root->left->left; // 节点 1
auto succ4 = succ(node4);
auto succ5 = succ(node5);
auto succ9 = succ(node9);
auto prev4 = prev(node4);
auto prev1 = prev(node1);
std::cout << "4 的后继 (应为 5): " << (succ4 ? std::to_string(succ4->key) : "nullptr") << std::endl;
std::cout << "5 的后继 (应为 7): " << (succ5 ? std::to_string(succ5->key) : "nullptr") << std::endl;
std::cout << "9 的后继 (应为 nullptr): " << (succ9 ? std::to_string(succ9->key) : "nullptr") << std::endl;
std::cout << "4 的前驱 (应为 3): " << (prev4 ? std::to_string(prev4->key) : "nullptr") << std::endl;
std::cout << "1 的前驱 (应为 nullptr): " << (prev1 ? std::to_string(prev1->key) : "nullptr") << std::endl;
std::cout << "\n--- 插入 ---" << std::endl;
insert(6, root);
std::cout << "插入 6 后的树:" << std::endl;
printTree(root);
orderedList.clear();
inOrderTraversal(root, orderedList);
std::cout << "中序遍历 (应包含 6): ";
for (int n : orderedList) std::cout << n << " ";
std::cout << std::endl;
std::cout << "\n--- 删除 ---" << std::endl;
std::cout << "删除 2 (叶节点):" << std::endl;
delete_node(2, root);
printTree(root);
orderedList.clear();
inOrderTraversal(root, orderedList);
std::cout << "中序: ";
for (int n : orderedList) std::cout << n << " ";
std::cout << std::endl;
std::cout << "\n删除 3 (两个子节点, 1 和 4):" << std::endl;
delete_node(3, root);
printTree(root);
orderedList.clear();
inOrderTraversal(root, orderedList);
std::cout << "中序: ";
for (int n : orderedList) std::cout << n << " ";
std::cout << std::endl;
std::cout << "\n删除 8 (两个子节点, 7 和 9):" << std::endl;
delete_node(8, root);
printTree(root);
orderedList.clear();
inOrderTraversal(root, orderedList);
std::cout << "中序: ";
for (int n : orderedList) std::cout << n << " ";
std::cout << std::endl;
std::cout << "\n删除 5 (根节点，有两个子节点):" << std::endl;
delete_node(5, root);
printTree(root);
orderedList.clear();
inOrderTraversal(root, orderedList);
std::cout << "中序: ";
for (int n : orderedList) std::cout << n << " ";
std::cout << std::endl;
// 释放内存
freeTree(root);
return 0;
}
测试用例
依次插入：
5 3 8 2 4 7 9
得到的 BST 结构：
5
/ \
3 8
/ \ / \
2 4 7 9
可以验证：
- 中序遍历结果是
2 3 4 5 7 8 9。 find(4)成功，find(6)失败。5的前驱是4，后继是7。- 删除
8后，可以用后继9替换它的位置。
应用分类详解
二叉搜索树的本质是“动态维护有序关系”。
一、动态集合查找
典型模式： 需要反复插入元素，并判断某个元素是否存在。
识别信号： 动态加入、查找、删除，不能只排序一次。
核心建模： 每个节点保存一个集合元素，比较大小决定进入左子树或右子树。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 动态集合 | STL set 基础模型 |
插入和查找都沿树高进行 |
| 去重维护 | 在线去重 | 重复元素查到后不再插入 |
二、前驱后继查询
典型模式： 需要找到比某个数略小或略大的元素。
识别信号： 最近的较小值、最近的较大值、排名相邻。
核心建模： 搜索路径上记录可能答案，或借助父指针向上跳。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 有序邻居 | luogu-P3369 | 普通 BST 是平衡树模板的概念基础 |
| 区间边界 | lower/upper bound 模型 | 比较时不断更新候选前驱或后继 |
三、平衡树入门模型
典型模式： 需要理解 Treap、Splay、红黑树等结构为什么要旋转或随机化。
识别信号： 操作和 BST 一样，但要求最坏或期望
核心建模： BST 负责有序性，平衡策略负责控制高度。
| 应用场景 | 经典题目 | 核心思路 |
|---|---|---|
| 普通平衡树 | luogu-P3369 | BST 操作加平衡维护 |
| 文艺平衡树 | luogu-P3391 | 用隐式键维护序列顺序 |
经典例题
- luogu-P3369 【模板】普通平衡树：BST 的所有基础操作都会出现，但实际需要平衡树保证复杂度。
- luogu-P3391 【模板】文艺平衡树：理解“有序性由树结构维护”之后，再学习按排名分裂。
- leetcodecn-700 二叉搜索树中的搜索：练习最基础的查找路径。