红黑树，非常经典的数据结构，主要用于一些容器中，比如C++语言中的map、Java语言中的TreeMap（后面会写源码分析博客）。红黑树能保持高效的查找，一般取时间复杂度为O(log2n)，由于高效，这个结构也比较复杂，所以很多人（包括我自己）都一直搞不懂红黑树到底是怎么插入、删除节点的。此篇博客，博主将图文并茂的一层一层揭开红黑树神秘面纱。
要彻底搞懂红黑树，难度还是比较大的，建议先阅读我之前写的两篇博客做铺垫，数据结构之二叉树、AVL树、红黑树、Trie树、B树、B+树、B*树浅析是通识篇，主要介绍了几种树结构的区别，数据结构之二叉搜索树详解（附C++代码实现查找、插入、删除操作）单独介绍二叉搜索树插入、删除操作。（其实红黑树 = 二叉搜索树 + 弱平衡）
数据结构之红黑树
一、红黑树概述
1、什么是红黑树？
红黑树是一棵二叉搜索树，并且这棵树实现了弱平衡（严格的平衡是对于树中任意节点的左右子树高度差不超过1）。弱平衡是指任意节点到到其子树中的叶节点所经过的黑色节点数相同，也可以称为黑色平衡（因为严格平衡的二叉搜索树AVL，维护成本太高，所以退而求其次）。
2、红黑树的五大特性
红黑树的五大特性：
1、节点是红色或者是黑色
2、根节点是黑色
3、每个叶节点（NIL或空节点）是黑色
4、每个红色节点的两个子节点都是黑色的
5、任意节点到其子树中的叶节点（NIL节点）所经过的黑色节点数相同（黑高相同）
红黑树引入了NIL节点，用于填充节点的左或右为空的位置，因此红黑树中的叶节点特指NIL节点。
一说定义，博客的画风瞬间变得枯燥起来了，可能有些小伙伴已经开始有抵触情绪的。这些特征你可以不用记住，后面用到的时候我会反复提出来的。
3、为什么要引入红黑树
还记不记得在博客 数据结构之二叉搜索树详解（附C++代码实现查找、插入、删除操作） 中使用二叉搜索树遇到的插入有序递增序列退化成链表的缺陷。
如果不引入平衡的概念，这种普通的二叉搜索树的效率将大大降低。但是引入强平衡（树中任意节点的左右子树高度差不超过1），形如AVL树，树的维护成本太高。为此Rudolf Bayer发明了一种带颜色标记的二叉搜索树即红黑树，此树弱平衡，任意节点到其子树中的叶节点所经过的黑色节点数相同。
(后面介绍需要用到)
二、红黑树相关操作
红黑树看起来挺简单的，不就是给每个节点都标上颜色么。但是实际维护还是比较复杂的，比如删除了一个节点如何调整？新增了一个节点标什么颜色？插入后树要进行怎样的调整？
1、节点旋转
为了调整红黑树的平衡，引入了两种旋转操作。具体过程请看图。
①、左旋
左旋，将旋转节点B放到它的父节点A的位置，将父节点A置为旋转节点B的左子树，然后将旋转节点B的左子树放到父节点A的右子节点位置。（节点A、B为轴）
②、右旋
右旋，将旋转节点B放到它的父节点A的位置，将父节点A置为旋转节点B的右子树，然后将旋转节点B的右子树放到父节点A的左子节点位置。（节点A、B为轴）
③、旋转的意义是什么？
大家看到这里要思考一个问题，这种旋转是否破坏了二叉搜索树的特性（左 < 父 < 右）？或者说是我们进行旋转的意义是什么？
以上图左旋为例，在进行旋转前，根据二叉搜索树的特性，A的左子树中任意节点值 < 节点A的值 < B的左子树中任意节点的值 < 节点B的值 < B的右子树中任意节点的值 。那么你对旋转后的树进行中序遍历看看得到的序列是什么，正好就是[A的左子树中任意节点值, 节点A的值 , B的左子树中任意节点的值, 节点B的值, B的右子树中任意节点的值]，也就是说，旋转不会破坏二叉搜索树的结构特性，只是让二叉搜索树更加平衡。
2、查找节点
查找节点是红黑树三大操作中最为简单的操作，因为红黑树是一棵特殊的二叉搜索树，所以按照二叉搜索树的查找方式查找即可（二叉搜索树特征，左子树中任意节点的值 < 父节点的值 < 右子树中任意节点的值）。查找伪代码：
root 红黑树根，target 需要查找的value
while root != NULL
if root->value == target
// 查找成功
break
else if root->value > target
// 二叉搜索树 左子树任意节点.value < 根.value < 右子树任意节点.value
// 根.value > target,则target只可能存在左子树中
root = root->left
else
// 二叉搜索树 左子树任意节点.value < 根.value < 右子树任意节点.value
// 根.value < target,则target只可能存在右子树中
root = root->right
// root == NULL，则说明未找到
return root
红黑树中元素查找示例图解：
红黑树中插入节点是稍微复杂一点点的操作，请保证前面的都消化完毕再继续阅读。
3、插入节点
有些博客上来就划分各种情况，但往往效果差强人意，现在请跟着博主的思路来彻底理解红黑树的插入细节。
①、如何寻找插入的位置？
我们首先简单回顾下前文在红黑树中的查找操作，如果target < root.value，则target只可能出现在root.left子树（若left子树为空，则树中不存在target），如果target > root.value，则target只可能出现在root.right子树（若right子树为空，则树中不存在target）。（如果刚看过就忘记了，再返回去看一遍吧，你的看的太粗了。。。）
插入位置寻找与之相似，如果target < root.value，则target只可能插入在root.left子树（当left子树为空，那就插入在root.left的位置），如果target > root.value，则target只可能插入在root.right子树（当right子树为空，那就插入在root.right的位置）。
②、插入的节点标什么颜色？
寻找到插入的位置后，插入的节点标什么颜色？
至于为什么，暂且不追究，等你看完插入后调整就知道了。我们现在来看看插入节点一律标红色会不会引发什么问题。（需要翻前文看看红黑树的五大性质）
1、如果这棵红黑树是空树，我们插入节点肯定是做为根，插入节点标红色违反了性质2（根节点必须是黑色）
2、如果插入节点的父节点是红色，插入节点标红色违反了性质4（每个红色节点的左、右子节点必定是黑色！）
插入的节点标红色有没有可能违反性质5？（假设当前标红色没有违反性质2、4，即插入的节点存在父节点，并且颜色是黑色）
答案是不会！插入节点存在黑色父节点，一共有四种情况，分别如下：
可以看出插入节点标红色如果没违反性质2（根节点必须是黑色）、性质4（每个红色节点的左、右子节点必定是黑色！）就不会违反性质5（任意节点到其子树中的叶节点（NIL节点）所经过的黑色节点数相同（黑高相同））。
可能有部分小伙伴疑问插入节点的兄弟节点为啥都是红色的，不能是黑色么，是不是还有两种情况呢？这是典型的不理解五大性质的特征，如果你觉得还有其他任何可能性，建议手动画一画，然后套一套五大性质，看看符不符合！
③、插入节点后如何调整？（旋转or变色）
解决了寻找插入位置、插入节点标色的问题，下面调整则是插入节点的重头戏了。假设经过前面两步，我们已经插入了节点到指定的位置，现在做单独的结构调整。
a、插入节点前是空树
根据前面的两个步骤，我们得到一棵根节点为红色为红黑树，此时违背了性质2（根节点一定是黑色节点）。
：将插入节点由红色修改为黑色。
b、插入节点的父节点是黑色
此种情况不需要进行任何调整，插入后不违背任何性质。
肯定有小伙伴会类推下去，插入节点的父节点是黑色（并且插入前父节点存在两个子节点）如何调整。如果你确实是真么想的，恭喜你，你的红黑树查找插入节点位置还没看懂哦。如果插入节点的父节点在插入前就存在两个子节点，那么插入节点的插入位置必定是在左、右子树中的一个啊！！！
c、插入节点的父节点是红色、叔父节点是红色
此种情况下，祖父节点必定是黑色，根据性质4（红色节点的两个子节点必定是黑色）。并且还需要分出两种情况。
c1、祖父节点是根节点
：将父节点、叔父节点标成黑色。
c2、祖父节点不是根节点
：将父节点、叔父节点标成黑色，并且将祖父节点颜色标成红色。（这里的祖父节点不是根，也就是当前树一棵子树。子树中黑高不能增加、减少，插入前祖父节点为黑色、NIL节点为黑色，黑高（祖父节点到NIL节点路径中黑色节点个数）为2。修改颜色后，黑高仍然是2！）
d、插入节点的父节点是红色、叔父节点是黑色
在插入节点是黑节点的时候，我们只需要考虑当前子树，但是当插入节点的父节点是红色时，我们需要考虑叔父节点的颜色。
如果插入节点的父节点是红色、叔父节点是黑色，根据性质4（红色节点必须有两个黑色的子节点），可知插入节点的祖父节点必定是黑色的。并且由叔父节点必定是NIL节点，否则会违背性质5（任意节点到其所有叶节点NIL节点所经过的黑色节点数相同）。
此时根据父节点、叔父节点在祖父节点的相对位置，可分为两种情况。
d1、父节点在祖父节点左侧，叔父节点在祖父节点右侧
：
如果插入节点插在父节点的左侧，以父节点-祖父节点为轴进行右旋，最后将原父节点与原祖父节点的颜色进行互换。
如果插入节点插在父节点的右侧，先以父节点-插入节点为轴进行左旋，再以插入节点-原祖父节点为轴进行右旋，最后将插入节点与原祖父节点的颜色进行互换。
d2、父节点在祖父节点右侧，叔父节点在祖父节点左侧
：
如果插入节点插在父节点的左侧，先以父节点-插入节点为轴进行右旋，再以插入节点-原祖父节点为轴进行左旋，最后将插入节点与原祖父节点的颜色进行互换。
如果插入节点插在父节点的右侧，以父节点-祖父节点为轴进行左旋，最后将原父节点与原祖父节点的颜色进行互换。
如果插入节点的父节点是红色、叔父节点是黑色，并且叔父节点不是NIL节点，则从祖父节点经过父节点到达所有叶节点的路径中，黑色节点的个数至少会比从祖父节点经过叔父节点到达所有叶节点的路径中，黑色节点的个数多1（这句话有些绕，简单说就是经过父节点的路径与经过叔父节点的路径黑高不同），此时违背了性质5，所以这种情况是不合法的。
删除节点是红黑树中最复杂的操作了，务必先理解前面的内容！
4、删除节点
同样在众多博友的博客中上来就划分情况，现在请跟着博主的思路来走，绝对清晰的一批。😂😂 胜利就在前方，大家加油~ 😜😜
①、如何查找需要删除的节点？
相信你看到这个位置，应该了理解红黑树的节点查找，类似二分查找，不断缩小查找子树的空间。（前面已经介绍过了红黑树的节点查找，这里就不再赘述了）
②、待删除的节点是否真有必要删除？
经过上面的步骤，我们已经查找到需要删除的节点，现在考虑一个问题，待删除的节点是否真的需要删除？
相信看过我之前二叉搜索树删除操作(链接 → 数据结构之二叉搜索树详解（附C++代码实现查找、插入、删除操作）)实现的，都知道有一种操作替换。因为红黑树仍然是一棵二叉搜索树，所以删除某个节点A必须要把中序遍历序列中节点A的下一个节点B移动到删除的位置，只有这样调整后的树中序遍历仍然是一棵二叉搜索树。
那么我们可以不进行删除操作，直接将节点B的值替换待删除节点A值（注意：只是value替换，节点A的颜色、指针都不能修改！），然后删除节点B。（节点B的left指针指向叶子节点（NIL节点），否则肯定是选择节点B左子树中的节点。）（我们也可以将整棵树中序遍历序列删除节点A的前一个节点进行替换。）
也就说对于删除的节点A，如果它存在非NIL的子节点，此时我们可以选择删除节点A（中序遍历）的前驱节点B或者后继节点C替换，然后删除替换的节点B（或C）。而根据上图的介绍前驱节点B的右子树必定为NIL节点，后继节点C的左子树必定为NIL节点。 这样删除节点的情况就减少了很多。
③、节点删除的调整
有了前两步的基础后，我们现在就可以开始处理删除操作了。（下面只考虑树中存在待删除节点的情况，如果树中查找不到需要删除的value，自然没有删除这一步了）
a、删除节点没有非NIL节点
此种情况是待删除节点A有两个子树，此时没有必要直接删除节点A，我们可以选择待删除节点A的（整棵树中序遍历）前一个节点B（或者（整棵树中序遍历）后一个节点C）的值替换节点A的值，然后转换为删除节点B（或者节点C）。（注意节点B、节点C都一个特征，就是有一个子树为NIL节点，下文有此种情况的删除方法。）（图中没有标颜色说明节点颜色任意，既可以是红色、也可以是黑色。）
b、删除节点只有一个NIL节点
删除节点有一个子节点时NIL节点（可能是左子节点也可能是右子节点），我们只要把非NIL节点的子节点整个替换掉删除节点即可。此种情况根据性质4、5可以确定所有节点，比较好处理。（注意看下图中关于删除节点y必定是黑色节点的说明）
c、删除节点有两个NIL节点
删除节点有两个NIL节点，则删除节点可能是红色或黑色。（注意：删除红色节点并不会影响黑高，可以直接删除。）
因为删除黑色节点会降低子树的黑高，所以此时需要调整树的结构，使之删除后当前子树的黑高不变，或者整个树的黑高都降低1（最坏的情况）。
三、总结
总的来说红黑树 = 二叉搜索树 + 黑高平衡（弱平衡）。插入、删除节点都需要进行相应的调整，使之仍然满足五大性质。
插入的关键是插入节点一律标红色，然后根据父节点、叔父节点的颜色、位置进行不同的调整。
删除节点前，我们先判断删除节点有几个非NIL节点。
如果有两个非NIL节点，将待删除节点A的（整棵树中序遍历）前一个节点B（或者（整棵树中序遍历）后一个节点C）的值替换节点A的值，然后转换为删除节点B（或者节点C）。
如果删除节点只有一个NIL节点，则删除节点必定是黑色（根据性质4、5反推，前文有具体说明），直接删除节点，并且使用非NIL子树替代之前的位置，将非NIL节点的根转换为红色。
如果删除节点有两个NIL节点，当删除节点为红色，直接删除（不会影响黑高），否则删除节点为黑色，此时需要调整树的结构，使之删除后当前子树的黑高不变，或者整个树的黑高都降低1（最坏的情况）
如果归纳的有遗漏或错误，欢迎斧正、交流。
转载：https://blog.csdn.net/qq_41855420/article/details/105596199