查看“树：红黑树”的源代码

[[category:数据结构]]

== 关于 ==
红黑树（Red Black Tree） 是一种含有红黑结点并能'''自平衡二叉查找树'''。
* 它可以在“O(log n)”时间内做查找，插入和删除（n 是树中元素的数目）。


Question：
# 红黑树是平衡二叉树吗？
#: 红黑树是一种特化的 AVL树，但其并非严格的 AVL树，其平衡因子的绝对值可能大于 1。但对其进行平衡的代价较低，其平均统计性能要强于 AVL 。
# 红黑树的应用？
#: 红黑树的应用十分广泛，如下：
## JDK 的集合类 TreeMap 和 TreeSet 底层实现，Java8 中 HashMap 的实现。
## Linux 的进程管理、内存管理，设备驱动及虚拟内存跟踪等一系列场景中。
## 一些数据库的索引实现等。

== 定义和性质 ==
# 每个节点要么是黑色，要么是红色。
# 根节点是黑色。
# 每个叶子节点（NIL）是黑色。
# '''每个红色结点的两个子结点一定都是黑色'''。【？】
#* 从每个叶子到根的所有路径上不能有两个连续的红色节点。
# '''任意一结点到每个叶子结点的路径都包含数量相同的黑结点'''。【？？？】
#* 如果一个结点存在黑子结点，那么该结点肯定有两个子结点。【所以，不存在只有一个叶子节点的节点？？？（因为叶子节点为黑色）】

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


典型的红黑树，如图：
: [[File:典型的红黑树.jpg|700px]]

== 自平衡 ==
红黑树总是通过'''旋转'''和'''变色'''达到自平衡。
* 旋转，包括“左旋”、“右旋”，与平衡二叉树同理。

== 操作 ==
在进行“插入”和“删除”等可能会破坏树的平衡的操作时，需要进行自平衡以到平衡状态。
* “读取”操作与排序二叉树同理，不会对树结构造成破坏，所以不需要进行自平衡。
【红黑树的插入、删除包含很多种情况，每种情况有不同的处理方式，较为复杂（4种插入case和5种删除case）】

=== 插入 ===
----
插入操作包括两部分工作：
# 查找插入的位置；
# 插入后自平衡。
查找插入的父结点很简单，跟查找操作区别不大。重点在于自平衡。


* '''插入的节点都是红色'''。原因如下：
*# 如果插入结点是红色：在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。而在父结点（如果存在）为红色结点时，才需要自平衡。
*# 如果插入结点是黑色：那么插入位置所在的子树黑色结点总是多 1，必须做自平衡。
*'''红黑树的生长是自底向上的'''。从插入节点开始，向上作自平衡处理。（这点不同于普通的二叉查找树，其生长是自顶向下的）


所有插入情景：
:[[File:红黑树：插入操作结点的叫法约定.png|400px]]
:[[File:红黑树：插入情景.png|1000px]]
如上，情景1、2和3的处理很简单，而情景4.2和情景4.3只是方向反转而已。所以难点再“插入结点的父结点为红结点”时：
: '''如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。'''这点很重要，因为后续的旋转操作肯定需要祖父结点的参与。


==== 插入情景4.1：父结点为红结点，叔叔结点存在并且为红结点 ====
从红黑树“性质4”（不可以同时存在两个相连的红结点）可以确定：祖父结点肯定为黑结点。

那么此时该插入子树的红黑层数的情况是：'''黑红红'''，显然最简单的处理方式是把其改为：'''红黑红'''：
# 将 P 和 S 设置为黑色。
# 将 PP 设置为红色。
#:如图：
#: [[File:红黑树：插入情景4.1_1.png|400px]] [[File:红黑树：插入情景4.1_2.png|400px]]
# 把 PP 设置为当前插入结点：【此时 PP 结点为红色】
## 如果 PP 的父结点是黑色，则已平衡无需再处理；
## 如果 PP 的父结点是红色（“性质4”），则把 PP 当作新的插入结点，应用不同插入情景继续插入操作自平衡处理。
## 如果 PP 刚好为根结点时（“性质2”），必须把 PP 重新设为黑色，那么树的红黑结构变为：'''黑黑红'''。
##: 即，从根结点到叶子结点的路径中，黑色结点增加了。【这是唯一一种会增加红黑树黑色结点层数的插入情景】

==== 插入情景4.2：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的左子结点 ====
从红黑树“性质5”（任意一结点到每个叶子结点的路径都包含数量相同的黑结点）可以确定：叔叔结点非红即为叶子结点（NIL）。
: 因为如果叔叔结点为非叶子节点的黑结点，而父结点为红结点，那么叔叔结点所在的子树的黑色结点就比父结点所在子树的多了，这不满足红黑树的“性质5”。


分为两种情况：
# '''情景 4.2.1'''：“插入结点是其父结点的左子结点”，处理：
## 将 P 设为黑色。【此时，叔叔节点不存在，或为叶子节点（黑色）】
## 将 PP 设为红色。
## 对 PP 进行右旋。
#: [[File:红黑树：插入情景4.2.1.png|400px]]
#: 如上，已平衡无需再处理。
# '''情景 4.2.1'''：“插入结点是其父结点的右子结点”，处理：
## 对 P 进行左旋。
## 把 P 设置为插入结点，得到“情景 4.2.1”，并进行如上“情景4.2.1”处理。
#: [[File:红黑树：插入情景4.2.2.png|600px]]

==== 插入情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点 ====
【同上，情景4.2，只是方向不同，对应的旋转操作不同】


分为两种情况：
# '''情景 4.3.1'''：“插入结点是其父结点的左子结点”，处理：
## 将 P 设为黑色。【此时，叔叔节点不存在，或为叶子节点（黑色）】
## 将 PP 设为红色。
## 对 PP 进行左旋。
#: [[File:红黑树：插入情景4.3.1.png|400px]]
#: 如上，已平衡无需再处理。
# '''情景 4.3.1'''：“插入结点是其父结点的右子结点”，处理：
## 对 P 进行左旋。
## 把 P 设置为插入结点，得到“情景 4.3.1”，并进行如上“情景4.3.1”处理。
#: [[File:红黑树：插入情景4.3.2.png|600px]]

=== 删除 ===