本篇主要写的是结合之前分析的2-3-4树和红黑树之间的联系分析红黑树的插入删除操作的原理。我刚刚开始学红黑树时在网上找红黑树相关资料大多都是以公式模式的方式说明在特性情况下需要变换旋转哪些节点，但是为什么要怎么旋转里面的原理是什么并没有说明。本篇就主要围绕红黑树和2-3-4树插入时的对比结合我自己的理解来说明红黑树插入时变化的思想。
背景知识
红黑树和2-3-4树的结构对应
在说明插入删除操作之前先结合之前2-3-4树和红黑树之间对比说明一下它们之间的对应关系。
RBTree_Insert1.png
这个对应关系看过前面一篇2-3-4树和红黑树对应关系文章的应该就不难理解。只不过这里4node节点对应的红黑树形态有稳定和不稳定两种状态。怎么理解这个稳定和不稳定状态呢？简单的说稳定的状态当4node节点一般是红黑树在变化完成以后我们能够看到的状态，而不稳定的状态一般都是出现在我们添加时向上递归的时候出现的情况，当出现不稳定状态的4node节点时都需要我们通过变色+旋转来转变为稳定状态。
二叉树的旋转
在分析红黑树插入时会涉及到二叉树的旋转，所以这里就先说明一下旋转的操作逻辑。
先说一下我是怎么记左旋右旋操作的，一句话：左旋左下，右旋右下。什么意思呢？就是说对一个节点左旋以后它会向左下移动，而当一个节点右旋以后它会向右下移动。至于左旋以后右子树的左子和右旋时右子树的左子变化逻辑可以看下图来理解。
左旋左下，右子树的左子变化逻辑：
RBTree_LeftRotate.png
右旋右下，左子树的右子变化逻辑：
RBTree_RightRotate.png
上面记录的是我自己的理解，如果感觉太抽象还是没明白那也可以去百度谷歌一下，网上讲这个的资料还是挺多的。
红黑树的局部调整
之前说了红黑树对应的2-3-4树4node的情况右两种，一种是稳定状态一种是不稳定状态，而不稳定状态可以通过变色+旋转来变为稳定状态，那具体是怎么个旋转变色。很简单如下图所示：
RBTree_Fixed1.png
RBTree_Fixed2.png
而红黑树在插入时全都是围绕2node 3node 4node之间的转化来进行的，本质上和2-3-4树是一样的。至于这里的不稳定状态变成稳定状态也是为了红黑树在执行下一步操作时维护之前提到的不能有连续两个红色节点相连的规则，以及保证红黑树相对平衡的高度而进行的。
红黑树的插入
红黑树的插入是在搜索二叉树的插入基础上再对树进行变换让树保持相对平衡来完成的。在我自己学习红黑树插入操作时有部分网上资料是根据2-3树来对红黑树插入时各个状态对比说明的，感觉也有一些复杂需要经过几次的变换（需要对红黑树转换成左倾红黑树再转换成2-3）。我这里就结合两种说明，先根据大部分资料中提到的规则来变换，再对这些变换的核心思想通过和2-3-4树的对比来加以说明。
首先这里需要明确的是红黑树在插入时，新的节点永远都是红色的。从红黑树的角度上说明因为红黑树中插入红色节点才不会让红黑树的结构发生变化（所有路径黑色节点数不发生变化）。从2-3-4树的角度上看插入节点为红色的意思就是新的节点永远都是第一时间想着“并入”到指定的节点之中，这和2-3-4树的思想是一致的。
首先分析红黑树插入节点时最简单的情况，也就是被插入的新节点的父节点为黑色，这种情况从2-3-4树的角度上可以理解成新节点直接被“并入”到老节点之中，结构没有发生变化，自然也不需要什么操作。从红黑树的角度上来讲，向黑色节点下面插入红色子节点自然不会影响红黑树中的任一一个性质（没有连续红色节点，黑色节点数也没有发生变化）。这种情况的具体操作逻辑如下图：
RBTree_insert_detail_0.png
如图，这就是红黑树中插入时最简单的情况，下面将会继续分情况说明插入时变换的操作以及操作对应的2-3-4树的比较。
情况一
状态：
- 新插入节点的父节点为红色；
- 新插入节点的祖父的另外一个子节点（叔叔节点）也为红色。
操作：
- 将新插入节点的父节点从红色染成黑色；
- 将新插入节点的祖父的另外一个子节点（叔叔节点）从红色染成黑色；
- 将新插入节点的祖父节点从黑色染成红色；
理解：
这一系列操作看着只有一顿变色，也没有对树进行旋转，那它的这一顿变色究竟有什么意义？先整理一下在操作变色以前树的结构是怎么样的一种情况。
RBTree_insert_detail_1ex.png
上图就是当前情况一的红黑树状态，新插入的节点为“40”。接下来根据情况一对应的操作看看变换以后红黑树的状态，以及变换前后它们和2-3-4树之间的关系。
RBTree_insert_detail_2ex.png
（注：上图已经把叶子节点都去掉了，因为叶子节点对分析没有什么帮助，而且图画起来也比较麻烦。另外红黑树转2-3-4树时也只做了对分析有关的一部分变换。后面的图也会去掉叶子节点来分析）
如上图【步骤1】，根据上述规则变换以后父节点“25”，叔叔节点“35”将都变成黑色，而祖父节点“30”变成红色；如果只根据【步骤1】很难看出红黑树经过颜色变化到底发生了什么情况，那根据变化前后红黑树对应的2-3-4树来一起分析。
根据上图【步骤2】结合之前红黑树和2-3-4树对应转换关系，红节点向上连接的线为红线，红线连接的节点可以组成一个node，那么可以看出在变化前节点“25”，“30”，“35”形成的是一个4node。而这个时候向红黑树新插入节点“40”的操作也就等同于向“25”，“30”，“35”组成的4node中插入一个节点“40”。
如图【步骤4】在向4node中插入节点“40”后会发生“进位”（在2-3-4中向4node中插入节点的一系列的操作在前面一片文章中已经做了介绍，如果有一些遗忘的可以返回去再看看），而被“进位”的是节点“30”。那么当前可以理解为被“进位”的节点“30”就是一个新插入的节点了。
这里为什么可以把进位的节点理解成一个新插入的节点？从两个角度来分析：
首先从红黑树的角度理解，通过变化颜色（就是上述对新插入节点的父节点和叔叔节点的变色）让以节点“30”为根节点的子树中黑色节点的个数和变化颜色以前保持一致，那么自然将以节点“30”为根的子树被插入到它的父亲节点下面后，黑色节点到数量也不会发生变化，而这个时候如果出现一些不符合红黑树要求的情况，就需要按照情况来分析解决，怎么解决？就和一个新节点插入时的解决方案一样。因此这里可以理解成把节点“30”当作一个新的节点来插入到它的父节点下面，然后再做具体分析。
从2-3-4树的角度理解，被“进位”的那个节点也就是被分裂出去的节点可以被理解为一个新节点来“合并”到它的父亲节点中（分裂完成子树的高度没有发生变化）。当然如果父亲节点也是4node那就继续分裂，这个时候“进位”的就是父亲节点4node中发生进位分裂的那个节点数据了，就这样层层递归直到被分裂节点的数据能够被合并到它的父节点中或到达根节点。
当上面节点“进位”完成，那就继续上述分析下一个步骤——一个新插入的节点被加入到一个黑色的节点下面这一情况，而这种情况通过之前分析可得知不做任何变化，具体逻辑如图【步骤5】。对于2-3-4树来说就是相当于节点“30”被合并到原来的根节点“20”中，形成一个新的3node根节点“20”，“30”。可以发现之前红黑树一顿变换颜色的操作，看着树结构没有发生变化实则已经发生了进位，2-3-4树已经发生了很大的变化，根节点已经从2node变换成3node了。而上述的规则中的变色其实是通过改变节点的颜色间接的改变了连线的颜色从而最终改变了节点的颜色；
总结：
根据上述分析情况一变色操作即可以理解成一种“进位”，将原本由父，祖父，叔叔组成的4node进行“进位”以后再做添加。
思考：
上面描述的情况其实只是其中的一种情况。还有一种情况，就是当前添加节点的祖父节点的父节点是红色的，那通过上述操作以后祖父节点变成红色了）那这时祖父节点和祖父的父节点不就形成了两个红色的节点了？那就不符合红黑树的规则了。而出现这种情况又需要怎么变换？这个时候就涉及到下面要分析的情况二了。
情况二
状态：
- 当前新插入节点的父节点是祖父节点的右子树；
- 当前新插入节点是父亲节点的右子；
- 新插入节点的父节点是红色；
- 新插入节点的祖父节点的另外一个子节点（叔叔节点）是黑色；
操作：
- 将新插入节点的父节点从红色设为黑色；
- 将新插入的祖父节点从黑色设为红色；
- 以祖父节点为支点左旋
理解：
情况二看着条件和操作感觉非常的复杂一会儿要变色一会儿要旋转，不仅要操作父节点还要操作祖父节点。还是一样先上图看看具体是什么情况。
RBTree_insert_detail_3ex.png
这里我顺带的把情况二出现的其中一种场景也画了一下，为了一起把分析情况一时出现的另外一种情况也一起分析了（本质上都是情况二）。如图，根据情况一的分析中我们在变色完成以后即可以把进位的节点“35”理解成一个新插入的节点。这个时候就已经全部满足上述情况二中状态描述的情况了，也就是出现来两个连续的红色节点。
这里我们先不急着变化，先看一下情况二的结构。
RBTree_insert_detail_4ex.png
这个时候出现了不稳定4node。在分析插入操作之前我们已经分析了红黑树中出现不稳定4node的时候需要怎么旋转，这里再重新回顾一下。
RBTree_insert_detail_5.png
而具体应用在刚刚的例子中就是如下
RBTree_insert_detail_6.png
好了现在回过头来看看，是不是我们之前把不稳定的4node转为稳定4node的过程就是情况二操作的描述过程。
总结：
情况二中一系列的描述以及操作总结起来其实就是将一个不稳定的4node状态的红黑树转化成一个稳定的4node状态节点。因此这里我也极其不建议去记当前的情况和面对当前情况需要做的变换操作第一步第二步第三步等等，我们只需要知道在什么状态下我们需要让它变成什么状态（如：“不稳定状态”变为“稳定状态”）。
情况三
情况三其实和情况二的本质是一样的，这里只是多出一步将“规则”的4node整理成“规则”的4node。这里引入一个“规则”，“不规则”这么两个概念，那就先说明一下什么是“规则”的4node，就是黑节点连接的两个红色节点在一条直接上，或者两个红色节点位于黑色节点的两边。我们上述说的都是规则的4node（虽然它们有一些是不稳定）。而不规则的呢？如下图：（基于不稳定4node，类似一个左右箭头的形状）
RBTree_insert_detail_7.png
上图就是不规则的4node状态。那怎么形成规则（不稳定）的4node？只要旋转一下就可以了，具体如下图：
RBTree_insert_detail_8.png
好了了解了怎么把不规则4node转成规则（不稳定）的4node以后就可以继续分析情况三了。
（注：上述的“规则”，“不规则”完全是个人的理解，不是官方的定义，是我自己定义的名称）
状态：
- 当前插入节点的父节点是祖父节点的右子树；
- 当前新插入节点是父亲节点的左子；
- 新插入节点的父节点是红色；
- 新插入节点的祖父节点的另外一个子节点（叔叔节点）是黑色；
操作：
- 将新插入节点的父节点右旋，并将父亲节点定义为新插入节点
- 将新插入节点的父节点从红色设为黑色；
- 将新插入的祖父节点从黑色设为红色；
- 以祖父节点为支点左旋
理解：
仔细观察状态都只和情况二有少许的不同，直接看上面的描述很难明白是怎么回事，那就继续用图片来说明吧。
RBTree_insert_detail_9.png
仍然继续刚刚的那个例子但是有稍作修改，这里把原来的节点“12”拿掉了这样节点“15”的左子就变成了一个黑色的NIL节点，然后继续往这个红黑树中插入一个大小为“16”的节点。这样就是当前分析的情况三了。是不是非常像情况二的样子（如果插入的节点大小为“19”那就是情况二了）。仔细看这里边是不是存在一个不规则的4node。而看到不规则的4node在做变换以前首先就需要通过树的旋转让它成为一个规则的4node。因此具体操作如下：
RBTree_remove_detail_10.png
当得到一个规则的4node时，接下来你根据上述操作会发现其实和情况二的操作是一样的。这里我就不具体再做说明了，不懂的可以回到情况二对比着看看，下面直接放个图：
RBTree_insert_detail_11.png
总结：
情况三本质上其实就是情况二的另一种状态，多出的一步其实就是让“不规则”的4node转换成“规则”的4node，剩下的逻辑就是得到一个不稳定的4node，然后通过变色旋转得到一个稳定的4node。这里的转换因为都是并入节点且变色旋转都是为了维护红黑树的性质，本质就是为了下次插入（或删除）做好准备，而这里对应够2-3-4树其实结构上是没有发生变化的（没有发生进位）。
红黑树插入总结
通过红黑树和2-3-4树对比分析可以总结出红黑树，在插入时如果发生“进位”，则是通过变色来完成节点数据的分裂，而如果是并入操作，则是通过将“不规则”转为“规则”4node，而“规则”4node不稳定状态通过旋转变色变成稳定4node状态。其实核心只要记住一句话“变色分裂，不规则转规则，不稳定转稳定”，并且记住那些基础的不稳定以及不规则形状的特征以及变换方法就可以很简单的记忆红黑树插入时的操作了。这也是为什么我在讲插入之前先说明一下红黑树局部调整的方法，因为插入操作的逻辑基本都是围绕这个局部调整方法（不稳定转稳定）做出变化的。
对红黑树删除的分析因为篇幅原因就放到后面一篇来讲解来。如果对上述分析说明有什么疑问的或者有什么建议的都可以留言，大家一起交流学习。
网友评论