在数据结构中，树结构是高效组织和检索数据的重要方式，常见的哈夫曼树、红黑树、B 树等在压缩、数据库、搜索引擎等领域应用广泛。本文将系统梳理核心树结构的知识点，助力复习回顾。
一、哈夫曼树与哈夫曼编码
1. 哈夫曼树（最优二叉树）
（1）定义
哈夫曼树是带权路径长度（WPL）最短的二叉树，其中 “带权路径长度” 指树中所有叶子节点的 “权值” 与 “该节点到根节点的路径长度” 的乘积之和（路径长度为节点数减 1）。
（2）构造步骤（哈夫曼算法）
- 初始化：将所有给定的权值作为独立的 “单节点二叉树”，组成森林；
- 选最小：从森林中选出权值最小的两棵树，作为新二叉树的左、右子树（左树权值可小于等于右树）；
- 新树权值：新二叉树的根节点权值 = 左子树权值 + 右子树权值；
- 重复操作：将新二叉树加入森林，重复步骤 2-3，直到森林中只剩一棵树，即为哈夫曼树。
（3）特点
- 哈夫曼树中没有度为 1 的节点（所有非叶子节点的度均为 2）；
- 若给定 n 个权值，构造的哈夫曼树共有2n-1个节点（n 个叶子节点，n-1 个非叶子节点）。
2. 哈夫曼编码
（1）原理
利用哈夫曼树的 “路径长度差异”，为出现频率高的字符分配短编码，频率低的字符分配长编码，且保证编码为 “前缀编码”（任一编码不是其他编码的前缀，避免解码歧义）。
（2）编码步骤
- 统计字符频率：将每个字符的出现频率作为 “权值”；
- 构建哈夫曼树：以字符为叶子节点，频率为权值，按哈夫曼算法构造树；
- 分配编码：约定 “左分支为 0，右分支为 1”，从根节点到每个叶子节点的路径上的 0/1 序列，即为该字符的哈夫曼编码。
（3）示例
若字符频率为：A (5)、B (3)、C (1)、D (1)，构造的哈夫曼树及编码如下：
- 哈夫曼树：根节点权值 = 10，左子树权值 = 5（A），右子树权值 = 5（左 3=B，右 2=（C+D））；
- 编码：A (0)、B (10)、C (110)、D (111)，满足前缀编码，且总编码长度最短。
二、B 树、B + 树、红黑树：平衡树的联系与区别
B 树、B + 树、红黑树均属于平衡树（通过特定规则维持树的高度平衡，确保查找、插入、删除的时间复杂度为 O (logn)），但适用场景差异显著，核心联系与区别如下：
1. 三者的核心联系
- 均为 “平衡查找树”：通过调整结构避免树退化为链表，保证高效的查找效率；
- 均支持动态插入 / 删除：插入或删除节点后，会通过旋转、分裂、合并等操作恢复平衡；
- 核心目标一致：减少树的高度，降低 IO 次数（尤其 B 树 / B + 树针对磁盘存储优化）。
2. 三者的关键区别
对比维度 |
B 树 |
B + 树 |
红黑树 |
结构特点 |
非叶子节点存储 “关键字 + 数据指针”；叶子节点不相连 |
非叶子节点仅存 “关键字 + 索引指针”，数据仅存于叶子节点；叶子节点按顺序相连（形成链表） |
二叉树，节点分为红 / 黑两种颜色；满足 “根黑、叶黑、红节点子节点必黑、任意节点到叶节点的黑路径长度相等” |
查找方式 |
找到关键字所在节点即可返回数据，支持 “随机查找” |
需找到叶子节点才能获取数据；支持 “随机查找” 和 “顺序查找”（利用叶子节点链表） |
二叉查找树逻辑，左子树关键字 < 根 < 右子树，按路径查找 |
适用场景 |
少量数据的内存查找（如早期数据库索引） |
磁盘存储的大规模数据（如 MySQL InnoDB 引擎的聚簇索引） |
内存中的高效查找 / 插入（如 C++ STL 的 map、Linux 内核的进程调度） |
IO 效率 |
非叶子节点存数据，单次 IO 获取信息少 |
非叶子节点仅存索引，单次 IO 可加载更多关键字，IO 次数更少 |
内存操作，无 IO 开销，依赖 CPU 缓存 |
插入删除 |
需分裂 / 合并节点，操作较复杂 |
分裂 / 合并逻辑与 B 树类似，但数据仅在叶子节点，调整更简单 |
通过 “旋转” 和 “变色” 恢复平衡，操作更轻量 |
三、常见树结构总结
将完全二叉树、满二叉树、平衡二叉树等核心知识点整理如下：
1. 完全二叉树
- 定义：除最后一层外，每一层的节点数均为最大值；最后一层的节点从左到右连续排列，缺失的节点仅在右侧。
- 特点：
- 可通过 “数组” 高效存储（父节点索引 i，左子节点 2i+1，右子节点 2i+2）；
- 叶子节点集中在最后两层，且最后一层的叶子节点靠左；
- 若树的高度为 h（根节点为 h=1），则节点数范围为2^(h-1) ≤ n ≤ 2^h - 1。
- 应用：堆排序（大根堆、小根堆均为完全二叉树）。
2. 满二叉树
- 定义：每一层的节点数均为最大值（即最后一层无缺失节点），是完全二叉树的特殊情况。
- 特点：
- 若高度为 h，节点总数为2^h - 1；
- 叶子节点数 = 非叶子节点数 + 1（叶子节点全在最后一层）。
- 注意：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。
3. 平衡二叉树（AVL 树）
- 定义：左右子树的高度差（平衡因子）的绝对值≤1，且左右子树均为平衡二叉树（平衡因子 = 左子树高度 - 右子树高度）。
- 特点：
- 高度严格平衡，查找效率稳定（时间复杂度 O (logn)）；
- 插入 / 删除后需通过 “左旋”“右旋”“左右旋”“右左旋” 调整平衡；
- 平衡条件严格，频繁插入 / 删除时调整成本高。
- 应用：早期需要严格平衡的查找场景（如老版数据库索引），现多被红黑树替代。
4. 红黑树
- 定义：满足以下 5 条规则的二叉查找树：
- 根节点为黑色；
- 所有叶子节点（NIL 节点，空节点）为黑色；
- 红色节点的两个子节点均为黑色（无连续红节点）；
- 任意节点到其所有叶子节点的 “黑色路径长度” 相等；
- 新插入节点默认为红色。
- 特点：
- 平衡条件宽松（允许左右子树高度差≤2 倍），调整成本低；
- 查找、插入、删除的时间复杂度均为 O (logn)，适合动态数据；
- 无需存储高度信息，仅需 1 位标记颜色，空间开销小。
- 应用：C++ STL 的 map/set、Java 的 TreeMap、Linux 内核的 epoll 事件表。
5. 哈夫曼树
- 核心：带权路径长度最短的二叉树，无度为 1 的节点；
- 应用：哈夫曼编码（文件压缩）、最优判定树（如霍夫曼判决）。
6. B 树
- 定义：m 阶 B 树（m≥2）是满足以下规则的多叉树：
- 根节点至少有 2 个子节点（除非树仅含根）；
- 每个非根节点至少有⌈m/2⌉个子节点，最多有 m 个子节点；
- 每个节点的关键字个数 = 子节点个数 - 1，且关键字按升序排列；
- 所有叶子节点在同一层，无数据（或数据在非叶子节点）。
- 特点：多叉结构，降低树高，减少磁盘 IO；
- 应用：Oracle 数据库的索引、早期文件系统（如 Ext3）。
四、复习
- 对比记忆：重点区分 B 树与 B + 树的存储差异、红黑树与 AVL 树的平衡策略；
- 结合应用场景：理解 “为什么 B + 树适合数据库”“为什么红黑树适合内存”，避免死记硬背；
- 动手实践：尝试手动构造哈夫曼树、模拟红黑树的插入调整，加深对原理的理解；
- 总结规律：所有平衡树的核心都是 “通过规则控制树高”，不同树的规则差异决定了其适用场景。