树：红黑树

关于

红黑树（Red Black Tree） 是一种含有红黑结点并能自平衡二叉查找树。

• 它可以在“O(log n)”时间内做查找，插入和删除（n 是树中元素的数目）。

Question：

1. 红黑树是平衡二叉树吗？

   红黑树是一种特化的 AVL树，但其并非严格的 AVL树，其平衡因子的绝对值可能大于 1。但对其进行平衡的代价较低，其平均统计性能要强于 AVL 。

2. 红黑树的应用？

   红黑树的应用十分广泛，如下：

   1. JDK 的集合类 TreeMap 和 TreeSet 底层实现，Java8 中 HashMap 的实现。
   2. Linux 的进程管理、内存管理，设备驱动及虚拟内存跟踪等一系列场景中。
   3. 一些数据库的索引实现等。

定义和性质

1. 每个节点要么是黑色，要么是红色。
2. 根节点是黑色。
3. 每个叶子节点（NIL）是黑色。
4. 每个红色结点的两个子结点一定都是黑色。【？】
   • 从每个叶子到根的所有路径上不能有两个连续的红色节点。
5. 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。【？？？】
   • 如果一个结点存在黑子结点，那么该结点肯定有两个子结点。【所以，不存在只有一个叶子节点的节点？？？（因为叶子节点为黑色）】

这些规则限制保证了红黑树的自平衡。保证了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。【？？？】

典型的红黑树，如图：

自平衡

红黑树总是通过旋转和变色达到自平衡。

• 旋转，包括“左旋”、“右旋”，与平衡二叉树同理。

操作

在进行“插入”和“删除”等可能会破坏树的平衡的操作时，需要进行自平衡以到平衡状态。

• “读取”操作与排序二叉树同理，不会对树结构造成破坏，所以不需要进行自平衡。

【红黑树的插入、删除包含很多种情况，每种情况有不同的处理方式，较为复杂（4种插入case和5种删除case）】

插入

插入操作包括两部分工作：

1. 查找插入的位置；
2. 插入后自平衡。

查找插入的父结点很简单，跟查找操作区别不大。重点在于自平衡。

插入的节点都是红色。原因如下：

1. 如果插入结点是红色：在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。而在父结点（如果存在）为红色结点时，才需要自平衡。
2. 如果插入结点是黑色：那么插入位置所在的子树黑色结点总是多 1，必须做自平衡。

所有插入情景：

文件:红黑树插入操作结点的叫法约定.png

文件:红黑树插入情景.png

如上，情景1、2和3的处理很简单，而情景4.2和情景4.3只是方向反转而已。所以难点并不多。