嵌入式开发之路

第04章 树：从二叉树到 AVL 与 B 树

Properties2
description树的实现与遍历、二叉搜索树的增删查、AVL 旋转维持平衡、B 树省磁盘，一棵树的家族图谱。
tags数据结构精讲

13分钟阅读

这一篇在干嘛？

第 3 章的表只能线性找（），要”查找快 + 插入快”两全，就得把元素按规则挂到树上。本章从树的定义讲起，重点拆解二叉搜索树（BST）的全部操作，再用 AVL 树解决”输入有序时 BST 退化成链表”的致命缺陷，最后带出伸展树和数据库底层的 B 树。

4.1 树的定义与实现

递归定义：树是节点的集合，要么为空，要么有一个根（root）加 0 个或多个非空子树 ，每棵子树的根由一条边连向大根。除了根，每个节点都有一个父节点。

图：一般的树

图：树的要素——根、叶、边、深度

基本词汇：叶（无子节点）、深度（到根的路径长，根为 0）、高（最深叶子的深度）。 个节点的树恰有 条边。

实现：每个节点存”第一个孩子 + 下一个兄弟”两个指针（first-child / next-sibling）——任意叉的树都能用两个指针搞定：

struct TreeNode {
    Object element;
    TreeNode *firstChild;    // 第一个孩子
    TreeNode *nextSibling;   // 下一个兄弟
};

4.2 树的遍历：UNIX 目录是最好的例子

图：UNIX 目录就是一棵树

先序遍历（先处理节点再进子树）：目录列表按名字打印——先打印本目录名，再递归打印每个子目录。

后序遍历（先走完子树再处理节点）：计算目录总大小——必须先把所有子目录的大小加完，才能加上本目录自身文件的大小：

图：后序遍历计算目录大小——数字是文件大小，目录大小由孩子汇总

白话：先序 = “见面先报名字”，后序 = “事情办完再汇报”。哪个顺序对，取决于”本节点的信息是否依赖子节点的结果”。

4.3 二叉树与表达式树

二叉树：每个节点至多两个孩子的树。满的 节点二叉树每个节点都有 0 或 2 个孩子；性质：叶节点数 = 度为 2 的节点数 + 1。

图：一般的二叉树

表达式树：叶子是操作数，内部节点是运算符。(a+b)c + (de+f)*g 的表达式树：

图：表达式树——中序读出中缀，后序读出后缀

白话：第 3 章的后缀表达式，其实就是表达式树的后序遍历；中缀（带足括号）是中序遍历。对表达式树做一次后序遍历（子树结果先算好，再到根做运算）就是求值算法本身。

4.4 二叉搜索树（BST）：查找的排序二叉化

性质：对树中每个节点 X，左子树所有节点值 < X，右子树所有节点值 > X。

图：只有左边的是搜索树——右图中 19 在 17 的左子树里，违反性质

contains：顺着性质走

bool contains(const Comparable &x, BinaryNode *t) const {
    if (t == nullptr)
        return false;                      // 走到空：不存在
    else if (x < t->element)
        return contains(x, t->left);       // 小了往左
    else if (t->element < x)
        return contains(x, t->right);      // 大了往右
    else
        return true;                       // 相等：找到
}

白话：每次比较排除一整棵子树。查找代价 = 根到目标路径的长度，最坏 （退化），平均 。

findMin / findMax：无脑走到底

最小值永远在最左（一路 left），最大值永远在最右（一路 right）——用循环而不是递归写， 平均。

insert：按 contains 的路走，空位即家

void insert(const Comparable &x, BinaryNode *&t) {   // 注意是指针的引用！
    if (t == nullptr)
        t = new BinaryNode{x, nullptr, nullptr};     // 空位：挂上
    else if (x < t->element)
        insert(x, t->left);
    else if (t->element < x)
        insert(x, t->right);
    else
        ;  // 重复元素：本版选择忽略（也可挂计数器）
}

白话：BinaryNode *&t 是”指针的引用”，递归深入时修改 t->left 就等于修改父节点里存的那个指针——新节点天然挂在正确的父节点下，不用回传父指针。这是 C++ 引用参数的神来之笔。

图：插入 5——沿着 contains 的路径走到空位

remove：分三种情形

  1. 叶节点：直接删，父指针置空。
  2. 只有一个孩子：父亲”过继”——把父节点指向自己的指针改指唯一的孩子。

图：删除只有一个孩子的节点 4——父节点直接改指其孩子

  1. 有两个孩子：不能简单摘除。用右子树的最小值（or 左子树最大值）顶替本节点，再在右子树里删掉那个最小值（它必然是叶或只有一个右孩子，退化为情形 1/2）。

图：删除有两个孩子的节点 2——用右子树最小值 3 顶替

白话：两个孩子的节点删除像”公司换 CEO”——找一个既比左派服众、又比右派好说话的人（右子树最小者）接位，然后原位那个人就可以放心离开。

平均情形分析：为什么期望 O(log N)

坏消息：把 顺序插入，BST 退化成一条链（深度 ），操作全 ：

图：坏二叉树——顺序插入让 BST 退化成链表

好消息：随机插入顺序下，树的平均深度约为 （平均深度 ≈ ）。

图：随机生成的二叉搜索树——形状相当平衡

白话：BST 的命运完全交给输入顺序。数据库没法赌输入随机，所以需要”自我修理”的树——AVL。

4.5 AVL 树：带平衡条款的 BST

AVL 条款：每个节点的左右子树高度差至多 1。可以证明高度至多 ，查找仍是 保证。

图：高度 9 的最小 AVL 树——最少需要多少节点的直观感受

插入破坏平衡时，找到最深的不平衡节点，按四种情形旋转修复。关键观察：只需处理”插入路径上第一个失衡点”，其上的部分自动恢复平衡。

单旋转（情形 1/4：外侧插入）

左-左 或 右-右 插入。以右-右为例：把失衡点 k₁ 的左孩子 k₂ 转上来当根：

图：单旋转——右子树过高，把 k₂ 提上来

图：单旋转的通用形态

白话：单旋转像”提携”——中间那棵子树 X 换爹：原本属于 k₁，现在归 k₂。它同时满足两边的排序性质（X 的值介于两者之间）。

双旋转（情形 2/3：内侧插入）

左-右 或 右-左 插入时单旋转救不了：

图：单旋转对情形 2 无效——问题节点在"内侧"

图：双旋转——先把 k₂ 左旋，再把 k₃ 右旋，孙子成根

图：右-左双旋转修复情形 3

白话：孙子上位分两步——先让孙子把自己爹（内侧那棵）顶掉，再顶掉爷爷。也可以理解为”两次单旋转”。判断用哪种：看插入发生在失衡点的”外侧”还是”内侧”，等价于看失衡点、其较高孩子、插入方向是否三点共线。

高度信息怎么存

每个节点存高度（一个字节足够）。插入后沿回溯路径更新高度、发现失衡即旋转；一次插入至多一次（双）旋转，。

4.6 伸展树：不存高度的自适应树

伸展树（splay tree）换了个思路：不维护平衡条款，而是每次访问（查找/插入/删除）后把目标节点旋转到根（splaying）。常用”之字形（zig-zag）双旋 + 一字形（zig-zig）先旋父再旋祖”的组合：

图：zig-zag——与 AVL 双旋转同构

图：zig-zig——先旋父亲再旋祖父

白话：伸展树押注”热点数据会被反复访问”——被访问过的元素被搬到根附近，下次访问更快。单次操作最坏 ，但摊还意义下每次 （第 11 章的势能法会严格证明）。优点是不用存高度、代码少；缺点是”别碰我的指针”——访问过程会改树结构，不能并发。

4.7 B 树：为磁盘而生的多叉平衡树

内存访问快、磁盘 I/O 慢——数据库索引的瓶颈不是比较次数，是读盘次数。B 树让每个节点存很多关键字（M 阶 B 树：每节点至多 M 棵子树、至少 ⌈M/2⌉ 棵），树高骤降：

图：5 叉树装 31 个节点只需 3 层

图：5 阶 B 树——所有叶子同层

插入导致节点满时分裂上推（中间关键字升到父亲），所有叶子永远同层，所以也是平衡的。

图：插入 55 引发分裂

白话：一个节点对应磁盘的一个块（比如 4KB），一次 I/O 整块读入。4 阶 B 树装 100 万关键字也就约 10 层 ≈ 10 次读盘；换成二叉树要 20 层。层数减半，I/O 减半——这是所有数据库索引的底层逻辑。

4.8 STL 的 set 与 map

  • set：数学集合，insert、erase、find（返回迭代器）、contains，底层是平衡 BST（红黑树，见第 12 章），各操作 。
  • map：键值对（关联数组），m[key] 直接索引——key 不存在时会自动插入默认值（这个坑见下）。遍历时得到 pair<const Key, Value>。
map<string, double> salaries;
salaries["Pat"] = 75000.00;            // 插入/更新
cout << salaries["Pat"];               // 查询
auto itr = salaries.find("Jan");
if (itr != salaries.end())
    cout << itr->second;

常见坑

① map[key] 在 key 不存在时顺手插入默认值——只读判断请用 find 或 count，别用 []，否则容器越查越大。② BST 的 remove 双孩子情形：选右子树最小值或左子树最大值顶替，选别的节点会破坏排序性质。③ AVL 旋转判断错”外侧/内侧”：外侧（一条直线）单旋转、内侧（一个折角）双旋转——画图确认三点是否共线。

通关标准

学完本篇你应该能做到：① 手写 BST 的 contains/insert/remove（含双孩子删除）；② 讲清单旋转与双旋转分别修复哪两种失衡、如何判断；③ 解释为什么顺序输入会让 BST 退化、AVL/B 树如何避免；④ 说清 B 树为什么是数据库索引发明；⑤ 正确使用 STL 的 set/map 并避开 [] 的隐式插入坑。

关系图谱

反向链接