二叉排序树与平衡二叉树
含AI生成内容
二叉排序树与平衡二叉树
二叉排序树（BST）
定义
二叉排序树（Binary Search Tree, BST），也称二叉搜索树、二叉查找树，是一棵空树或满足以下性质的二叉树：
- 左子树上所有结点的关键字均小于根结点的关键字
- 右子树上所有结点的关键字均大于根结点的关键字
- 左右子树本身也是二叉排序树
核心性质：对 BST 进行中序遍历，得到的是递增有序序列。这一性质是 BST 所有应用的基础。
BST 的基本操作
查找
从根开始比较，目标值小于当前结点则向左、大于则向右，直到命中或到达空结点。
BSTNode *BSTSearch(BiTree T, int key) { while (T != NULL && key != T->data) { if (key < T->data) T = T->lchild; else T = T->rchild; } return T;}ASL（平均查找长度）分析：
- 最好情况：平衡的 BST，ASL = O(log n)
- 最坏情况：退化为单支树（插入序列有序时），ASL = O(n)
- 平均情况：随机插入，ASL = O(log n)
插入
插入总是发生在叶子结点位置：
bool BSTInsert(BiTree &T, int key) { if (T == NULL) { T = (BiTree)malloc(sizeof(BSTNode)); T->data = key; T->lchild = T->rchild = NULL; return true; } if (key == T->data) return false; // 已存在 else if (key < T->data) return BSTInsert(T->lchild, key); else return BSTInsert(T->rchild, key);}删除（三种情况）
| 被删结点类型 | 删除方法 | 注意点 |
|---|---|---|
| 叶子结点 | 直接删除 | 修改双亲指针为 NULL |
| 只有左或右子树 | 用子树的根替换被删结点 | 相当于绕过被删结点 |
| 左右子树均非空 | 用中序后继（或前驱）替换 | 转换为删除叶子或单孩子结点 |
关键理解：删除有两个孩子的结点时，用中序后继替换被删结点。中序后继是右子树中最左下的结点，它一定是叶子或最多只有右孩子。这样就把”删除双子结点”转化为”删除叶子或单孩子结点”。
BST 的退化问题
BST 的性能高度依赖于输入顺序。如果依次插入有序序列（如 1, 2, 3, …, n），BST 会退化为单支树，查找复杂度退化为 O(n)。解决退化的两种方法：
- 平衡二叉树（AVL）：强制保持左右子树高度差不超过 1
- 红黑树：通过颜色约束保持弱平衡
平衡二叉树（AVL）
定义
平衡二叉树（Balanced Binary Tree），又称 AVL 树（由 Adelson-Velskii 和 Landis 提出），是任意结点的平衡因子绝对值不超过 1 的二叉排序树。
平衡因子（Balance Factor, BF）= 左子树高度 - 右子树高度，取值范围：{-1, 0, 1}。
平衡旋转（核心考点）
当插入或删除导致某结点 |BF| > 1 时，需要进行旋转调整。四种旋转类型：
| 旋转类型 | 失衡情况 | 操作 | 口诀 |
|---|---|---|---|
| LL | 在左孩子的左子树插入 | 右单旋 | 左左→右旋 |
| RR | 在右孩子的右子树插入 | 左单旋 | 右右→左旋 |
| LR | 在左孩子的右子树插入 | 先左旋后右旋 | 左右→双旋 |
| RL | 在右孩子的左子树插入 | 先右旋后左旋 | 右左→双旋 |
LL 右单旋
A (BF=2) B / 右旋 / \ B T3 → T1 A / \ / \T1 T2 T2 T3LR 先左后右
A (BF=2) A C / 左旋 / / \ B T3 → C T3 → B A / \ / \T1 C B T2 / \ / T2 T1 T1RR 左单旋（对称于 LL）
A (BF=-2) B \ 左旋 / \ T1 B → A C / \ / \ T2 C T1 T2RL 先右后左（对称于 LR）
旋转的代码实现要点：需要修改三个结点的指针——失衡结点、孩子结点、子树结点。注意子树（如 T2）在旋转后归属的新的双亲。
插入 vs 删除的旋转次数（重要考点）
| 操作 | 旋转次数 | 说明 |
|---|---|---|
| 插入 | 至多 1 次（O(1)次旋转） | 插入后从插入点向上回溯，找到第一个失衡结点调整后，整棵树恢复平衡 |
| 删除 | 可能多次（O(log n)次旋转） | 删除后调整了失衡结点，可能导致上一层也失衡，需要继续向上回溯调整 |
这是 AVL 树与 红黑树 对比时的关键区别之一：AVL 删除需要 O(log n) 次旋转，而红黑树删除最多 3 次旋转。
AVL 树的高度与最少结点数
设 N(h) 表示高度为 h 的 AVL 树的最少结点数：
N(1) = 1N(2) = 2N(h) = N(h-1) + N(h-2) + 1 (h ≥ 3)这个递推关系类似斐波那契数列。由此可推导：高度为 h 的 AVL 树最多有 2^h - 1 个结点（满二叉树），最少约 1.618^h 个结点。
结论：n 个结点的 AVL 树高度为 O(log n)，查找、插入、删除的时间复杂度均为 O(log n)。
AVL 树与 BST 的对比
| 对比项 | BST（一般情况） | AVL 树 |
|---|---|---|
| 查找最坏时间复杂度 | O(n) | O(log n) |
| 查找平均时间复杂度 | O(log n) | O(log n) |
| 插入最坏时间复杂度 | O(n) | O(log n) |
| 删除最坏时间复杂度 | O(n) | O(log n) |
| 平衡性 | 不保证 | 严格平衡 |
| 实现复杂度 | 简单 | 中等 |
AVL 与 红黑树 的详细对比见红黑树页面。
关联页面
- 树与二叉树基础 — 二叉树定义与性质
- 二叉树的遍历与线索化 — BST 的中序递增序列性质
- 红黑树 — AVL 的”表兄弟”，性能对比
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
评论区
