目录

有序二叉树：

平衡二叉树：

234树：

红黑树

红黑树特点：

为什么红黑树是最优二叉树？

哈夫曼树和哈夫曼编码

---

有序二叉树：

平衡二叉树：

在有序二叉树的基础上得来的，且左右子树的高度差绝对值不能超过1.

调整策略：

1、LL型调整策略

注意要找造成不平衡节点的最近的不平衡节点

2、RR型

10插入后，5是不平衡的节点，往右走两步。中间节点为8

3、LR型

转换为LL型

4、RL型

平衡二叉树太耗费资源，引入了红黑树。红黑树的基础是234树

234树：

变成四个节点的后，取中间节点向上走一层，连接两端

红黑树

二节点用黑色表示，三节点用黑红，四节点用黑红红表示，然后按照234树变成红黑树。

红黑树特点：

1、红黑树只有红色和黑色两种颜色

2、根节点一定是黑色的，

3、叶子节点是存在的，统一为黑色

4、如果一个节点的值是红色的那么他的子节点的值一定是黑色的

5、从根节点到任意一个叶子节点，路径上的黑色节点数目相同。（黑色节点数就是234数的高度）

为什么红黑树是最优二叉树？

最长链不超过最短链的二倍

时间复杂度比有序二叉树更稳定，平衡调整更简单

哈夫曼树和哈夫曼编码

自定义变长编码表容易引起歧义