二叉搜索树
概念讲解
定义
二叉搜索树(Binary Search Tree,简称 BST)是一棵二叉树,并且对树中任意一个节点都满足:
- 若左子树非空,则左子树上所有节点的值都小于该节点的值;
- 若右子树非空,则右子树上所有节点的值都大于该节点的值;
- 左、右子树本身也都是二叉搜索树。
注意第 1、2 条说的是"所有节点",不是"直接左(右)孩子"。这一点是 BST 判定题最常设的陷阱。
如果允许重复值,通常约定:重复值统一放到左子树,或统一放到右子树,并在插入时规定好。下文默认节点值互不相同。
中序遍历的有序性
对 BST 做中序遍历(左 → 根 → 右),得到的序列是严格递增的。
理由:中序遍历先访问左子树的所有节点(它们都小于根),再访问根,最后访问右子树的所有节点(它们都大于根)。对每个子树递归成立,所以整体有序。反过来,若一棵二叉树的中序遍历严格递增,它也是 BST——于是"中序遍历是否有序"可以作为 BST 的判定方法。
50
/ \
30 70
/ \ / \
20 40 60 80
中序:20 30 40 50 60 70 80
前序:50 30 20 40 70 60 80查找、插入与删除
查找
从根出发,把待查值与当前节点值比较:小则去左子树,大则去右子树,相等即命中;走到空指针说明不存在。
12345678910111213141516171819#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* find(TreeNode* root, int x) {
while (root != nullptr) {
if (x == root->val) return root;
if (x < root->val) root = root->left;
else root = root->right;
}
return nullptr;
}每比较一次就丢掉一整棵子树,比较次数等于查找路径上的节点数,复杂度 , 为树高。
插入
沿着查找路径走到空位置,在那里新建节点。若值已存在则不插入(也可按约定挂到重复一侧)。
123456TreeNode* insert(TreeNode* root, int x) {
if (root == nullptr) return new TreeNode(x);
if (x < root->val) root->left = insert(root->left, x);
else if (x > root->val) root->right = insert(root->right, x);
return root;
}插入顺序决定树形。例如依次插入 50, 30, 70, 20, 40, 60, 80,得到的正是上图;若依次插入 10, 20, 30, 40, 50,则每个新值都比前一个大,全部挂在右边,退化成一条右斜链。
删除(三种情形)
删除是最容易写错的操作,按被删节点 p 的孩子数量分三种情况:
- p 是叶子(没有孩子):直接删除,让父节点对应指针置空。
- p 只有一个孩子:用这个唯一的孩子顶替 p 的位置(把父节点指向 p 的指针改为指向该孩子)。
- p 有两个孩子:不能简单上移。做法是用 p 的中序后继(右子树中的最小值,即右子树最左节点)替换 p 的值,再在右子树中删除那个后继节点。后继节点最多只有一个右孩子,于是回到情形 1 或 2。
也可以改用中序前驱(左子树最大值)替换,效果等价。
12345678910111213141516171819202122232425262728TreeNode* findMin(TreeNode* root) {
while (root->left != nullptr) root = root->left;
return root;
}
TreeNode* erase(TreeNode* root, int x) {
if (root == nullptr) return nullptr;
if (x < root->val) {
root->left = erase(root->left, x);
} else if (x > root->val) {
root->right = erase(root->right, x);
} else {
if (root->left == nullptr) {
TreeNode* temp = root->right;
delete root;
return temp;
}
if (root->right == nullptr) {
TreeNode* temp = root->left;
delete root;
return temp;
}
TreeNode* suc = findMin(root->right);
root->val = suc->val;
root->right = erase(root->right, suc->val);
}
return root;
}删除只是"移走一个值",不会打乱其余节点的相对顺序,所以删除任意节点后,剩下的节点中序遍历序列仍然有序——只是少了一个元素。
前驱与后继
- 中序前驱:中序遍历中紧挨在某节点前面的节点。若该节点有左子树,前驱就是左子树中最大的节点(左子树最右端);否则需要沿父指针向上找。
- 中序后继:紧挨在后面的节点。若有右子树,后继就是右子树中最小的节点(右子树最左端);否则需要向上找祖先。
在上面的示例树中: 的前驱是 ,后继是 ;整个树的最小值在最左端 ,最大值在最右端 。
复杂度与退化
BST 上的查找、插入、删除都只需沿一条根到叶的路径走,复杂度为 :
| 树形 | 高度 | 单次操作 |
|---|---|---|
| 平衡(最好) | 左右 | |
| 随机插入 | 期望 | 期望 |
| 退化成链(最坏) |
退化最典型的触发方式就是按升序(或降序)插入:每次新值都挂在最右(或最左),树变成单链表,查找退化为顺序查找。为避免这种情况,实际使用中会引入平衡树(AVL 树、红黑树、Treap、Splay 等),通过旋转维持 ,从而保证最坏也是 。竞赛中常用的 std::set / std::map 底层就是平衡树,而 std::priority_queue 是堆,不是 BST。
考点分析
初赛考查方式
- 选择题: BST 的定义、中序遍历序列、前驱后继位置
- 程序阅读: 查找/插入/删除代码的功能与输出
- 分析题: 给定插入序列画树、计算查找比较次数、退化分析
常见考点
- 由插入序列画出 BST,写出前序/中序序列
- 删除节点后树的结构变化
- 判定 BST 的正确做法(区间约束或中序有序)
- 平均与最坏复杂度
例题精讲
例题 1:建树与遍历
题目: 依次插入 8, 3, 10, 1, 6, 14, 4, 7, 13,画出 BST,并写出前序与中序序列。
解答:
- 为根; 作左孩子; 作右孩子;
- 作 的左孩子; 作 的右孩子;
- 作 的右孩子;
- 作 的左孩子; 作 的右孩子;
- 且 ,作 的左孩子。
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13前序(根 → 左 → 右):8 3 1 6 4 7 10 14 13
中序(左 → 根 → 右):1 3 4 6 7 8 10 13 14(严格递增,可用它自查建树是否正确)
查找 的比较路径为 ,共 次比较。
例题 2:删除有两个孩子的节点
题目: 在上面这棵树中删除节点 ,树会变成什么样?
解答:
节点 有左右两个孩子,属于第三种情形。它的中序后继是右子树最小值: 的右子树为 (含 ),最小值为 。于是用 覆盖 的值,再在右子树中删除原来的 ( 是叶子,直接删除)。
8
/ \
4 10
/ \ \
1 6 14
\ /
7 13中序遍历仍为 1 4 6 7 8 10 13 14,只是原来的 不在了、 提前出现——序列依旧有序。
练习题
- 依次插入
5, 2, 8, 1, 3, 7, 9,写出中序序列与树高。
查看答案
中序:1 2 3 5 7 8 9。树形为根 、左子树以 为根(孩子 )、右子树以 为根(孩子 ),高度为 (按节点数计)。
- 判断 BST 时,为什么"每个节点只和它的左右孩子比较"是错的?
查看答案
BST 约束的是整棵子树,而不是直接孩子。反例:根 ,左孩子 ,右孩子 ,而 的右孩子是 。逐对比较时 、 都满足,但 位于 的左子树中却大于 ,违反 BST 定义。正确做法是给每个节点传一个合法值域 ,或在遍历时检查中序序列是否升序。
- 为什么按升序插入会让 BST 退化?如何缓解?
查看答案
升序插入时每个新值都大于此前所有值,只能一路向右挂,最终形成长度为 的右斜链,树高 ,单次操作从 退化为 。缓解办法是使用平衡树(AVL、红黑树、Treap 等)在插入后通过旋转把树高维持在 ;也可以先随机打乱插入顺序,使期望树高为 。
易错点
⚠️ 注意:
- BST 要求左子树所有节点小于根、右子树所有节点大于根,只比较父子会误判
- BST 的中序遍历严格递增,但"前序遍历有序"不能作为判定依据
- 删除有两个孩子的节点要用中序后继(右子树最小)或中序前驱替换,不能直接把孩子提上来
- 中序后继是"右子树最左",中序前驱是"左子树最右",方向不要记反
- 平衡 BST 的查找是 ,退化成链时是 ,不能说 BST 查找一定是
std::set/std::map是平衡树实现,std::priority_queue是堆,两者都不是"普通 BST"