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

[[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.2'''：“插入结点是其父结点的右子结点”，处理：
## 对 P 进行左旋；
## 把 P 设置为插入结点，得到“情景 4.2.1”，并进行如上“情景4.2.1”处理。
#: [[File:红黑树：插入情景4.2.2.png|600px]]

==== 情景4.3：父结点为红结点，叔叔结点不存在或为黑结点，父结点是祖父结点的右子结点【类似“情景4.2”】 ====
【同上“情景4.2”，只是方向不同，对应的旋转操作不同】
分为两种情况：
# '''情景 4.3.1'''：“插入结点是其父结点的左子结点”，处理：
## 将 P 设为黑色；
## 将 PP 设为红色；
## 对 PP 进行左旋。
#: [[File:红黑树：插入情景4.3.1.png|400px]]
#: 如上，已平衡无需再处理。
# '''情景 4.3.2'''：“插入结点是其父结点的右子结点”，处理：
## 对 P 进行左旋；
## 把 P 设置为插入结点，得到“情景 4.3.1”，并进行如上“情景4.3.1”处理。
#: [[File:红黑树：插入情景4.3.2.png|600px]]

=== 删除 ===
删除操作也包括两部分工作：
# 查找目标结点；
#* 当不存在目标结点时，忽略本次操作；
# 删除后自平衡。
#* 删除结点后还需要找结点来替代被删除结点的位置：
## 被删除结点无子结点，直接删除；
## 被删除结点仅一个子结点，用子结点替换删除结点；
## 被删除结点有两个子结点，用后继结点替换删除结点；【后继结点（中序遍历的后继节点）。即：大于删除结点的最小结点。】



删除思路：'''删除结点被替代后，在不考虑结点的键值的情况下，对于树来说，可以认为删除的是替代结点'''。如图：
: [[File:红黑树：删除结点换位思路.png|600px]]
所以，如上三种替代节点情况都可以转换：
# “被删除结点仅一个子结点”：可以看作“删除子节点”。如果子节点又有两个子节点（对于红黑树，不可能子节点只有一个子节点），则相当于删除节点时“被删除结点有两个子结点”。
# “被删除结点有两个子结点”：可以看作“删除后继节点”。如果后继结点有右子结点（肯定不存在左结点？？？），则相当于删除节点时“被删除结点仅一个子结点”。
如上图，删除“P”（有两个子节点），可以看作删除“P”的后继节点“Q”
: [[File:红黑树：二叉树删除情景转换.png|400px]]
综上所述，'''删除操作删除的结点可以看作删除替代结点，而替代结点最后（经过层层的删除情景转换）总是在树末'''。
: 所以，删除红黑树的情景就少了很多，只需考虑删除树末结点的情景了。



所有删除情景：
: [[File:红黑树：删除操作结点的叫法约定.png|400px]]
: [[File:红黑树：删除情景.png|1200px]]

==== 情景1：替换结点是红色结点 ====
把替换结点换到了删除结点的位置时，由于替换结点时红色，删除也了不会影响红黑树的平衡，只要'''把替换结点的颜色设为被删除的结点的颜色即可重新平衡'''。

==== 情景2：替换结点是黑结点 ====
当替换结点是黑色时，就不得不进行自平衡处理了。我们必须还得考虑替换结点是其父结点的左子结点还是右子结点，来做不同的旋转操作，使树重新平衡。

===== 情景2.1：替换结点是其父结点的左子结点 =====
分为两种情况：
# '''情景2.1.1'''：“'''替换结点的兄弟结点是红结点'''”，处理：
#* 若兄弟结点是红结点，那么根据“性质4”，兄弟结点的父结点和子结点肯定为黑色。
## 将 S 设为黑色；
## 将 P 设为红色；
## 对P进行左旋，得到“情景2.1.2.3”并处理。
#: [[File:红黑树： 删除情景2.1.1.png|600px]]
# '''情景2.1.2'''：“'''替换结点的兄弟结点是黑结点'''”，处理：
#* 当兄弟结点为红结点，其父结点和子结点的具体颜色无法确定。此时又得考虑多种情景：
## “'''情景2.1.2.1'''”：“'''替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色'''”，处理：
##* 即将删除的左子树的一个黑色结点【R 结点】，显然左子树的黑色结点少 1 了，然而右子树又又红色结点，那么我们直接向右子树“借”个红结点来补充黑结点就好啦，此时肯定需要用旋转处理了。
### 将 S 的颜色设为 P 的颜色；
### 将 P 设为黑色；
### 将 SR 设为黑色；
### 对 P 进行左旋。
##: [[File:红黑树：删除情景2.1.2.1.png|600px]]
##: 【如上，平衡后的图看似不满足红黑树的性质（性质5）：R 是即将替换的，它还参与树的自平衡，平衡后再替换到删除结点的位置，即 R 最终可以看作是删除的。所以最终仍是满足红黑树性质的。】
## “'''情景2.1.2.2'''”：“'''替换结点的兄弟结点的右子结点为黑结点，左子结点为红结点'''”，处理：
##* 兄弟结点【S 结点】所在的子树有红结点，我们总是可以向兄弟子树借个红结点过来，显然该情景可以转换为“情景2.1.2.1”。
### 将 S 设为红色；
### 将 SL 设为黑色；
### 对 S 进行右旋，得到“情景2.1.2.1”。
##: [[File:红黑树：删除情景2.1.2.2.png|600px]]
## “'''情景2.1.2.3'''”：“'''替换结点的兄弟结点的子结点都为黑结点'''”，处理：
##* 兄弟子树没有红结点可“借”时：把兄弟结点设为红色，再把父结点当作替代结点，去向父结点的兄弟结点去“借”，而后再进行平衡。【把兄弟结点设为红色，是为了在 P 所在的子树中保证平衡（R 即将删除，少了一个黑色结点，子树也需要少一个）】
### 将 S 设为红色；
### 把 P 作为新的替换结点；
### 重新应用删除结点情景来进行处理。
##: [[File:红黑树：删除情景2.1.2.3.png|600px]]

===== 情景2.2：替换结点是其父结点的右子结点【类似“情景2.1”】 =====
【同上“情景2.1”，只是方向不同，对应的旋转操作不同】
# '''情景2.2.1'''：“'''替换结点的兄弟结点是红结点'''”，处理：
## 将 S 设为黑色；
## 将 P 设为红色；
## 对P进行右旋，得到“情景2.2.2.3”并处理。
#: [[File:红黑树：删除情景2.2.1.png|600px]]
# '''情景2.2.2'''：“'''替换结点的兄弟结点是黑结点'''”：
## “'''情景2.2.2.1'''”：“'''替换结点的兄弟结点的左子结点是红结点，右子结点任意颜色'''”，处理：
### 将 S 的颜色设为 P 的颜色；
### 将 P 设为黑色；
### 将 SL 设为黑色；
### 对 P 进行右旋。
##: [[File:红黑树：删除情景2.2.2.1.png|600px]]
## “'''情景2.2.2.2'''”：“'''替换结点的兄弟结点的左子结点为黑结点，右子结点为红结点'''”，处理：
### 将 S 设为红色；
### 将 SR 设为黑色；
### 对 S 进行左旋，得到“情景2.2.2.1”。
##: [[File:红黑树：删除情景2.2.2.2.png|600px]]
## “'''情景2.2.2.3'''”：“'''替换结点的兄弟结点的子结点都为黑结点'''”，处理：
### 将 S 设为红色；
### 把 P 作为新的替换结点；
### 重新应用删除结点情景来进行处理。
##: [[File:红黑树：删除情景2.2.2.3.png|600px]]