RB-tree(红黑树)

1、概要

红黑树是一种自平衡的二叉搜索树，它在插入、删除和查找通过一定的规则可以把时间复杂度控制在O(log n)内。红黑树广泛应用域各种场景，如C++的map和set底层实现等。

红黑树不仅是个二叉搜索树，而且必须满足以下性质：

1. 每个节点不是红色就是黑色
2. 根节点为黑色
3. 空节点（叶子节点）都是黑色的
4. 不能有连续的红色节点，如果节点为红色，其子节点必须为黑
5. 任一节点至NULL（树尾端）的任何路径，所含之黑节点数目必须相同

根据以上规则有以下推论：

1. 根据规则4，新增节点必须为红。
2. 根据规则3，新增节点之父节点必须为黑，当新节点根据二叉搜索树的规则到达其插入点，却未能符合上述条件时，就必须调整颜色并旋转。

2、优点

对于二叉搜索树，如果插入的数据是随机的，那么它就是接近平衡的二叉树，平衡的二叉树，它的操作效率（查询，插入，删除）效率较高，时间复杂度是O（logN）。但是可能会出现一种极端的情况，那就是插入的数据是有序的（递增或者递减），那么所有的节点都会在根节点的右侧或左侧，此时，二叉搜索树就变为了一个链表，它的操作效率就降低了，时间复杂度为O(N)，所以可以认为二叉搜索树的时间复杂度介于O（logN）和O(N)之间，视情况而定。那么为了应对这种极端情况，红黑树就出现了，它是具备了某些特性的二叉搜索树，能解决非平衡树问题，红黑树是一种接近平衡的二叉树（说它是接近平衡因为它并没有像AVL树的平衡因子的概念，它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构，进而提升整体的性能，并没有严格的卡定某个平衡因子来维持绝对平衡）。

2、插入节点

场景1：插入节点的父节点为黑色（叔父节点颜色任意）

如果我们想插入元素5，那么会作为10的左子树插入进去。

由于10是黑节点，5是红节点，故不会影响红黑树的平衡。

所以，当插入节点的父节点是黑色时，直接插入无需自平衡

场景2：插入节点的父节点为红色（且叔父节点也为红）

根据性质2—> 红色节点不能相连，故祖父节点必为黑色。

如果我们想插入元素80，那么会作为60的右子树插入进入。

由于其节点颜色和父节点及其叔父节点颜色都为红色，故需要做出调整。

1. 将父节点与叔父节点 和 祖父节点交换颜色（即祖父节点变为红色，父节点和祖父节点变为黑色）
2. 将祖父节点设置为当前节点，继续进行后续处理。

场景3：插入节点的父节点为红（且叔父节点为黑）

此时有两种情况（祖、父、插入节点是否在一条直线）：

1. 祖父节点、父节点和插入节点在一条直线上（即LL型或者RR型）
2. 不在一条直线上（即LR型或RL型）

第一种情况

若要插入100，则会作为80的右子树插入其中，此时祖父节点（60）父节点（80）和插入节点（100）都在一条直线

此时的处理如下：

1. 交换父节点和祖父节点的颜色（即父节点变为黑，祖父节点变红）
2. 对父节点和祖父节点进行旋转

第二种情况

若要插入8，则会作为5的右子树插入，此时祖父节点10父节点5和插入节点8不在一条直线

此时的处理如下：

1. 插入节点和父节点进行旋转（大白话就是让三个节点在一条直线上）

2. 此时就和上一条情况一样了，交换父节点和祖父节点的颜色
3. 父节点8和祖父节点10进行旋转

3、删除节点

场景1：删除单个红节点

所谓单个红节点指的是此节点为红色且左右孩子都为空

比如下图的5，10，60，100都是单个红节点

如果我们这里要删除10，直接删除

场景2：删除带有一个子节点的节点

如果一个节点A其中一个孩子为空，另一个孩子是单独的节点B（其左右孩子为空），那么能否推导出这两个节点的颜色？

答案是可以的。节点A为黑色，B为红色。

如果是其他答案，那么就违反了性质5

如图：这里的8就是一个带有一个子节点的节点

若要删除8，操作步骤如下：

1. 将5替换到元素8，只复制值，不复制元素
2. 在删除孩子节点5。

场景3：删除带有2个子节点的节点

假设要删除节点S，找到其左子树最靠右的节点G，用该节点值替换S，并根据节点G的情况进行删除。

场景4：删除单个黑节点

这里的单个黑节点指的是，黑节点的左右子树为空

在这里，为方便讨论，做出如下代名：

要删除的黑色节点为X，父节点为P，X的兄弟节点为B

要根据兄弟节点B的颜色和B是否有有红色的孩子进行分组讨论

场景4.1 兄弟节点为黑色

为了方便理解，在这里提出几个概念：

1. 若兄弟节点B有红色孩子节点，称之为侄子节点S
2. 若节点X的方向与S的方向相反，称为对侄红。
3. 若方向一致，称为顺侄红

​ 这里的节点方向指的是节点对于其父节点是左孩子还是右孩子。

如图：若要删除25，25对于其父节点50为左节点，那么的60为顺侄红，100为对侄红

​ 在兄弟节点为黑色的前提下，根据是否有对侄红和顺侄红分成3种情况进行讨论：

场景：4.1.1 兄黑对侄红

如图，我若想要删去，元素12那么符合兄黑对侄红的情况。

具体操作步骤如下：

1. 删去元素12

2. 兄弟节点B和父节点P进行旋转（父兄旋转）

3. 侄子节点和父节点与兄弟节点交换颜色（之后按照父红兄弟黑处理）

场景：4.1.2 兄黑顺侄红

如果要删除25，那么60就是顺侄红

操作步骤如下：

1. 删除25

2. 侄子节点和父节点进行旋转，并对调颜色（其实就是把顺侄红变成对侄红）

3. 接着按照对侄红处理，旋转，对调颜色

场景：4.1.3 兄黑双侄黑

若要删除50，那么就会有兄弟为黑色，两个侄子也为黑色的情况

操作步骤如下：

1. 删除50
2. 交换父亲和兄弟的颜色（父黑兄红）

场景4.2 兄弟节点为红色

若要删除60，兄弟节点为红色。

操作如下：

1. 删除60

2. 兄弟节点与父节点进行旋转，并交换颜色

3. 之后以删除元素的原本所在的那个位置为视角（即24的右子树），观察它的兄弟节点满足删除节点的哪几种情况进行操作（这里为双侄黑，那么就是父变黑，兄变红）

参考文献

https://blog.csdn.net/cy973071263/article/details/122543826

https://www.processon.com/view/link/6550422f54fca5688e143664

1727768583346)]

3. 之后以删除元素的原本所在的那个位置为视角（即24的右子树），观察它的兄弟节点满足删除节点的哪几种情况进行操作（这里为双侄黑，那么就是父变黑，兄变红）

参考文献

https://blog.csdn.net/cy973071263/article/details/122543826

https://www.processon.com/view/link/6550422f54fca5688e143664

https://www.bilibili.com/video/BV18C4y137jn?p=9&vd_source=6d7a9e0fcca5190f6402c992c5a9cdb6