Appearance
二叉排序树（BST）
兼得查找与插入的优势
数组查找快（O(1) 随机访问）但插入慢（O(n) 移动元素），链表插入快（O(1)）但查找慢（O(n)）。BST 试图兼得两者的优点：平均情况下查找和插入都是 O(log n)——前提是树不会退化成链表。
BST 是 408 考研查找章节的核心内容，也是理解 AVL 树、红黑树、B 树等高级结构的基础。
核心思想
二叉排序树是一棵二叉树，它满足以下性质（递归定义）：
- 左子树上所有结点的值 < 根结点的值
- 右子树上所有结点的值 > 根结点的值
- 左、右子树本身也分别是二叉排序树
由此可得一个重要推论：对 BST 进行中序遍历，可以得到一个递增的有序序列。
⚠️ 易错：BST 的中序遍历一定是递增序列。这意味着：给定一棵 BST，对它做中序遍历可以得到排序结果——这是 408 判断题的常考点。
结点定义：
c
typedef struct BSTNode {
int key;
struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;交互可视化
通过下方的交互动画，你可以逐步观察二叉排序树的执行过程：
操作详解
查找操作
从根结点出发，将目标值 key 与当前结点比较：
- 若 key == 当前结点值，查找成功
- 若 key < 当前结点值，在左子树中继续查找
- 若 key > 当前结点值，在右子树中继续查找
- 若走到空结点，查找失败
c
BSTNode *BST_Search(BSTree T, int key) {
while (T != NULL && key != T->key) {
if (key < T->key)
T = T->lchild;
else
T = T->rchild;
}
return T;
}查找过程实质上是走了一条从根到目标结点的路径，比较次数 = 路径上的结点数 = 结点所在层次。
插入操作
BST 的插入基于查找：先查找 key 是否已存在，若不存在，则在查找失败的位置插入新结点。
关键步骤：
- 若树为空，创建新结点作为根
- 若 key < 当前结点值，递归插入左子树
- 若 key > 当前结点值，递归插入右子树
- 若 key == 当前结点值，不插入（BST 中不允许重复关键字）
c
int BST_Insert(BSTree *T, int key) {
if (*T == NULL) {
*T = (BSTree)malloc(sizeof(BSTNode));
(*T)->key = key;
(*T)->lchild = (*T)->rchild = NULL;
return 1; // 插入成功
}
if (key == (*T)->key)
return 0; // 已存在，插入失败
else if (key < (*T)->key)
return BST_Insert(&((*T)->lchild), key);
else
return BST_Insert(&((*T)->rchild), key);
}插入的新结点一定是叶子结点，这是 BST 插入的重要特征。
不同的插入顺序会构造出不同形态的 BST。例如，序列 {50, 30, 70, 20, 40} 和 {20, 30, 40, 50, 70} 包含相同元素，但前者构造出较平衡的树，后者退化为单支树（类似链表）。
删除操作
BST 的删除较复杂，需要分三种情况讨论（设待删除结点为 z）：
情况一：z 是叶子结点 直接删除，将其父结点对应指针置空。
情况二：z 只有一棵子树 让 z 的子树替代 z 的位置，即用 z 的子结点顶替 z。
情况三：z 有两棵子树 ⭐ 找到 z 的中序后继（即 z 的右子树中最左下的结点 s），用 s 的值替换 z 的值，然后转而删除 s（s 一定没有左子树，转化为情况一或情况二）。
⚠️ 易错：BST 删除度为 2 的结点时，用中序前驱（左子树最大值）或中序后继（右子树最小值）替换均可。但两种方式得到的 BST 不同。408 真题一般会指定用哪种，如果没指定则默认用中序前驱。
c
void BST_Delete(BSTree *T, int key) {
if (*T == NULL) return;
if (key < (*T)->key) {
BST_Delete(&((*T)->lchild), key);
} else if (key > (*T)->key) {
BST_Delete(&((*T)->rchild), key);
} else { // 找到待删除结点
if ((*T)->lchild == NULL) {
// 情况一、二：无左子树（含叶子结点）
BSTNode *temp = *T;
*T = (*T)->rchild;
free(temp);
} else if ((*T)->rchild == NULL) {
// 情况二：无右子树
BSTNode *temp = *T;
*T = (*T)->lchild;
free(temp);
} else {
// 情况三：左右子树都存在，找中序后继
BSTNode *s = (*T)->rchild;
while (s->lchild != NULL)
s = s->lchild;
(*T)->key = s->key;
BST_Delete(&((*T)->rchild), s->key);
}
}
}复杂度分析
| 操作 | 最好时间复杂度 | 最坏时间复杂度 | 说明 |
|---|---|---|---|
| 查找 | O(log₂n) | O(n) | 取决于树的高度 |
| 插入 | O(log₂n) | O(n) | 先查找再插入，查找决定时间 |
| 删除 | O(log₂n) | O(n) | 先查找再删除，查找决定时间 |
查找长度分析（ASL）：
- 最好情况：BST 接近完全二叉树，树高 h ≈ log₂n，ASL ≈ O(log₂n)
- 最坏情况：BST 退化为单支树（输入序列有序时），树高 h = n，ASL ≈ (n+1)/2 = O(n)，与顺序查找相同
| 树形 | ASL | 等价于 |
|---|---|---|
| 平衡 BST | O(log₂n) | 折半查找判定树 |
| 单支树 | O(n) | 顺序查找 |
空间复杂度：O(1)，查找、插入、删除操作只需常数级辅助空间（递归实现需 O(h) 栈空间）。
考研高频考点
- ⭐ BST 的性质：中序遍历得到递增序列（选择题/判断题高频）
- ⭐ 根据插入序列构造 BST（画图题必考）
- ⭐ 删除操作三种情况的处理方式，特别是有两棵子树时用中序后继替换（大题高频）
- ⭐ ASL 的计算：给定 BST 求查找成功/失败的 ASL（计算题高频）
- ⭐ 不同插入顺序 → 不同树形 → 不同查找效率（概念题）
- 相同关键字集合，不同插入顺序得到不同 BST，但中序遍历结果相同
- BST 与折半查找的对比：BST 是动态结构，折半查找依赖静态有序表
相关知识
- BST 在最坏情况下退化为链表，为此引入了平衡二叉树（AVL）和红黑树两种自平衡方案
- BST 的查找过程与折半查找的判定树完全对应——折半查找的判定树就是一棵平衡 BST
- BST 是 B 树的特例（2 阶 B 树等价于 BST），理解 BST 的操作是学习 B 树的基础