算法中主要的几种树

• AVL树追求“高度平衡”，用于快速查找；
• 红黑树在平衡与插入效率之间做折中，是许多库（如 TreeMap、HashMap）的核心结构；
• 哈夫曼树追求“最优编码”，常用于压缩算法（如 ZIP、JPEG、MP3 等）。

---

🌳 一、AVL树（平衡二叉搜索树）

1.1 定义

AVL树（Adelson-Velsky and Landis Tree）是最早被提出的自平衡二叉搜索树（BST）。 它在任何节点上都满足以下平衡条件：

对于任意一个节点，其左子树和右子树的高度差（平衡因子）不超过 1。

即：

| height(left) - height(right) | ≤ 1

若插入或删除节点后破坏了平衡性，则通过**旋转（Rotation）**来恢复。

---

1.2 结构示意

一个 AVL 树既满足 二叉搜索树（BST） 的性质：

左子树 < 根 < 右子树

又保持“尽量平衡”，例如：

      4
    /   \
   2     6
  / \   / \
 1  3  5  7

---

1.3 平衡调整（旋转）

AVL树的关键是 旋转操作。 共有四种旋转类型，用于恢复平衡：

类型	说明	图示
LL旋转	新节点插入左子树的左侧	右旋
RR旋转	新节点插入右子树的右侧	左旋
LR旋转	新节点插入左子树的右侧	先左旋再右旋
RL旋转	新节点插入右子树的左侧	先右旋再左旋

例：LL型（右旋）

插入导致左高：
      5
     /
    3
   /
  2

右旋后变为：

     3
    / \
   2   5

---

1.4 时间复杂度

操作	复杂度
查找	O(log n)
插入	O(log n)（可能伴随旋转）
删除	O(log n)（可能伴随旋转）

---

1.5 优缺点与应用

✅ 优点：

• 高度平衡，查找效率高且稳定（接近完美平衡）。

❌ 缺点：

• 插入/删除频繁时旋转次数多，维护成本高。

📦 适用场景：

• 读操作远多于写操作的系统（如索引结构、缓存树等）。

---

🔴 二、红黑树（Red-Black Tree）

2.1 定义

红黑树是一种 近似平衡的二叉搜索树（BST），它在插入和删除时通过“着色 + 局部旋转”来维持平衡。 红黑树不是严格平衡的，但能保证最长路径不超过最短路径的两倍。

---

2.2 性质（五大约束）

红黑树定义了如下 5 条性质：

1. 每个节点非红即黑；
2. 根节点是黑色；
3. 所有叶子节点（NIL节点）是黑色；
4. 如果一个节点是红的，则它的两个子节点都是黑的（不允许连续红节点）；
5. 从任意节点到其所有叶子节点的路径上，黑色节点数相同。

---

2.3 示例

一个合法的红黑树：

        10(B)
       /     \
   5(R)       15(R)
  /  \        /   \
2(B) 7(B)   12(B) 18(B)

---

2.4 插入与删除平衡调整

红黑树的平衡调整方式复杂于 AVL 树，因为需要满足“颜色约束”。 核心手段包括：

• 重新着色（Recoloring）
• 左旋（Left Rotate）
• 右旋（Right Rotate）

例如插入时常见三种情况：

情况	说明	处理方式
叔叔节点为红	重新染色（父叔变黑，祖父变红）
叔叔节点为黑，且是“内侧”插入	先旋转成“外侧”结构（双旋）
叔叔节点为黑，且是“外侧”插入	单旋并染色

---

2.5 时间复杂度

操作	复杂度
查找	O(log n)
插入	O(log n)
删除	O(log n)

红黑树在最坏情况下高度约为 2 * log2(n+1)，性能非常稳定。

---

2.6 优缺点与应用

✅ 优点：

• 保证平衡的同时减少旋转次数；
• 插入/删除效率高于 AVL；
• 适合频繁修改的场景。

❌ 缺点：

• 查找效率略低于 AVL（因为不完全平衡）。

📦 应用：

• Java 的 TreeMap、TreeSet；
• Java 8 的 HashMap 冲突链表转红黑树；
• Linux 的 CFS调度器、epoll；
• C++ STL 的 std::map / std::set。

---

🟢 三、哈夫曼树（Huffman Tree）

3.1 定义

哈夫曼树（Huffman Tree）是一种用于最优编码（最短加权路径长度）的带权路径树，又称最优二叉树。

其主要应用是 数据压缩（Huffman 编码）。

---

3.2 基本思想

核心目标：

让频率高（权值大）的字符编码更短，频率低的字符编码更长，从而整体平均编码长度最短。

---

3.3 构造过程

假设有字符及其出现频率：

字符	权值
A	5
B	9
C	12
D	13
E	16
F	45

构造步骤：

1. 将所有字符视为独立节点；
2. 每次取权值最小的两个节点合并为一个新节点，新节点的权值=两子节点权值之和；
3. 重复步骤 2，直到只剩下一个根节点。

最终得到的二叉树即为哈夫曼树。

---

3.4 编码示例

若从根到左子树记为 0，右子树记为 1， 则每个字符的哈夫曼编码如下：

字符	编码
F	0
C	100
D	101
A	1100
B	1101
E	111

平均编码长度最小，达到压缩效果。

---

3.5 应用场景

✅ 优点：

• 平均码长最小，实现高效压缩。

📦 应用：

• 文件压缩（ZIP、GZIP、JPEG、MP3 等）
• 传输编码（如霍夫曼编码通信）

---

⚖️ 四、三者对比总结

特性	AVL树	红黑树	哈夫曼树
类型	平衡二叉搜索树	近似平衡二叉搜索树	最优二叉树（非搜索树）
平衡性	严格平衡	近似平衡	不要求平衡
调整手段	旋转	旋转 + 着色	合并最小权值节点
查找效率	高（O(log n)）	稍低（O(log n)）	不用于查找
插入/删除效率	较低（频繁旋转）	较高（较少旋转）	只构建一次
应用场景	数据索引、查找树	Java TreeMap、HashMap等	数据压缩、编码
设计目标	查找性能最优	插入删除性能与平衡折中	编码长度最优

---

🧠 五、总结

• AVL树：强调高度平衡，查找快，插入慢。
• 红黑树：适度平衡，综合性能最好，是现代语言库的首选。
• 哈夫曼树：用于编码压缩，与搜索无关。

三者分别代表了数据结构三种优化思路：

平衡 → 稳定 → 最优编码。