从红黑树中删除节点不是一件容易的事，因此将它分成几部分并分别考虑每种情况是有意义的。
cartoonbank.ru
在上一篇文章中，我们研究了形成红黑搜索树的规则，并考虑了添加元素时进行平衡的情况。
现在让我们谈谈删除项目。
以这棵红黑树为例：
回想一下，红黑树的主要属性是每个节点左右两侧的黑色高度相同。因此，在图中，我们将在每个节点旁边指示黑色高度的值，以便在每个阶段可以检查其稳定性。
分而治之
乍一看，从红黑树中删除元素并不是一件容易的事，因此我建议将其分为几个部分，并分别考虑。
首先，让我们将任务分为两类：
- 删除的节点的颜色：K或H
- 子节点数：2、1、0
结果，我们得到6个选项的矩阵：K2，Ch2，K1，Ch1，K0，Ch0。
对于每个选项，将指示树的相应节点。
让我们考虑每个选项的删除过程。
K2-有两个孩子的红色结
删除具有两个子节点的节点的任务被简化为删除具有一个或零个子节点的节点的任务。
为此，您需要找到小于或大于已删除元素的最接近元素并将其交换。
请注意，在交换元素时，您只需要更改节点中的值，并保持颜色不变，以免破坏树形结构且不更改黑色高度。
交换之后，您需要从新位置删除该项目。它要么是左侧分支中最右侧的元素（左侧最大），要么是右侧最左侧的元素（右侧最小），在任何情况下，左侧或右侧都不会有一个子代。因此，删除具有2个孩子的节点的任务简化为删除具有1个或0个孩子的元素的任务：
- K2 => K1或K0
CH2-有两个孩子的黑结
与前面的情况类似，我们将给出一个删除黑色节点16的示例。
如您所见，在交换之后，任务被简化为删除具有一个子元素的元素：
- Ch2 => Ch1或Ch0
K1-带着一个孩子的红色结
如果红色节点没有一个子节点，则代替它的是黑色NIL元素，红色节点的黑色高度为1。因此，另一方面，黑色高度也应为1。但是，由于红色节点不能有红色子节点，因此颜色，那么他的另一个孩子应该是黑色的。由于黑色高度必须为1，因此只能是黑色NIL元素，因为在普通黑色元素的情况下，高度会更高。
因此，不会发生K1案件。
CH1-带着一个孩子的黑结
如果黑色元素没有一个子元素，则有一个黑色的NIL元素，其黑色高度为1。因此，另一侧应该有一个没有子元素的红色节点。要删除此类元素，只需将红色元素的值传输到黑色节点即可，同时保留黑色高度。
K0-没有孩子的红色结
最简单的情况。我们只需删除该元素，将其替换为NIL引用：
删除红色元素不会更改黑色高度。
CH0-没有孩子的黑结
删除没有子节点的黑色节点也非常简单：我们将其替换为对NIL的引用。
您认为这几乎是全部吗？哈哈，六次。
删除黑色元素后，子树的黑色高度会发生变化，您需要为其父级平衡它。
图中删除的元素用x表示，其高度-h。当我们刚开始平衡时，h = 1，但是随着递归调用的增加，它会增加。
为了确定起见，让我们确定删除的元素是正确的子元素。去除后，其高度降低并变为h。这意味着左儿子的身高保持h + 1。我们需要对齐左右子树的高度，并使它们等于h + 1。
我建议再次将任务分为几个部分我们有什么选择？
父级可以是红色或黑色。左儿子也可以是黑色或红色。正确的儿子永远是黑人-从那里开始，我们搬迁后便开始平衡。
有6种不同的情况需要考虑：
- KCH1和KCH2-父级为红色，左子级为黑色。
- CHK3和CHK4-父级为黑色，左子级为红色。
- HH5和HH6-父母是黑人，左孩子是黑人。
我们将积蓄耐心和爆米花，未来最有趣，最神秘的地方。
KCH1-父红色，左孩子为黑色，子孙为黑色
只要有红色节点，就可以移动和/或重新着色它们以恢复黑色高度的平衡。在这种情况下，我们可以将红色从父级降低到左子级，从而对齐父级的黑色高度：
确保从图中再次检查是否保留了节点a和b的黑色高度，并且整个子树的高度已变得相同并等于h + 1。
KCH2-父代为红色，左子代为黑色，左孙子为红色。
在这种情况下，仅重画是不够的。我们需要在节点3-7之间向右微转。结果，我们将能够将右侧子树的高度增加到h + 1：
绿色节点表示它可以是黑色或红色。
注意。如果节点“ 1”为黑色，而“ c”为红色，则问题可以归结为变量HH5。
CHK3-父母是黑人，左儿子是红色，右孙子有黑人曾孙
拥有黑色曾孙可让您重绘红色孙子，并向右转3-7一点，将其发送到右侧子树，不要问为什么，只需信任并检查黑色高度是否稳定：
请注意，红色节点5不会增加黑色高度。
CHK4-父母是黑人，左儿子是红色，右孙子有红色曾孙
在红色森林的更深处，有更多的黑色柴火，而红色的柴火则更少，也就是说，通过对红色节点重新着色，可以稳定黑色的高度。
在这种情况下，您需要左转大弯，其中包括两个小转弯5-3和5-7。节点b的颜色从红色更改为黑色，因此其高度增加了1。请确保黑色高度稳定。
HCH5-父母是黑人，左儿子是黑人，右红色孙子。
子树中的红色元素越来越少，将最后一个红色孙子重涂成黑色，并向左大转，就像前面的情况一样。
检查子树的黑色高度是否稳定。
HCH6-父母是黑人，左儿子是黑人，他的孙子也是黑人
然后是红色木头耗尽的那一刻。没什么可做的，您必须将黑色节点涂成红色，从而使节点7的黑色高度相等，但不是通过增加右侧子树的黑色高度，而是通过降低左侧子树的黑色高度来实现。结果，我们整个结构的黑色高度将减少1，并且我们必须递归地调用平衡到祖先。
带有平衡和递归的删除示例
从红黑树中删除元素后，我们讨论了所有6种黑色高度平衡的情况。为了更好地了解这一切的工作原理，让我们继续从原始树中删除节点30。
第一步只是删除节点30，
第二步是在其父节点25上启动平衡，
这是HH6的一种情况：我们
用悲伤的一半稳定了节点25的高度，
第三步是在祖父的水平上（对于节点20）
进行平衡。，让我们在平衡前后画出整棵树。 HK4就是这种情况：
注意平衡后红黑树的变化，左侧子树中的某些元素已移至右侧，高度已稳定，元素已删除，每个人都很高兴！
使用二进制搜索树时，从红黑树中删除项目是最困难的操作之一。在“算法和数据结构”课程中，我们不仅考虑二进制搜索树，还考虑许多其他有趣的算法，有关更多详细信息，请参见课程程序。
