高级树结构、编码原理与存储体系

摘要：本次课程从平衡二叉树的旋转机制出发，深入讲解了红黑树（2-3-4树转换）、哈夫曼编码（贪心策略与前缀特性）以及B/B+树（磁盘IO优化）。同时补充了栈/队列基础、内存与磁盘的物理差异，强调了“不同场景匹配不同数据结构”的核心工程思想。

知识点梳理

1. 平衡二叉树 (AVL Tree)

• 核心机制：通过四种旋转操作维持左右子树高度差 ≤ 1。
  • LL型：右旋（中间节点上提）。
  • RR型：左旋。
  • LR型：先左旋后右旋。
  • RL型：先右旋后左旋。
• 调整原则：插入新节点后，从插入点自底向上逐层检测，遵循“就近原则”优先处理离插入点最近的不平衡节点。
• 性能特征：查询稳定 $O(\log N)$，但构建时旋转频繁、耗性能高。适用场景：查询多、增删少。

2. 红黑树 (Red-Black Tree)

• 本质来源：由2-3-4树转换而来（2节点→黑节点；3节点→黑+红；4节点→黑+2红）。
• 构建逻辑：自底向上插入叶子节点，节点满时通过“向上挤”中间值的方式分裂合并，保持树高平衡。
• 关键特性：
  1. 根节点必为黑色。
  2. 红色节点的子节点必为黑色。
  3. 叶子节点（NIL/null）均为黑色。
  4. 从根到任意叶子的路径上，黑色节点数量相同。
  5. 最长路径（红黑相间）不超过最短路径（纯黑）的2倍。
• 性能优势：查找时间复杂度严格稳定在 $O(\log N)$，不受数据分布影响；相比AVL树旋转更少，综合性能更优。Java中HashMap链表过长时自动转红黑树即基于此。

3. 哈夫曼树与哈夫曼编码

• 核心概念：
  • 权值：节点存储的数值（如字符频率）。
  • 路径长度：根到节点的边数。
  • WPL（带权路径长度）：所有叶子节点的权值 × 路径长度之和。哈夫曼树是WPL最小的二叉树。
• 构建策略（贪心）：每次选权值最小的两个节点合并为新节点（权值为两者之和），重复至只剩一个根节点。注意：相同权值节点合并顺序不影响WPL最优性，但可能导致树形结构不唯一。
• 编码规则：左分支为0，右分支为1。高频字符靠近根（编码短），低频字符远离根（编码长）。
• 前缀特性：任何字符编码都不是其他编码的前缀（因所有字符均在叶子节点），保证解码无歧义。
• 对比定长编码：ASCII等定长编码无法压缩；哈夫曼变长编码通过频率差异化实现高效压缩。

4. 栈与队列

注：两者均限制随机访问，底层可用数组或链表实现，核心在于逻辑约束而非物理存储。

5. B树与B+树（磁盘存储优化）

• 设计动机：磁盘IO（毫秒级）比CPU（纳秒级）慢百万倍，需减少磁盘访问次数。
• B树特性：
  • 多叉结构：K阶B树每个节点最多K-1个键值、K个子节点指针。
  • 页对齐：每个节点独占一个磁盘页（默认4KB），一次IO读取整个节点。
  • 矮胖树形：高阶数（常>100）显著降低树高，减少IO次数。
  • 有序分裂：插入满节点时，中间键值上提分裂，维持有序与平衡。
• B+树优化：
  • 所有数据仅存于叶子节点。
  • 叶子节点通过指针连接成有序链表。
  • 优势：范围查询、顺序访问效率极高，是数据库索引首选。
• vs 红黑树：红黑树适合内存（电信号快、二叉树高度可接受）；B/B+树适合磁盘（机械IO慢、需多叉压高度）。

补充：存储物理原理（逐字稿精华）

• 磁盘读写：写入=电生磁（电流方向决定磁极N/S）；读取=磁生电（磁感线切割线圈感应电流方向）。机械寻道耗时约5-6ms。
• 内存特性：基于电容器，需持续通电维持电荷，断电数据丢失；读取约20ns，比磁盘快百万倍。
• 传输机制：电压信号比电流更稳定（不受电阻变化影响）；总线通过多导线并行传输提升带宽。
• 页管理：OS以4KB页为单位管理磁盘/内存交换，小于4KB文件也占整页（空间换时间）。

⚠️ 易错点提醒

1. AVL旋转触发：必须自底向上检测，且只处理最近的不平衡祖先节点，非全局调整。
2. 红黑树叶子：NIL/null节点才是真叶子（黑色），非存储数据的末端节点。
3. 哈夫曼树唯一性：相同权值节点合并顺序可变，树形可能不同，但WPL一定相同且最优。
4. 哈夫曼前缀：编码只在叶子节点生成，天然避免前缀冲突；若自行设计变长编码必须验证此性质。
5. B树阶数定义：K阶指最大子节点数，键值数=K-1；2-3-4树仅为4阶B树特例。
6. 场景区分：勿将内存数据结构（红黑树）与磁盘数据结构（B树）直接比较性能，二者解决不同层级问题。