RB-tree(红黑树)
1、概要
红黑树是一种自平衡的二叉搜索树，它在插入、删除和查找通过一定的规则可以把时间复杂度控制在O(log n)内。红黑树广泛应用域各种场景，如C++的map和set底层实现等。
红黑树不仅是个二叉搜索树，而且必须满足以下性质：
- 每个节点不是红色就是黑色
- 根节点为黑色
- 空节点（叶子节点）都是黑色的
- 不能有连续的红色节点，如果节点为红色，其子节点必须为黑
- 任一节点至NULL（树尾端）的任何路径，所含之黑节点数目必须相同
根据以上规则有以下推论：
- 根据规则4，新增节点必须为红。
- 根据规则3，新增节点之父节点必须为黑，当新节点根据二叉搜索树的规则到达其插入点，却未能符合上述条件时，就必须调整颜色并旋转。
2、优点
对于二叉搜索树，如果插入的数据是随机的，那么它就是接近平衡的二叉树，平衡的二叉树，它的操作效率（查询，插入，删除）效率较高，时间复杂度是O（logN）。但是可能会出现一种极端的情况，那就是插入的数据是有序的（递增或者递减），那么所有的节点都会在根节点的右侧或左侧，此时，二叉搜索树就变为了一个链表，它的操作效率就降低了，时间复杂度为O(N)，所以可以认为二叉搜索树的时间复杂度介于O（logN）和O(N)之间，视情况而定。那么为了应对这种极端情况，红黑树就出现了，它是具备了某些特性的二叉搜索树，能解决非平衡树问题，红黑树是一种接近平衡的二叉树（说它是接近平衡因为它并没有像AVL树的平衡因子的概念，它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构，进而提升整体的性能，并没有严格的卡定某个平衡因子来维持绝对平衡）。
2、插入节点
场景1：插入节点的父节点为黑色（叔父节点颜色任意）
如果我们想插入元素5，那么会作为10的左子树插入进去。
由于10是黑节点，5是红节点，故不会影响红黑树的平衡。
所以，当插入节点的父节点是黑色时，直接插入无需自平衡
场景2：插入节点的父节点为红色（且叔父节点也为红）
根据性质2—> 红色节点不能相连，故祖父节点必为黑色。
如果我们想插入元素80，那么会作为60的右子树插入进入。
由于其节点颜色和父节点及其叔父节点颜色都为红色，故需要做出调整。
- 将父节点与叔父节点 和 祖父节点交换颜色（即祖父节点变为红色，父节点和祖父节点变为黑色）
- 将祖父节点设置为当前节点，继续进行后续处理。
场景3：插入节点的父节点为红（且叔父节点为黑）
此时有两种情况（祖、父、插入节点是否在一条直线）：
- 祖父节点、父节点和插入节点在一条直线上（即LL型或者RR型）
- 不在一条直线上（即LR型或RL型）
第一种情况
若要插入100，则会作为80的右子树插入其中，此时祖父节点（60）父节点（80）和插入节点（100）都在一条直线
此时的处理如下：
- 交换父节点和祖父节点的颜色（即父节点变为黑，祖父节点变红）
- 对父节点和祖父节点进行旋转
第二种情况
若要插入8，则会作为5的右子树插入，此时祖父节点10父节点5和插入节点8不在一条直线
此时的处理如下：
- 插入节点和父节点进行旋转（大白话就是让三个节点在一条直线上）
- 此时就和上一条情况一样了，交换父节点和祖父节点的颜色
- 父节点
8和祖父节点10进行旋转
3、删除节点
场景1：删除单个红节点
所谓单个红节点指的是此节点为红色且左右孩子都为空
比如下图的5，10，60，100都是单个红节点
如果我们这里要删除10，直接删除
场景2：删除带有一个子节点的节点
如果一个节点A其中一个孩子为空，另一个孩子是单独的节点B（其左右孩子为空），那么能否推导出这两个节点的颜色？
答案是可以的。节点A为黑色，B为红色。
如果是其他答案，那么就违反了性质5
如图：这里的8就是一个带有一个子节点的节点
若要删除8，操作步骤如下：
- 将
5替换到元素8，只复制值，不复制元素 - 在删除孩子节点
5。
场景3：删除带有2个子节点的节点
假设要删除节点S，找到其左子树最靠右的节点G，用该节点值替换S，并根据节点G的情况进行删除。
场景4：删除单个黑节点
这里的单个黑节点指的是，黑节点的左右子树为空
在这里，为方便讨论，做出如下代名：
要删除的黑色节点为X，父节点为P，X的兄弟节点为B
要根据兄弟节点B的颜色和B是否有有红色的孩子进行分组讨论
场景4.1 兄弟节点为黑色
为了方便理解，在这里提出几个概念：
- 若兄弟节点
B有红色孩子节点，称之为侄子节点S - 若节点
X的方向与S的方向相反，称为对侄红。 - 若方向一致，称为顺侄红
这里的节点方向指的是节点对于其父节点是左孩子还是右孩子。
如图：若要删除25，25对于其父节点50为左节点，那么的60为顺侄红，100为对侄红
在兄弟节点为黑色的前提下，根据是否有对侄红和顺侄红分成3种情况进行讨论：
场景：4.1.1 兄黑对侄红
如图，我若想要删去，元素12那么符合兄黑对侄红的情况。
具体操作步骤如下：
- 删去元素
12
- 兄弟节点
B和父节点P进行旋转（父兄旋转）
- 侄子节点和父节点与兄弟节点交换颜色（之后按照父红兄弟黑处理）
场景：4.1.2 兄黑顺侄红
如果要删除25，那么60就是顺侄红
操作步骤如下：
- 删除
25
- 侄子节点和父节点进行旋转，并对调颜色（其实就是把顺侄红变成对侄红）
- 接着按照对侄红处理，旋转，对调颜色
场景：4.1.3 兄黑双侄黑
若要删除50，那么就会有兄弟为黑色，两个侄子也为黑色的情况
操作步骤如下：
- 删除
50 - 交换父亲和兄弟的颜色（父黑兄红）
场景4.2 兄弟节点为红色
若要删除60，兄弟节点为红色。
操作如下：
- 删除
60
- 兄弟节点与父节点进行旋转，并交换颜色
- 之后以删除元素的原本所在的那个位置为视角（即24的右子树），观察它的兄弟节点满足删除节点的哪几种情况进行操作（这里为双侄黑，那么就是父变黑，兄变红）
参考文献
https://blog.csdn.net/cy973071263/article/details/122543826
https://www.processon.com/view/link/6550422f54fca5688e143664
1727768583346)]
- 之后以删除元素的原本所在的那个位置为视角（即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
标签：场景,删除,侄红,插入,详解,祖父,红黑树,节点,图文 From： https://blog.csdn.net/2404_87273268/article/details/142671498