首先在分析红黑树删除操作之前先说明一下搜索二叉树中删除一个节点时的一个技巧。当删除节点位与树的内节点时，这个时候可以对这个删除的节点进行替换，替换成一个“离自己最近”的子节点，什么是“离自己最近”的子节点？就是当前节点的左子为根的子树中最大的节点，或者当前节点的右子为根的子树中最小的节点。换句话说就是数值离当前节点相差最小的节点来替代，然后等效的删除这个子节点。具体什么意思呢？文字很难让人理解，直接上图。
RBTree_remove_detail_0.png
如图，当前需要删除的是节点“30”，然后通过遍历左右子节点，取左子节点的右子循环直到最后一个，取右子节点的左子循环到最后一个。如图取到的就是节点“28”和节点“32”。因此这个时候可以用这两个节点来代替节点“30”的删除。那到底谁来代替呢？这里应该都是可以的，在Java中TreeMap的源码中是从右子开始遍历，也就是说用节点“32”来代替，如果没有右子就从左子开始遍历。那找到替代节点以后，接下来的操作就是直接移除代替节点并且把替代节点的数据赋值给原本要删除的节点。当然如果这个替代节点有子节点则直接上移来顶替被删除的替代节点；
RBTree_remove_detail_1.png
具体删除操作就如上图，而红黑树则是在二叉树的删除基础上继续对树结构进行调整达到相对平衡。从上图中也可以发现一个规律，真正被替代删除的节点一定是没有子节点或只有一个子节点的，这个规律在一会儿分析红黑树删除时会有用到。
回到红黑树的删除操作，红黑树的删除操作就是在二叉树的删除操作后面跟上一个调整平衡的操作来保证红黑树的相对平衡。下面分析都是在红黑树删除节点时找到了替代节点以后根据替代节点删除时进行的平衡调整进行分析，具体怎么找替代节点，下面就不再做详细分析了。
首先先说明最简单的一种删除情况，就是在二叉树删除寻找替代节点的基础上定位到最后删除的节点是一个红色的节点，这种情况就可以直接删除不做任何操作。这个很好理解，从红黑树的角度去分析理解，最后通过遍历找到删除节点是红色的，那直接删除也不会对整个树结构造成任何影响，就如同向黑色节点后面添加红色节点一样没有任何问题，也就是说只要不出现连续两个红色节点相连接的情况下插入红色节点时不会对红黑树产生任何影响，当然删除以后所有路径黑色节点数也不会发生变化。从2-3-4树的角度去分析，最后删除的是红色的节点，那意味着删除的是一个多node（3node或者4node）中的一个数据，因此不需要对树做出任何调整。
RBTree_remove_detail_2.png
接下来分析的情况都是当真正删除的节点（替代节点）是黑色节点时的情况。当黑色节点被删除时意味着红黑树将会不再平衡（至少某条或几条路径上黑色节点数量会少1个）。因此需要进行平衡调整，而这个调整的思路通俗的说就是：自己能搞定的自己搞定，自己搞不定问兄弟借，兄弟借不到问父亲借；从这句话中也可以看出删除黑色节点时可能会出现三种情况，我们只要按照顺序来套用就可以顺利的让红黑树右回到平衡；那这句话具体是什么意思？核心就是“借节点”，“自己有多余的节点自己来调整，没有就问兄弟“借节点”来调整平衡，再没有就问父亲“借节点”来调整平衡。至于怎么“借节点”以及各种情况下的具体实现，接下来会按照顺序逐个分析说明；
情况一 “自己能搞定的自己搞定”
什么情况是“自己能搞定的自己搞定”呢？其实之前分析的删除红色节点就是这种情况之一。在找到替代节点以后发现替代节点是红色节点，这时可以把红色节点依附的黑色节点合并看成一个3node，当要删除一个3node节点中的一个数据，自然不需要做过多调整“自己就能搞定”，只要直接移除这个红色的节点就ok了。这个时候3node将会重新变成2node。对2-3-4树或者说红黑树的结构都不会产生影响，具体图例可以参照之前说明删除红色节点情况的那张图来参考分析；
当然另外还有一种就情况就是当删除的是一个黑色节点，但是它有一个红色的子节点。有红色的子节点就说明它也是一个3node（这里不可能是4node，因为被选中替代的节点一定是最多只有一个子节点的节点，这个是在上面分析二叉树删除技巧时总结的规律）。这个时候删除的是黑色的节点，但因为替代节点实质上是一个3node，因此它自己其实是能搞定的，那怎么来搞定？对于2-3-4树其实什么都不需要做，但是对于红黑树为了维护红黑树的那几个准则则就需要如下操作，前面操作和二叉树删除是一样的，首先移除替代节点，然后用替代节点的子节点来顶替替代节点指向它之前的祖父节点，最后是红黑树的调整操作，把原替代节点的子节点从红色染成黑色。具体逻辑参照下图：
RBTree_remove_detail_3.png
接下来继续分析这里为什么需要把红色子节点“35”染黑？对于2-3-4树来说其实没有意义，因为对2-3-4树来说删除仍然只是从3node转换成了2node，在结构上并没有发生什么变化。而对于红黑树来说染黑是为了保证红黑树中黑色节点数不发生变化。从这里也能看出红黑树和2-3-4树的对应关系——单一黑色节点对应2-3-4树的2node；
总结一下，当真正被删除节点（替代节点）是一个3node或者4node中的其中一个节点数据，则这个时候就可以直接删除（删除红色节点的情况）或者删除后再做颜色调整（删除黑色节点的情况）来重新让红黑树达成平衡；
情况二 “自己搞不定问兄弟借”
之前分析的情况都是被删除节点是3node或者4node中的其中一个节点数据的情况。而当被删除节点是一个2node的情况（单一黑色节点，没有子节点）需要怎么操作？这个时候就需要尝试向兄弟节点来借节点了。先说说什么是兄弟节点，兄弟节点就是红黑树中拥有同一个父节点的另一个节点。简单的说就是一个二叉树，同一个父节点的两个子节点，其中一个是自己另一个就是自己的兄弟节点。继续上面的讨论那什么情况可以问兄弟节点成功借到呢？当然是兄弟节点有“多余节点”的情况下了。也就是说兄弟节点是一个3node或者4node（意味着兄弟节点至少有一个红色的子节点），具体兄弟节点可能出现的情况如下图：
RBTree_remove_detail_4.png
兄弟节点为上述三种的情况下就可以被借走节点。接下来就具体分析看看怎么来向兄弟节点借的。
RBTree_remove_detail_5.png
如上图，可以看到被删除节点的兄弟节点是“30”。这里出现了一个特殊情况这个兄弟节点和上面分析的三种情况都不一样？这里从二叉树的角度看“30”节点确实是节点“55”的兄弟节点，但是从红黑树的角度看节点“30”并非是节点“55”的“真正”兄弟节点。首先把这个红黑树转成2-3-4树：
RBTree_remove_detail_6.png
经过转换可以看到”30“节点只是根节点的一个内部节点数据，而这个”35“节点才是真正的兄弟节点。那这种情况怎么才能在红黑树中找到真正的兄弟节点？操作很简单只需要（左右）旋转父亲节点，让父亲节点的两个节点数据颜色对换一下就可以了。在上述情况只需要右旋父亲节点“50”，然后将节点“50”染红，节点“30”染黑。这里不建议强行记住兄弟节点为左子的情况右旋父节点，右子的情况左旋父节点。最好是根据场景去分析目前什么情况需要变成什么情况。如当前情况我们需要找到真正的兄弟节点，就需要等价调整红黑树对应2-3-4树中的3node节点中内节点颜色，怎么调整对换内节点颜色？动手画一下图就很快能想到通过树的左右旋转，染色操作来完成。之前说明添加操作时分析的不规则4node转规则4node这些其实都是一样的道理，不需要具体去记忆规则，只需要知道目标是什么，观察现在怎么样，最后做出一个“守恒操作”（不影响红黑树结构的操作，一般是旋转是加变色）。其实总结一下就是记忆什么情况做出怎么样的“守恒操作”。
根据上述旋转变色以后具体可以得到如下红黑树：
RBTree_remove_detail_7.png
这里我把2-3-4树的对比也放出来了，可以看到这个操作是没有影响2-3-4树的结构的。这里也是为了说明这个等价守恒操作的意义。
继续上面的分析，在上面操作以后找到了需要被删除的节点“55”的真正兄弟节点“35”，这个时候节点“55”作为一个黑色节点被删除势必影响平衡（以节点“50”为根的右子路线上相比左子少1个黑色节点），根据上述描述就需要问兄弟节点借。怎么借？从兄弟节点拿一个不影响平衡的红色节点过来染黑就可以了。为了说明多种情况，把重点需要分析的这块截取出来：
RBTree_remove_detail_8.png
这里把父节点标成“?”是为了一起说明父节点为红或者黑时的两种情况，因为父节点的颜色其实是不影响总体逻辑分析的所以先设为“?”等到具体情况再做分析。好了接下来分析节点“55”是怎么从兄弟节点中借一个红色节点过来的。具体逻辑如下：
- 找真正的兄弟节点（真正的兄弟节点可能不在兄弟位上，如果在则不需要这一步）
- 确认兄弟节点是否需要调整至一条直线上，没有则通过旋转变色调整到一条直线上，然后重新定义兄弟节点（新的兄弟节点为原兄弟节点的子节点），为后续“借”节点做准备（一条直线是为了旋转转移节点方便）
- 染色将要代替原来父节点的节点，染色原父亲节点为黑色代替被删除节点
- 旋转父亲节点
而对应当前场景的具体操作如下：
- 左旋节点“35”
- 将兄弟节点“35”的右子节点“40”染成和节点“?”同色
- 右旋父节点“?”
- 将节点“?”染黑
光描述很抽象，上图看看变化的流程吧。
RBTree_remove_detail_9.png
这里给出了红黑树和2-3-4树的对比图例，对于上述那一系列的操作其实就是为了把节点转移过去。之前说的是从兄弟节点“借”，本质上其实是将原父节点给自己，从兄弟节点拿出一个节点来顶替父节点这种形式来完成借这个操作的。而从2-3-4树的角度来分析，就是合并重新分配的一个过程。我一开始把父节点标成问号，其实是想说明，不论父节点是什么颜色兄弟节点的一个子节点都会成为新的父节点，因此这里就不再需要分情况去判断原父节点红色时新父节点（兄弟节点）要染成什么颜色，只要知道它的目的自然明白其实不需要分析父节点的颜色。这里从红黑树的角度上分析来看，当节点“55”要被删除时，右边明显少了一个黑色节点，因此从父节点中“拿”个节点过来染黑，从兄弟节点中把被删除节点借走的父亲节点“还”给父亲节点，这一“拿”一“还”虽然节点已经发生变化但是颜色是没有变的，简单的说就是被删除节点借父亲节点来顶替，父亲节点再问兄弟节点要一个来顶替父亲节点，最后形成平衡；
注意：这里需要注意的是在Java（JDK 1.8）中红黑树的实现类TreeMap里面实现代码的操作和上面描述的不一致！JDK1.8的操作中当删除节点“35”时，具体操作如下：
- 将兄弟节点“35”染成和节点“?”同色
- 将节点“35”左子节点“33”染成黑色
- 右旋父节点“?”
- 将节点“?”染黑
有什么区别呢？用一次染色来代替旋转；结果是怎么样的呢？
RBTree_remove_detail_10.png
可以看到虽然不影响平衡但是结构发生了变化。原来按照我的理解完成的变化以后兄弟节点只是被“借走”了一个节点，而Java中则是“借走了兄弟节点的两个节点”。当然这种情况只会出现在兄弟节点是4node的情况下。（有兴趣的同学可以对比观察一下这两种删除操作有什么差异优劣）
具体为什么Java中以这种方式来实现删除我也不是很清楚。猜测可能是为了代码的清晰逻辑简单。也就是说只有当兄弟节点的子节点和兄弟节点父节点不在一条直线上的情况下才考虑旋转变色，其它情况只需要变色，来实现兄弟节点这部分的变化；
总结：
从上面的分析可以了解到红黑树在删除时的变换思想。首先要从兄弟节点借节点到前提是被删除节点真正到兄弟节点上有多余节点（红色节点多node）。而这个借节点的过程就是一种转移逻辑如下：
兄弟节点红色子节点 代替 兄弟节点
兄弟节点 代替 父亲节点
父亲节点 代替 被删除节点
核心就是按照上述顺序来完成对删除节点的补充（借节点）。通过这一系列的变色旋转将原本的红色节点变成黑色节点来填补原来黑色节点的缺失。而对于2-3-4树来说只是一种合并再分裂，这里合并再分裂在红黑树上并没很明显的体现。
情况三 “兄弟借不到问父亲借”
这种情况也就是说当前节点是一个2node，当被删除时自己搞不定（没有多余的红色的节点来顶替），这个时候问兄弟节点借，但是兄弟节点恰好也是一个2node，也没有“多余”的节点可以借，这个时候只能问父节点来借节点数据来填补将要删除的黑色节点；
那么简单的总结一下这种情况就是：
- 被删除节点是一个2node
- 被删除节点的兄弟节点是一个2node（兄弟节点的双子都是黑色的或者就没有双子也就是都是叶子节点）
那么继续分析，触发了这种场景的情况下需要怎么操作。很简单只要将兄弟节点染红。怎么理解呢？
从红黑树的角度理解：既然一边一个黑色节点被删除了，当然另外一边为了平衡也需要减少一个黑色节点，最快的方法自然就是将兄弟节点染红。而两边黑色节点个数少1了这个怎么补上就找父节点了，具体父节点是自己就能搞定（自己就是3node 或者 4node）还是说找兄弟节点借（自己2node，兄弟3或4node）又或者继续向祖父节点借（自己和兄弟都是2node）这就得让父节点自己来处理了；
从2-3-4树的角度理解：染红是为了后续向父亲节点借到黑色节点的情况下合并形成3node来弥补黑色节点少1的现状；也就是2-3-4树在删除时的一种合并操作；
RBTree_remove_detail_11.png
如上图：如果删除的是节点“55”这个时候会将兄弟节点染红来保持平衡，但是以问号为根的子树中黑色节点是少1的，所以这个时候需要问父节点“?”借。这里假设我们必然能借到一个黑色节点来使这个子树平衡。那么子树其实就已经调整完成。
第二步，在子树调整完成的基础上，我们只要继续分析父节点“?”的情况就可以了，不再需要关注子树，因为目前的情况是子树会借到一个黑色节点重新保持平衡，而节点“?”将要失去一个黑色节点，因此只要分析节点“?”在将要失去一个黑色节点的情况下去要做出的操作。那么继续分析首先就要清楚节点“?”有哪几种情况了，如下：
RBTree_remove_detail_12.png
ok，这里我们分情况来做讨论
- 节点“?”为2node的情况，这个时候只能把自己“借给”子节点用于合并平衡，那当前节点又处于少一个节点的情况，这个时候就重新回到一开始的准则“自己搞不定问兄弟借，兄弟借不到问父亲借”的情况来。
- 节点“?”为3node的情况，3node有两种情况，但是不论是哪种情况连接着刚刚节点“35”和“55”的必然都是节点“B”，因此只要把节点“B”染黑借给子节点就完事了；
- 节点“?”为4node的情况，4node的情况不论连接节点“35”和“55”的是节点“B”还是节点“C”情况都可以和上面3node一样来处理；
这里也是一种递归思想，当子节点打算从父节点中借黑色节点来达到平衡的前提下，父节点必然将要失去一个黑色节点，这里就可以将父节点重新当作一个将要删除的节点来做分析。考虑到递归可能比较难理解，这里给出一组示例。有红黑树和2-3-4树的对比，基本逻辑和上述是一致的，只要跟着分析一遍相信会清晰很多。
RBTree_remove_detail_14.png
总结：从这里可以看出当删除时向父节点借节点数据时运用到的是一种递归思想；当变完兄弟节点的颜色以后，默认从父节点里面获得一个黑色节点，这个黑色节点可能是父节点自己，也可能是一个3node或者4node的子节点（当然这个子节点必然是红节点）。我们只要把父节点当作是一个将要被删除的节点（马上要被子节点借走）继续做分析就可以了，然后继续根据开始分析的情况以父节点为要删除的节点做分析——父节点自己能搞定的自己搞定，自己搞不定问父节点的兄弟借，父节点的兄弟借不到问祖父借
以上就是个人结合2-3-4树对红黑树删除的理解，有问题或建议可以留言，大家一起交流学习。
网友评论