接上章： B树(多路查找树)

本章主要介绍【红黑树】的性质以及【红黑树】节点的增加和删除操作。是类比B树节点的增加和删除来阐述的。所以看此文前，心中要有B树。😁😁

◼ 红黑树也是一种自平衡的二叉搜索树 ，以前也叫做平衡二叉B树(Symmetric Binary B-tree)。

一、红黑树的性质

◼红黑树必须满足以下 5 条性质

1. 节点是RED或者BLACK
2. 根节点是BLACK
3. 叶子节点(外部节点，空节点)都是BLACK
   (这里的叶子节点，指的是假象出来的节点)
4. RED 节点的子节点都是 BLACK
   4.1 ✓ RED 节点的 parent 都是 BLACK
   4.2 ✓ 从根节点到叶子节点的所有路径上不能有 2 个连续的 RED 节点
5. 从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点

RBTree.jpg

[注意：下面这棵树不是红黑树]

01.jpg

因为不满足红黑树的5条性质中的性质5。
即：从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点

02.JPG

从02图中可以看出，02-图1中所有节点的路径中都包含3个Black节点。
但是这里有个节点为38的路径，到叶子节点包含2个黑色的节点。
所以，这棵树不是红黑树，不满足红黑树的第五条性质。
小结：必须全部满足红黑树的5条性质才可以称之为这是一颗红黑树，缺少任何一条都不是红黑树。

◼红黑树 和 4阶B树(2-3-4树)具有等价性
1.BLACK 节点与它的 RED 子节点融合在一起，形成1个B树节点
2.红黑树的 BLACK 节点个数 与 4阶B树的节点总个数 相等
(只有4阶B树可以与红黑树完美匹配，2-3树 并不能完美匹配 红黑树 的所有情况)

RBTree vs 2-3-4Tree.jpg

因为红黑树中，红黑树的BLACK节点与它的RED子节点融合在一起，形成了一个B树节点。所以，红黑树和2-3-4阶B数排列组合后有以下几种情况：
红黑树的BLACK父节点与它的RED子节点组合：
(这种组合规律还得满足红黑树的5条性质，比如：红节点作为父节点，不满足红黑树性质2，所以满足条件的有以下4中情况：)

① 红黑红 ②黑红 ③红黑 ④黑

03.jpg

二、【二叉搜索树】节点的增加和删除。

◼1.【添加】-【红黑树】节点的添加

新添加的是根节点，直接染成BLACK即可。
在B树种，新添加的节点必定是添加到叶子节点中，也就是必定是在最后一排添加。新添加的节点我们设置为红色(图04中用粉红代替)，这样添加一个红色节点，红黑树的性质中1，2，3，5都满足条件，只有红黑树性质4持质疑态度。

下图是红黑树添加节点的所有情况：

04.jpg

由图可知，一共有12中情况，这12中情况里面，有4中情况直接满足红黑树的性质，因为parent是BLACK，所以无需要再调整红黑树。如下图所示：

06.jpg

所以，目前只剩下8中不满足红黑树的性质4，这8中情况的parent都为RED（Double RED）

07.jpg

好，现在我们目标明确了，一共有8中情况需要修复。我们来一一看下这8中情况：
这8中情况，都是因为不满足红黑树性质4，所以需要修复。

★ 1.1 /1.2 【添加】- 修复红黑树性质4 - LL/RR

◼判断条件：uncle不是RED
① parent染成BLACK ，grand染成RED。
② grand进行单旋转操作。
☆LL:右旋转
☆RR:左旋转

08.jpg

添加节点步骤详细描述如下:
如果此时我们添加节点52，用B树的角度来看，因为B树节点是由一个父黑色和它的红色子节点融合在一起的。
所以，如果节点52想要添加成功，并且满足红黑树的性质，节点52要变成BLACK，节点46要变成RED；让节点50为根节点，节点38指向节点50。------------这个操作其实就是AVL树种的左旋转
相同的道理，节点72要变成BLACK，节点76要变成RED；让节点72为根节点，节点55指向节点72。------------ 这个操作其实就是AVL树种的右旋转

★ 1.3 /1.4 【添加】- 修复红黑树性质4 - LR/RL

uncle不是RED
①. 自己染成BLACK，grand染成RED
②. 进行双旋操作
☆LR: parent 左旋转，grand 右旋转
☆RL: parent 右旋转，grand 左旋转

09.jpg

添加节点步骤详细描述如下:
RL情况：首先，将节点50进行右旋转，然后再对节点46进行左旋转，两次旋转之后，节点48将变成父节点并且染成BLACK，节点46和节点48成为这棵子树的子节点并且染成RED。
LR情况：首先将节点72进行左旋转，然后在对节点76进行右旋转，两次旋转之后，节点74将变成父节点并且染成BLACK，节点74和节点76成为这棵子树的子节点并且染成RED。

到此，我们又解决了4种情况，LL/RR和RL/LR。这四种情况的uncle节点是BLACK，即也就是图010中黑色区域

010.jpg

目前为止，我们还剩余4中情况没有解决，这4中情况就是uncle节点是RED，即也就是图010中红色区域亟待解决。

因为红黑树与2-3-4树完美匹配，在4阶B数中，节点元素个数符合 1 ≤ x ≤ 3，所以在图010中，uncle节点是红色，如果我们添加节点10，在B树种这种现象叫做上溢。
下面就介绍下uncle节点是红色的四种情况，也就是解决上溢现象。

★ 1.5 【添加】- 修复性质4-上溢-LL
在B树中，上溢现象的解决方案是找出一个中间节点向上合并，左右分裂成两个节点。

◼判定条件:uncle 是RED

1. parent、uncle 染成 BLACK
2. grand 向上合并
   ★ 染成 RED，当做是新添加的节点进行处理

◼grand 向上合并时，可能继续发生上溢
◼ 若上溢持续到根节点，只需将根节点染成 BLACK

011.jpg

添加节点步骤详细描述如下:
挑出最中间的向上合并，我们选择节点 25，因为节点 25是节点节点38的子节点。节点 10 、节点 17和节点 33独立成两个B树节点。将节点 17 和节点 33染成黑色。
此时还不算完，我们还需要考虑节点25 向上合并后的情况。这种情况我们可以简化来考虑，节点25 向上合并，那么对于节点38和节点55来说，算是新插入的节点，所以我们可以将节点25 当成新插入的节点来处理。依然满足12中情况(8中需要调整的+4中不需要调整的)。所以把节点25 染成红色，重新执行了一遍新添加节点的逻辑，这里属于一种递归的操作。

★ 1.6 【添加】- 修复性质4-上溢-RR

◼判定条件:uncle 是RED

1. parent、uncle 染成 BLACK

2. grand 向上合并
   ★ 染成 RED，当做是新添加的节点进行处理

   
   
   012.JPG

添加节点步骤详细描述如下:
把节点 36的祖父节点节点 25向上合并，当成新添加的节点。将节点 17和节点 33染成黑色。

★ 1.7 【添加】- 修复性质4-上溢-LR

◼判定条件:uncle 是RED

1. parent、uncle 染成 BLACK
2. grand 向上合并
   ★染成 RED，当做是新添加的节点进行处理

013.JPG

添加节点步骤详细描述如下:
一样的道理，节点 25向上合并，当做新添加的节点；节点 17和节点 33染成黑色。

★ 1.8 【添加】- 修复性质4-上溢-RL

◼判定条件:uncle 是RED

1. parent、uncle 染成 BLACK
2. grand 向上合并
   ★染成 RED，当做是新添加的节点进行处理

014.JPG

添加节点步骤详细描述如下:
同样的道理，节点 25向上合并，当做新添加的节点；节点 17和节点 33染成黑色。

至此，添加节点的12中情况全部处理完毕。
4中情况不用处理；
4中情况uncle节点是黑色；
4中情况uncle节点是红色。(即：B树上溢的情况，只需要parent和uncle染成BLACK，grand向上合并即可)

添加节点的所有情况已经介绍完毕，下面介绍删除节点的情况。首先要知道在B树种，真正被删除的节点都是在最后一层的叶子节点中的。所以在红黑说中想要删除节点，也是在最后一层。如下图所示：

015.jpg

◼2.【红黑树】节点的删除

红黑树中，如果删除的是红色节点的话，没有违背红黑树的性质，所以删除红色节点不需要处理；删除黑色节点违背了红黑树的性质，需要单独处理，删除黑色节点的话又有三种情况需要处理，如下图所示：

016.jpg

◼一、拥有 2 个 RED 子节点的 BLACK 节点
◼二、拥有 1 个 RED 子节点的 BLACK 节点
◼三、BLACK 叶子节点

★ 2.1 【删除】- 拥有 2 个 RED 子节点的 BLACK 节点

步骤分析：
拥有两个RED子节点的BLACK节点，不能直接删除，因为在二叉树中度为2的节点肯定是用前驱或者后继来替代。所以如果删除节点 25，那么也就用前驱节点 17或者后继节点 33来代替。又因为删除红色节点不违背红黑树的性质，所以不需要单独处理。
总结如下：
✓ 不可能被直接删除，因为会找它的子节点替代删除
✓ 因此不用考虑这种情况

通过分析，我们已经PASS掉这一种情况了，也就是说红黑树节点的删除，我们真正需要考虑的就以下两种情况：一、拥有 1 个 RED 子节点的 BLACK 节点 和 二、BLACK 叶子节点。

★ 2.2 【删除】- 拥有 1 个 RED 子节点的 BLACK 节点
删除度为1的节点，子节点【替代】原节点的位置。

◼ 判定条件:用以替代的子节点是 RED
◼将替代的子节点染成BLACK 即可保持红黑树性质

017.JPG

删除节点步骤详细描述如下:
如果要删除黑色节点 46和节点 76。
先从二叉搜索树角度来看，这是删除度为1 的节点，需要用子节点节点 50替代原节点 46的位置；用子节点 76替代原节点 72的位置。
再从B树的角度来看，可直接删除节点 46和节点 76，节点节点 50和节点 72变成黑色，独立成一个单独的B树节点。

这里声明以下，在红黑树中，节点的删除都尽量以BLACK和RED来判断。不要用二叉搜索树的性质来判断。

★ ★ 2.3【删除】- BLACK 叶子节点

★ 2.3.1【删除】- BLACK 叶子节点-sibling为BLACK

删除BLACK叶子节点(sibling为BLACK):
先从二叉搜索树的角度来看，这是删除度为0的节点，直接删除即可。
再从B树的角度来看，这是删除叶子节点，在B树种这种删除操作属于下溢，因为B树种要求一个节点至少存储一个元素。B树下溢的解决方案有两种，一种是兄弟节点可以借元素，一种是兄弟节点不可以借，此时父节点向下合并。

☆2.3.1.1☆ 【删除】- BLACK 叶子节点-sibling为BLACK 并且 兄弟节点可以借元素。

以下三种情况，是兄弟节点可以借元素的，如下图所示：

018.jpg

图中的三种情况都满足以下条件：
①它的兄弟节点是黑色的 ；
②它的兄弟节点有一个/两个红色的子节点。
只有满足这两个条件的这三种情况，才可以借元素。两种情况缺一不可，破坏任何一个条件，都不满足借元素的条件。

◼ 如果 sibling 至少有 1 个 RED 子节点
★进行旋转操作
★旋转之后的中心节点继承 parent 的颜色
★旋转之后的左右节点染为 BLACK

019.jpg

删除节点步骤详细描述如下:
我们要删除节点 88`，这种情况在AVL树中从左到右依次属于LR、LL、LL/LR的旋转情况。

☆2.3.2.2☆ 【删除】- BLACK 叶子节点-sibling为BLACK 但是兄弟节点不可以借元素。

◼ 判定条件:sibling 没有 1 个 RED 子节点
◼ 将 sibling 染成 RED、parent 染成 BLACK 即可修复红黑树性质

◼ 如果 parent 是 BLACK
 会导致parent 也下溢
 这时只需要把 parent 当做被删除的节点处理即可

020.jpg

图1删除节点步骤详细描述如下:
父节点是红色，删除 节点88，将节点80下来和节点76合并。节点80变成BLACK，节点76变成红色。节点80和节点76合并成一个B树节点。

图2删除节点步骤详细描述如下:
父节点是黑色并且兄弟节点也是黑色的删除情况，直接按照被删除节点处理即可。

★2.3.2【删除】- BLACK 叶子节点-sibling为RED

021.jpg

由图可知，我们删除节点88，但是节点76不是节点88的兄弟，节点76是节点88的侄子。节点88的兄弟是节点55。
这里，首先我们要把节点76变成节点88的兄弟，一旦节点节点76变成节点88的兄弟，我们就又回到了 2.3.1【删除】- BLACK 叶子节点-sibling为BLACK。

如何把节点76变成节点88的兄弟呢？😅

解决方案：依旧是旋转，我们只需要把这种情况当成LL的情况即可，进行右旋转。

022.jpg

好，这次，节点的删除所有情况也已经阐述完毕。

知识点小结如下图所示：

023.png

红黑树的学习，源自于腾讯课堂小码哥的《恋上数据结构与算法》，感觉这个讲的超级棒，目前看过的最详细和最全的红黑树资料，值得学习和拥有。😁😁