第12讲：二叉搜索树与平衡二叉树——从无序到有序的进化之路
说实话，树结构里最常用的就是二叉搜索树（BST）。我当年刚学数据结构时，觉得链表就够用了，直到项目里需要频繁查找数据……嗯，BST 让我打开了新世界的大门。
12.1 二叉搜索树的定义
二叉搜索树，说白了就是一棵有“规矩”的二叉树：
- 左子树上所有节点的值 < 根节点的值
- 右子树上所有节点的值 > 根节点的值
- 左右子树也分别是二叉搜索树
这个性质保证了中序遍历的结果是递增序列。我在项目中经常用它来做数据排序的中间结构，比直接排序要灵活得多。
核心性质：BST 的中序遍历 = 有序序列。这是很多算法题的突破口。
12.2 查找操作
查找是 BST 最基础的操作。思路很简单：
- 从根节点开始，比较目标值与当前节点值
- 相等 → 找到了
- 目标值 < 当前值 → 去左子树找
- 目标值 > 当前值 → 去右子树找
- 走到空节点 → 没找到
// 递归查找
TreeNode* searchBST(TreeNode* root, int val) {
if (root == NULL || root->val == val) {
return root;
}
if (val < root->val) {
return searchBST(root->left, val);
} else {
return searchBST(root->right, val);
}
}
// 迭代查找（我更喜欢这个，省栈空间）
TreeNode* searchBST_iter(TreeNode* root, int val) {
while (root != NULL && root->val != val) {
if (val < root->val) {
root = root->left;
} else {
root = root->right;
}
}
return root;
}
我的习惯：能用迭代就别用递归。递归虽然代码简洁，但深度大了容易栈溢出。我曾经在一个嵌入式项目里吃过这个亏。
12.3 插入操作
插入的本质就是“找位置”。从根开始，一路比较，直到找到空位。你想想看，这个过程和查找几乎一样，只是最后一步变成了“挂节点”。
TreeNode* insertBST(TreeNode* root, int val) {
if (root == NULL) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->val = val;
newNode->left = newNode->right = NULL;
return newNode;
}
if (val < root->val) {
root->left = insertBST(root->left, val);
} else if (val > root->val) {
root->right = insertBST(root->right, val);
}
// 等于的情况，我一般选择不插入，或者根据业务决定
return root;
}
注意：插入重复值时，不同场景处理方式不同。有的项目要求去重，有的要求计数。我建议在函数注释里明确说明。
12.4 删除操作——最麻烦的一个
删除操作是 BST 里最复杂的。为什么？因为删完还要保持 BST 的性质。我当年面试时就被问过这个，写错了两次才过……
删除分三种情况：
| 情况 | 处理方式 |
|---|---|
| 叶子节点 | 直接删掉，父节点对应指针置 NULL |
| 只有一个子节点 | 用子节点替换当前节点 |
| 有两个子节点 | 找右子树的最小节点（或左子树的最大节点）替换当前节点，然后删掉那个节点 |
TreeNode* deleteBST(TreeNode* root, int val) {
if (root == NULL) return NULL;
if (val < root->val) {
root->left = deleteBST(root->left, val);
} else if (val > root->val) {
root->right = deleteBST(root->right, val);
} else {
// 找到了要删的节点
if (root->left == NULL) {
TreeNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
TreeNode* temp = root->left;
free(root);
return temp;
}
// 有两个子节点：找右子树的最小值
TreeNode* temp = findMin(root->right);
root->val = temp->val;
root->right = deleteBST(root->right, temp->val);
}
return root;
}
TreeNode* findMin(TreeNode* root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}
避坑指南：我曾经在删除有两个子节点的节点时，直接释放了替换节点，结果导致内存重复释放。正确的做法是：先复制值，再递归删除那个替换节点。
12.5 BST 的痛点——退化成链表
BST 有个致命问题：如果插入的数据是有序的（比如 1,2,3,4,5），树会退化成一条链表。查找复杂度从 O(log n) 变成 O(n)。
为什么会这样？因为 BST 没有自平衡机制。你想想看，每次插入都往右子树走，树就歪了。
我有个项目就踩过这个坑。当时用 BST 做缓存，数据是按时间顺序插入的，结果查询越来越慢。后来换成 AVL 树才解决。
12.6 平衡二叉树（AVL树）的引入
AVL 树，说白了就是一棵“会自我纠正”的 BST。它给每个节点加了一个“平衡因子”：
- 平衡因子 = 左子树高度 - 右子树高度
- 平衡因子的绝对值 ≤ 1
- 一旦超过 1，就触发旋转操作
我的理解：AVL 树就像一个有强迫症的人，每次插入或删除后都要检查一下树是不是歪了，歪了就立刻扶正。
12.7 四种旋转操作
旋转是 AVL 树的核心。一共四种情况：
| 失衡情况 | 旋转方式 | 适用场景 |
|---|---|---|
| LL（左左） | 右旋 | 左子树的左子树插入导致失衡 |
| RR（右右） | 左旋 | 右子树的右子树插入导致失衡 |
| LR（左右） | 先左旋后右旋 | 左子树的右子树插入导致失衡 |
| RL（右左） | 先右旋后左旋 | 右子树的左子树插入导致失衡 |
// 右旋（LL情况）
TreeNode* rightRotate(TreeNode* y) {
TreeNode* x = y->left;
TreeNode* T2 = x->right;
x->right = y;
y->left = T2;
// 更新高度
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x;
}
// 左旋（RR情况）
TreeNode* leftRotate(TreeNode* x) {
TreeNode* y = x->right;
TreeNode* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}
注意：旋转后一定要更新高度！我见过有人忘了更新高度，结果平衡因子算错，树越转越乱。
12.8 知识体系总览
下面这张图总结了本章的核心逻辑：
12.9 总结与建议
BST 和 AVL 树，说白了就是“无序”和“有序”之间的博弈。BST 简单但可能退化，AVL 稳定但旋转有开销。
我个人建议：
- 数据基本随机 → BST 就够用
- 数据有序或查询频繁 → 上 AVL 树
- 内存紧张 → 考虑其他平衡树（如红黑树，旋转次数更少）
最后说一句：代码写再多，不如画图理解。我每次写 AVL 旋转前，都会先在纸上画一遍节点变化。你试试看，真的管用。