第十四章 查找算法（二）：二叉排序树、平衡二叉树、B树与B+树

上一章我们聊了静态查找，说白了就是数据不动，我们建好索引去查。但实际项目中，数据是动态的——不停地插入、删除、查找。这时候，静态查找结构就有点力不从心了。

我记得刚入行那会儿，接手一个嵌入式数据库模块，数据量不大，但操作频繁。我一开始用了有序数组加二分查找，结果每次插入都要移动大量数据，性能惨不忍睹。后来换成二叉排序树，世界清净了。

这一章，我们就来聊聊动态查找的几种核心结构：二叉排序树、平衡二叉树、B树和B+树。它们各有各的脾气，选对了，事半功倍。

14.1 二叉排序树（BST）

二叉排序树，也叫二叉搜索树。它的定义很简单：左子树所有节点值 < 根节点值 < 右子树所有节点值，而且左右子树也分别是二叉排序树。

说白了，就是中序遍历一下，就能得到一个有序序列。

14.1.1 查找操作

查找过程很直观：从根开始，比根小往左走，比根大往右走，相等就找到了。这其实就是二分查找的链表版本。

// 二叉排序树节点定义
typedef struct BSTNode {
    int key;
    struct BSTNode *left, *right;
} BSTNode;

// 递归查找
BSTNode* BST_Search(BSTNode* root, int key) {
    if (root == NULL || root->key == key)
        return root;
    if (key < root->key)
        return BST_Search(root->left, key);
    else
        return BST_Search(root->right, key);
}

// 非递归查找（我更喜欢这个，省栈空间）
BSTNode* BST_Search_Iter(BSTNode* root, int key) {
    while (root != NULL && root->key != key) {
        if (key < root->key)
            root = root->left;
        else
            root = root->right;
    }
    return root;
}

14.1.2 插入操作

插入就是查找的延伸。先查找，没找到就在查找路径的最后一个节点上挂新节点。

BSTNode* BST_Insert(BSTNode* root, int key) {
    if (root == NULL) {
        BSTNode* newNode = (BSTNode*)malloc(sizeof(BSTNode));
        newNode->key = key;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    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;
}

14.1.3 删除操作

删除稍微麻烦点，分三种情况：

• 叶子节点：直接删掉，父节点对应指针置空。
• 只有一个孩子：用孩子顶替自己。
• 有两个孩子：用右子树的最小节点（或左子树的最大节点）替换自己，然后删除那个替换节点。

14.1.4 BST的问题

BST有个致命弱点：它可能退化成链表。比如按递增顺序插入数据，BST就变成了一条右斜树，查找复杂度从O(log n)退化到O(n)。

你想想看，如果数据是1,2,3,4,5这样插入，树就变成了一条直线。那跟链表有啥区别？

为了解决这个问题，平衡二叉树登场了。

14.2 平衡二叉树（AVL）

AVL树是BST的升级版。它要求任意节点的左右子树高度差不超过1。这个高度差叫平衡因子。

说白了，AVL树就是一棵「左右匀称」的BST。它通过旋转操作来维持平衡。

14.2.1 平衡因子

平衡因子 = 左子树高度 - 右子树高度。取值只能是-1、0、1。一旦超出这个范围，就要调整。

14.2.2 四种旋转

AVL树的调整有四种基本旋转：

失衡情况	旋转方式	说明
LL（左左）	右旋	在左孩子的左子树插入节点
RR（右右）	左旋	在右孩子的右子树插入节点
LR（左右）	先左旋后右旋	在左孩子的右子树插入节点
RL（右左）	先右旋后左旋	在右孩子的左子树插入节点

嗯，这里要注意：旋转不是凭空想象的，它有严格的步骤。我建议你画图理解，光看代码容易晕。

// AVL节点定义
typedef struct AVLNode {
    int key;
    int height;
    struct AVLNode *left, *right;
} AVLNode;

// 获取高度
int getHeight(AVLNode* node) {
    return node ? node->height : 0;
}

// 右旋
AVLNode* rightRotate(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;
    
    x->right = y;
    y->left = T2;
    
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    
    return x;
}

// 左旋（对称）
AVLNode* leftRotate(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;
    
    y->left = x;
    x->right = T2;
    
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    
    return y;
}

14.3 B树

BST和AVL都是内存中的数据结构。但实际项目中，数据量一大，内存装不下，就得用磁盘。磁盘读写比内存慢几个数量级，这时候树的高度就成了关键。

B树就是为磁盘存储设计的。它是一个多路平衡查找树，每个节点可以存多个关键字，有多个分支。

14.3.1 B树的定义

一棵m阶B树满足：

• 每个节点最多有m棵子树（m-1个关键字）。
• 根节点至少有2棵子树（除非它是叶子）。
• 除根节点外，每个非叶子节点至少有⌈m/2⌉棵子树。
• 所有叶子节点在同一层。

说白了，B树就是「矮胖」的树。同样的数据量，B树的高度远小于BST。

14.3.2 B树的查找

B树的查找分两步：先在节点内查找（可以用顺序查找或二分查找），然后根据结果进入下一层。

// B树节点定义（简化版）
#define M 5  // 5阶B树

typedef struct BTreeNode {
    int keys[M-1];          // 关键字数组
    struct BTreeNode* child[M]; // 孩子指针
    int numKeys;            // 当前关键字数量
    int isLeaf;             // 是否为叶子
} BTreeNode;

14.3.3 B树的插入与删除

插入时，先找到叶子节点。如果节点满了，就分裂成两个节点，把中间关键字上提到父节点。这个过程可能一直传到根节点。

删除更复杂，涉及合并和借位操作。我建议你理解原理即可，实际开发中很少手写B树，一般用现成的库。

14.4 B+树

B+树是B树的变种，它把数据全部放在叶子节点，非叶子节点只存索引（关键字）。

14.4.1 B+树的特点

• 非叶子节点：只存关键字，不存数据。用于索引。
• 叶子节点：存所有关键字和对应的数据指针。
• 叶子节点之间：用链表连接，方便范围查询。

你想想看，B+树比B树好在哪？

第一，非叶子节点不存数据，所以一个节点能存更多关键字，树更矮。第二，叶子节点用链表串起来，范围查询（比如查所有大于100的数据）只需要找到起点，然后顺着链表走就行，不用回溯。

14.4.2 B+树 vs B树

对比项	B树	B+树
数据存储位置	所有节点都存数据	只在叶子节点存数据
叶子节点结构	无链表连接	有链表连接
范围查询	需要中序遍历	链表遍历即可
节点存储量	较少（因为存数据）	更多（只存索引）
典型应用	文件系统	数据库索引

14.5 知识体系总览

下面这张图总结了四种查找树的关系和适用场景：

14.6 如何选择

在实际项目中，选哪种树取决于你的场景：

• 数据全在内存，且随机插入：用AVL树。虽然维护成本高，但查找稳定。
• 数据全在内存，但插入有序：千万别用普通BST，会退化成链表。用AVL或红黑树。
• 数据在磁盘上，需要频繁范围查询：B+树是首选。数据库索引几乎都用它。
• 数据在磁盘上，但主要是点查询：B树也可以，但B+树更通用。

好了，这一章的内容就到这里。下一章我们会继续深入，聊聊哈希查找——另一种完全不同的查找思路。

---

公众号:蓝海资料掘金营，微信deep3321