14. 查找进阶：二叉排序树（BST）、平衡二叉树（AVL）、B树与B+树
各位同学，今天我们来啃一块硬骨头——查找结构的进阶内容。说实话，这块内容我当年学的时候也绕了好一阵子。但等你真正搞懂了，你会发现这些树结构的设计思路，简直是天才级别的。
我们先从最基础的开始，一步步往上走。
14.1 二叉排序树（BST）—— 最朴素的二分思想
二叉排序树，说白了就是把二分查找的思想搬到链式结构上。它的定义很简单：左子树所有节点都小于根节点，右子树所有节点都大于根节点。左右子树本身也是BST。
我刚开始做嵌入式项目时，经常用BST来管理传感器数据。比如温度传感器的ID排序，插入和查找都很方便。但后来发现一个问题——BST的性能完全取决于树的形状。
核心操作的时间复杂度：
- 最好情况（平衡树）：O(log n)
- 最坏情况（退化成链表）：O(n)
为什么会退化？你想想看，如果插入的数据是递增的，比如1, 2, 3, 4, 5...那BST就变成了一条右斜线，跟链表没区别。我在一个项目中就踩过这个坑——数据量大了以后，查找速度从微秒级掉到了毫秒级。
来看一个简单的BST插入实现：
typedef struct BSTNode {
int key;
struct BSTNode *left, *right;
} BSTNode;
BSTNode* bst_insert(BSTNode *root, int key) {
if (root == NULL) {
BSTNode *node = (BSTNode*)malloc(sizeof(BSTNode));
node->key = key;
node->left = node->right = NULL;
return node;
}
if (key < root->key)
root->left = bst_insert(root->left, key);
else if (key > root->key)
root->right = bst_insert(root->right, key);
// 相等则不插入（视需求而定）
return root;
}小技巧：在实际项目中，如果数据量不大（比如几百个），BST完全够用。但一旦上了万级，我建议你直接上平衡树。
14.2 平衡二叉树（AVL）—— 让树永远保持匀称
AVL树解决了BST的退化问题。它的核心思想是：每个节点的左右子树高度差不超过1。一旦超过，就通过旋转来调整。
我记得第一次手写AVL旋转时，左旋右旋搞混了好几次。后来我总结了一个口诀："左左右旋，右右左旋，左右先左后右，右左先右后左"。嗯，虽然有点绕，但确实管用。
AVL的四种旋转情况：
| 失衡情况 | 旋转方式 | 示例场景 |
|---|---|---|
| LL（左左） | 右旋 | 在左子树的左孩子插入 |
| RR（右右） | 左旋 | 在右子树的右孩子插入 |
| LR（左右） | 先左旋后右旋 | 在左子树的右孩子插入 |
| RL（右左） | 先右旋后左旋 | 在右子树的左孩子插入 |
我曾经在一个实时系统中用AVL树管理任务优先级队列。数据量大概10万级，查找和插入都能稳定在O(log n)。但代价是什么？每次插入和删除都可能触发多次旋转，这在写操作频繁的场景下开销不小。
注意：AVL树对平衡要求非常严格。如果你的应用场景是写少读多，AVL是绝佳选择。但如果写操作很频繁，我建议你考虑红黑树（虽然本章不展开，但值得了解）。
14.3 B树与B+树—— 磁盘世界的王者
好，接下来我们聊聊B树和B+树。这两个东西，说白了就是为磁盘IO量身定做的。
你想想看，内存访问是纳秒级的，磁盘访问是毫秒级的。差了百万倍。所以磁盘上的数据结构，核心目标只有一个：减少磁盘IO次数。
B树和B+树通过一个巧妙的设计来实现这个目标：每个节点存储多个关键字，拥有多个分支。这样树的高度就大大降低了。一个3阶B树，100万数据只需要3-4层就能搞定。
来看B树的核心定义：
- 每个节点最多有m个孩子（m称为阶数）
- 除根节点外，每个节点至少有⌈m/2⌉个孩子
- 所有叶子节点在同一层
B+树是B树的变种，区别在于：
| 特性 | B树 | B+树 |
|---|---|---|
| 数据存储 | 所有节点都存数据 | 只有叶子节点存数据 |
| 内部节点 | 存关键字+数据指针 | 只存关键字（索引） |
| 叶子节点 | 无链表连接 | 有链表连接（范围查询利器） |
| 范围查询 | 需要中序遍历 | 直接走叶子链表 |
我个人习惯在数据库索引场景中首选B+树。为什么？因为内部节点不存数据，可以放更多关键字，树更矮，IO更少。而且叶子节点的链表结构，让范围查询变得极其高效。
实际项目经验：我曾经优化过一个嵌入式数据库的查询模块。原来用的是B树，范围查询要来回跳转节点。改成B+树后，范围查询速度提升了3倍以上。嗯，这就是数据结构的魅力。
下面我用一张图来总结这四种查找结构的核心逻辑：
最后说一句，这些树结构在实际项目中怎么选？我个人的经验是：
- 数据量 < 1000，且写操作频繁：BST就够了，别折腾
- 数据量 1000~10万，读多写少：上AVL，性能稳定
- 数据量 > 10万，且涉及磁盘IO：B+树，没得选
- 嵌入式场景，内存受限：B树可能更合适，因为B+树需要额外的叶子链表
避坑指南：我曾经在一个项目中，为了追求"完美"用了AVL树，结果写操作频繁导致频繁旋转，CPU占用率飙升。后来换成红黑树（允许一定程度的不平衡），问题就解决了。所以记住：没有最好的数据结构，只有最合适的。
好了，这一章的内容就到这里。这些树结构是查找算法的核心，也是很多高级数据结构的基石。搞懂了它们，你再看数据库索引、文件系统、内存管理，都会有一种"原来如此"的感觉。