红黑树是一种具有红黑性质的平衡树。在前面章节中我们有讲到过另外一种平衡树。
AVL树：https://www.jianshu.com/p/fa3858234329
AVL树讲究完全平衡。一旦左右子树高度相差2，就需要旋转来达到平衡。旋转的次数是O(h)。和高度相等。
红黑树就厉害了，只要达到近似平衡，黑高度（从根节点到叶子节点的黑色节点数目）左子树和右子树相同。
红黑树的基本概念和性质
哨兵节点 如果一个节点没有子节点或者没有父节点，则该节点指针属性是NIL 。
一个红黑树是满足下列性质的BST:
- （1）每个节点或者是黑色，或者是红色。
- （2）根节点是黑色。
- （3）每个叶子节点（NIL）是黑色。
- （4）如果一个节点是红色的，则它的子节点必须是黑色的。
- （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
简单概括： 黑根，红黑黑，黑高相同
一颗完整的红黑树，如下图所示：
image.png
红黑树，和AVL树的区别，就在于，它总是希望通过，简单的改变颜色，就使这棵树，达到黑高度相同。从而平衡。实在不行就通过旋转。所以红黑树的平衡方法，改变颜色,旋转。
左旋和右旋
image.png
根据上图，我们按照《算法导论》的伪代码进行逐行解析源码
//按照从下往上不断平衡的原则，先搞定X的指针变化，然后在搞定Y的指针变化，最后把X,Y指针相连
//p 是父节点的意思，NIL 是空节点的意思，left和right分别是左节点和右节点的意思
//1 首先 旋转完的x的right x 的右节点指针指向y的左节点【b】
//2 旋转完的【b】的父亲改变了， y.left.p = x; 【b】的父亲变成x
//3 旋转完的 Y的父节点也改变了，
//4 【R】节点的子节点改变了 对应这段代码 x.p.left = y x.p.right = y ;
//5 最后把他两个相连 y.left = x; x.p =y;
LEFT-ROTATE(T, x){
y = x.right // set y 设置y是x的右子树
x.right = y.left // 【x】的右节点指针指向y的左节点【b】
if (y.left != T.NIL){ //如果y的左子树不空 【b】不是空 ，就是 【b】的父亲
y.left.p = x; //【b】的父亲改成X
}
y.p = x.p ; //Y的父亲是原来X的父亲
if(x.p ==T.NIL){ //如果x的父亲是空的，说明x是根节点。
T.root = y ; //那么这个时候，这棵树的根节点，变成Y
}else if( x.p.left ==x ){ //如果【x】是【R】的左节点
x.p.left = y ; //那么改成【R】的左节点是【Y】
}else{ //如果【x】是【R】的右节点
x.p.right = y ; //那么改成【R】的右节点是【Y】
}
y.left = x;
x.p =y;
}
主要步骤就是
- 先找到旋转反方向的子节点【Y】，作为固定点，左旋就是逆时针旋转【X】,右旋就是顺时针旋转【X】。旋转之后，从下到上，从X===【b】==》Y===》R(右旋转正好左右调换)逐渐改变指针。使得指针指向正确的节点。右旋正好镜像调换，所以就不写了。
jdk源码中TreeMap是红黑树的实现。还有类似的TreeSet(底层是用TreeMap的Key来保存 Set 集合的元素)，下面我们来看看，TreeMap中的左旋，右旋代码：
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
Entry<K,V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
p对应伪代码中的【x】,【r】对应【Y】,简直是一模一样的代码（过分）。
红黑树的插入操作：
上伪代码：
RB-INSERT(T, z){
y = T.NIL ; // 新建节点“y”，将y设为空节点。
x = T.root ; // 设“红黑树T”的根节点为“x”
while(x!= T.NIL){ //先循环遍历，从根节点不断往下找，直到找到插入的位置，
//插入之后，肯定是叶子节点，所以x =T.NIL ，while条件不满足，跳出循环
y =x ; //最后是插入位置Y，也就是说，插入的节点的父节点是【y】
if(z.key<x.key){
x =x.left ;
}else{
x = x.right;
}
}
z.p = y ; // 设置 “z的父亲” 为 “y”
if(y==T.NIL){
T.root =z ; // 若父节点【y】是空节点，则将【z】设为【根节点】
}else if(z.key <y.key){ // 若【z】小于父节点【y】 那，就是y 的左节点
y.left =z ;
}else{
y.right = z; // 若【z】大于父节点【y】 那，就是y 的右节点
}
z.left =T.NIL ;
z.right =T.NIL ;
z.color = RED ;
RB-INSERT-FIXUP(T, z) // 通过RB-INSERT-FIXUP对红黑树的节点进行颜色修改以及旋转，
// 让树T仍然是一颗红黑树
}
基本步骤就是先找到插入位置【y】，这个作为插入节点【z】的父节点。再判断是 【y】节点的左节点还是右节点，最后，插入的时候是叶子节点，所以left.right都是空节点NIL。刚开始插入为了满足规则（5）.不破坏黑平衡，所以先插入的节点，肯定是红色的。
再看TreeMap的实现，没有传入Comparator的时候
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value); //如果map中原来有的话，替换原来的值，直接return
} while (t != null);
}
//parent 就相当于伪代码中的y ,新建一个节点Entry
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
可以发现代码差不多，也是先查找插入位置，然后在和父节点比较大小，确定是父节点的左节点还是右节点。
插入操作之后的平衡操作
- 情况说明：被插入的节点是根节点。
处理方法：直接把此节点涂为黑色。 - 情况说明：被插入的节点的父节点是黑色。
处理方法：什么也不需要做。节点被插入后，仍然是红黑树。 - 情况说明：被插入的节点的父节点是红色。
处理方法：那么，该情况与红黑树的“特性(5)”相冲突。这种情况下，被插入节点是一定存在非空祖父节点的；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。理解这点之后，我们依据"叔叔节点的情况"，将这种情况进一步划分为3种情况(Case)。
在下面的伪代码中，详细讲解了3种情况，该如何操作，以及为什么这么操作，使得这个红黑树趋于平衡。
3中情况： - 当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。
- 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子
- 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子
//z是插入之后的节点，而且已经颜色变成红色的了
RB-INSERT-FIXUP(T, z){
while(z.p.color ==RED){
if(z.p ==z.p.p.left) { //如果z的父节点是祖父节点的左孩子
y = z.p.p.right ; //y是z的叔叔节点
//CASE1 =====================叔叔是红色（前提条件父亲节点是红色的）
/**
* CASE 1
* 如果叔叔也是红色的，那么同时把叔叔和父亲变成黑色的，
* 然后祖父节点变成红色的，就能使，这棵小红黑树，黑平衡
* 因为叔叔和父亲，同时+1 ,祖父-1 ，经过z的黑高度相当于没变。
*/
if(y.color ==RED){
z.p.color =BLACK ;
y.color = BLACK;
z.p.p.color = RED ;
z = z.p.p ; //然后祖父节点，变成新的当前节点，就是说，
//z节点到祖父节点，这棵小红黑树，已经黑平衡了，从下往上逐渐通过
//变色或者旋转来使整个树，黑平衡。
/**
* CASE 2 (条件 y.color =BLACK && z == z.p.right)
* 既然不属于CASE1 ，那么 y.color ==RED 不成立，那就是说 y 是黑色的，叔叔节点是黑色的
* z是右节点， 看下图中 【z】节点 =【007】 【z.p】z父亲节点 =【002】 【y】z叔叔节点 =【014】
* 之前 我们说过，红黑树新增的时候，【核心思想】：【要不断的将破坏红黑树特性的红色节点上移(即向根方向移动)】
* 那么应该是【002】节点为固定点，然后【007】节点逆时针旋转（左旋），把【007】转到【002】和【011】中间
* ，旋转完发现，【002】和【007】连续两个红节点，不符合红黑树特性（4）
*/
}else if(z == z.p.right){
z = z.p ;
LEFT-ROTATE(T, z);
}
/**
* CASE 3 (条件 y.color =BLACK && z == z.p.left)
* z是左节点， 看下图中 CASE3 【z】节点 =【002】 ，经过case2的时候z = z.p 使得z是【002】节点
* 首先尝试，改变颜色直接到达黑平衡。吧【z.p】【007】节点变成红色，那经过【007】节点的黑色-1 .那么
* 把【011】节点变成黑色，+1。使得黑高度正负抵消，但是【011】到【015】这条路径，黑高度又-1 ，然后通过
* 【007】位固定点，顺时针旋转【011】节点，使得【007】这个黑色加入到【011】===》【015】这条路中。
*/
z.p.color = BLACK ;
z.p.p.color =RED ;
RIGHT-ROTATE(T, z.p.p);
}else{
same as then clause with "right" and "left" exchanged 正好相反，然后交换left和right就好了
}
}
root.color = BLACK; 在最后 root根节点，变成黑色的根节点
}
下图是，3种情况，如何改变颜色，或者旋转使得趋于黑平衡。
image.png
TreeMap中的fixAfterInsertion方法，和上面的伪代码，实现一模一样 。
红黑树的删除操作
红黑树的复杂主要在于删除操作
主题思路基本同二叉查找树，首先查找到这个节点z，然后就是执行RB-DELETE算法，当结点z有至多一个儿子时，让y=z，然后删除结点y用结点y的儿子x（x可以是nil，这时nil.parent可指向z.parent，体现了哨兵的作用）去取代结点y，z有两个儿子时，删除结点z的后继y，并用y的唯一的儿子结点x取代y
上删除操作的伪代码：
/**
* 主题思路基本同二叉查找树，首先查找到这个节点z，
* 然后就是执行RB-DELETE算法，先当做BST删除掉节点，删除节点，需要改变指针，或者需要后继赋值
* 算法描述：
* 当结点z有至多一个儿子时，
* 让y=z，然后删除结点y用结点y的儿子x（x可以是nil，
* 这时nil.parent可指向z.parent，体现了哨兵的作用）去取代结点y，z有两个儿子时，
* 删除结点z的后继y，并用y的唯一的儿子结点x取代y
*/
RB-DELETE(T, z){
if(z.left ==T.NIL || z.right ==T.NIL){
y= z;
}else{
y = TREE-SUCCESSOR(z); // TREE-SUCCESSOR可以是左子树的最大值，或者右子树的最小值.
// 【注意：】 后继只可能最多有一个孩子，因为假设TREE-SUCCESSOR算法取得是右子树的最小值.
// 那么假如左右子树都有，那左子树肯定比这个后继节点小，所以所谓的后继就不是后继了，取左子树最大值同理
//所以下面是分两种情况
}
if(y.left != T.NIL){
x = y.left;
}else{
x = y.right ;
}
/**
* x是y的替换品，那么x肯定是个叶子节点，只需要改变x的parent, 和y的父亲节点的指针，
* y如果是y父亲节点的左孩子，就if(y.p.left ==y) y.p.left = x; 父亲节点的左孩子指向x(y的替换品)
* y如果是y父亲节点的右孩子，就if(y.p.right ==y) y.p.right = x; 父亲节点的右孩子指向x(y的替换品)
*/
x.p = y.p ; //x的parent替换为y的parent 本来是y.p===>y===>x,把y干掉之后，y.p===>x,也就是x.p = y.p
/**
* CASE1 y（被删除的节点）的父亲节点是空，那么y就是根节点，z也是根节点，删除
* 之后，x顶替，成为root节点
*/
if(y.p ==T.NIL){
T.root = x ;
/**
* CASE2 y（被删除的节点）是父亲节点的左孩子，x顶替为y父亲节点的左孩子
*
*/
}else if(y.p.left ==y){
y.p.left = x; //那么x替换成y.p.left x是y一个替换品
}else{
y.p.right = x; //那么x替换成y.p.right
}
if( y!= z){
z.key = y.key; //【y】节点的值 赋值给 【z】节点
}
//最后
if(y.color == BLACK){
RB-DELETE-FIXUP(T, x)
}
}
下面，我们来一个例子，来逐行校对，上面的伪代码。
图0： 原图： 需要删除节点7，根节点
image.png
图1：把y（删除的节点）的值，赋值给z,
image.png
图2： 赋值过去之后，根节点是数字5， 然后2节点的右节点，指向替代品4,4的父亲指针指向原来y（5号节点）的父亲2号节点。
image.png
图3：指针变换结束
image.png
删除之后的平衡操作。
首先上伪代码，大家跟着伪代码一步步理解。
/**
* 红黑树删除节点后，重新平衡后，可能有多种平衡方法，平衡之后，树结构也有多样的
* 承接上面的RB-DELETE ,x是实际被删除节点【y】的替代品，承接图3，x 就是4号节点，是红色的,直接走最后一步，把x变成黑色，就好了
*然后图0 ，y节点原来是黑色的，那么根结点到x结点的路径中的黑色结点数目将会减少1，需要执行RB-DELETE-FIXUP，恢复黑平衡
* 【既然删除y(y是黑色)，意味着减少一个黑色节点；那么，再在该位置上增加一个黑色即可。
* 这样，当我们假设"x包含一个额外的黑色"，就正好弥补了"删除y所丢失的黑色节点"】
* 加上黑色之后，就会出现下面3种情况：
* ① 情况说明：x是“红+黑”节点。
* 处理方法：直接把x设为黑色，结束。此时红黑树性质全部恢复。
* ② 情况说明：x是“黑+黑”节点，且x是根。
* 处理方法：什么都不做，结束。此时红黑树性质全部恢复。
* ③ 情况说明：x是“黑+黑”节点，且x不是根。
* 处理方法：这种情况又可以划分为4种子情况。这4种子情况
* 总共有四种Case ,其中CASE1 ====》 可以转化为CASE2 ,也可以转化成case3 ,
* CASE3 ====》 可以转化为CASE4 ；
*/
RB-DELETE-FIXUP(T, x){
while(x!=root && x.color ==BLACK){
if(x == x.p.left){
w = x.p.right ; //w 是x的兄弟节点
/**
* CASE1 x是“黑+黑”节点，x的兄弟节点是红色。
* 因为【总的思路是把多余的黑色节点往上移动】
* case1 左旋转使得兄弟节点是黑色的。
* 只有这样子，才能先x父节点的黑色+1 （x的黑节点，移动其中一个到父节点，【往上移动】），
* 然后x的兄弟节点黑色-1 ，变成红色。
*
*/
if(w.color ==RED){
w.color = BLACK;
x.p.color = RED;
LEFT-ROTATE(T, x.p);
w = x.p.right;
}
/**
* case 2 x是“黑+黑”节点，x的兄弟节点是黑色。x的兄弟节点的两个孩子都是黑色
* 将“x中多余的一个黑色属性上移(往根方向移动)”
* x是“黑+黑”节点，我们将x由“黑+黑”节点 变成 “黑”节点，多余的一个“黑”属性移到x的父节点中，
* 即x的父节点多出了一个黑属性(若x的父节点原先是“黑”，则此时变成了“黑+黑”；
* 若x的父节点原先时“红”，则此时变成了“红+黑”)。
* 此时，需要注意的是：所有经过x的分支中黑节点个数没变化；
* 但是，所有经过x的兄弟节点的分支中黑色节点的个数增加了1(因为x的父节点多了一个黑色属性)！
* 为了解决这个问题，我们需要将“所有经过x的兄弟节点的分支中黑色节点的个数减1”即可，
* 那么就可以通过“将x的兄弟节点由黑色变成红色”来实现。
* 经过上面的步骤(将x的兄弟节点设为红色)，
* 多余的一个颜色属性(黑色)已经跑到x的父节点中。
* 我们需要将x的父节点设为“新的x节点”进行处理。
* 若“新的x节点”是“黑+红”，直接将“新的x节点”设为黑色，即可完全解决该问题；
* 若“新的x节点”是“黑+黑”，则需要对“新的x节点”进行进一步处理。
*/
if(w.left.color ==BLACK && w.right.color ==BLACK){
w.color =RED;
x = x.p ;
}else {
/**
* case 3 x是“黑+黑”节点，x的兄弟节点是黑色。x的兄弟节点的左孩子是红色，右孩子是黑色的
* case 3是为了case4 做准备的，总而言之，case3变化之后，得呈现这个样子：
*
*/
if(w.left.color ==RED && w.right.color ==BLACK){
w.left.color = BLACK;
w.color =RED;
RIGHT-ROTATE(T, w)
w =x.p.right;
}
/**
* case 4 比较复杂,在外面解释
*
*/
w.color = x.p.color;
x.p.color =BLACK ;
w.right.color =BLACK;
LEFT-ROTATE(T, x.p);
x = root;
}
}else{
same as then clause with "right" and "left" exchanged
}
}
x.color =BLACK;
}
用一个红黑树的例子来讲解。
先上原图：
图0：
image.png
注意：5节点后面还有两个NIL（节点），哨兵节点，到后面你会发现，这个哨兵节点是有用的。
接下来，我们删除0010节点。
图1：
image.png
删除掉之后，我们会走【RB-DELETE-FIXUP】这个算法，来让树保持黑平衡。
case 1 就是图1
case1 : *x是"黑+黑"节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。* x节点就是NIL 节点,就是图中的【NULL LEAF】节点。从伪代码分析中我们可以知道，case1和case3 都只是一种中间状态，都需要后续的操作，才能真正实现黑平衡。case2和case4 ，才能实现黑平衡。因为只有case2和case4 ，把x上面的多余黑色，向上移动到父节点。
接下来，走case1中的伪代码，w代表兄弟节点，p代表父亲,LEFT-ROTATE(T, x.p);代表旋转x的父亲节点，也就是【005】节点。
if(w.color ==RED){
w.color = BLACK;
x.p.color = RED;
LEFT-ROTATE(T, x.p);
w = x.p.right;
}
经过变化之后，如下图：
图3 ：
image.png
case 3 x是“黑+黑”节点，x的兄弟节点是黑色。x的兄弟节点的左孩子是红色，右孩子是黑色的
case 3是为了case4 做准备的，,在走case3 的伪代码：
if(w.left.color ==RED && w.right.color ==BLACK){
w.left.color = BLACK;
w.color =RED;
RIGHT-ROTATE(T, w)
w =x.p.right;
}
经过变化之后，如下图：
图4 ：
image.png
case 4 x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色。【0011】节点的左孩子是个NIL（黑色）节点。
case 4 涉及到3条路径的黑高度变化。
在走case4 的伪代码：
w.color = x.p.color; //上图中就是把5号节点的颜色，给兄弟节点【0011】节点
x.p.color =BLACK ;
w.right.color =BLACK;
LEFT-ROTATE(T, x.p);
x = root;
case 4 完整的一个操作如下图：
图4-2 ：
image.png
- 首先旋转之后，把 x.p.color =BLACK ; 把父亲节点的颜色变色黑色，就是【核心思想：把黑加黑中的某个黑色，向上移动给父亲节点】。
- 但是这样子的话，根节点到兄弟节点的左孩子NULL LEAF，这条路径多了一个黑色，然后把0011节点变成红色，
- 但是这样的话，根节点到兄弟节点的右孩子0012节点，少了一个黑色，那就吧0012节点变成黑色。最终根节点到3个NULL LEAF都是黑高度=2 ；
上面这个红黑树，删除节点之后，经过了3个情况。最终才完成黑平衡。但是并没有经过case2 .
然后我们再来看看case2如何让树黑平衡。
x是"黑+黑"节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色
将“x中多余的一个黑色属性上移(往根方向移动)”。 x是“黑+黑”节点，我们将x由“黑+黑”节点 变成 “黑”节点，多余的一个“黑”属性移到x的父节点中，即x的父节点多出了一个黑属性(若x的父节点原先是“黑”，则此时变成了“黑+黑”；若x的父节点原先时“红”，则此时变成了“红+黑”)。 此时，需要注意的是：所有经过x的分支中黑节点个数没变化；但是，所有经过x的兄弟节点的分支中黑色节点的个数增加了1(因为x的父节点多了一个黑色属性)！为了解决这个问题，我们需要将“所有经过x的兄弟节点的分支中黑色节点的个数减1”即可，那么就可以通过“将x的兄弟节点由黑色变成红色”来实现。
经过上面的步骤(将x的兄弟节点设为红色)，多余的一个颜色属性(黑色)已经跑到x的父节点中。我们需要将x的父节点设为“新的x节点”进行处理。若“新的x节点”是“黑+红”，直接将“新的x节点”设为黑色，即可完全解决该问题；若“新的x节点”是“黑+黑”，则需要对“新的x节点”进行进一步处理。
如下图2：
image.png
网友评论