RBtree删除怎么实现

这篇文章主要讲解了“RBtree删除怎么实现”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“RBtree删除怎么实现”吧！下面先放出红黑树删除函数的代码：我们设要删除的结点为z，在下面的过程中y总是指向树中会被删除的结点或是会被替代的结点而x总是指向要替代z或y的结点；从代码上看，红黑树的删除操作与二叉树搜索树一样都是分三种情况进行的：1).z只有左儿子/右儿子
2).z有左右儿子,z的后继结点是z的右儿子
3).z有左右儿子,z的后继的结点不是z的右儿子
那么现在我们就来分析这三种情况下删除z需要怎样操作，以及删除z后红黑树的那些性质会被违反，我们如何进行调整以恢复性质。情况1：z只有左儿子/右儿子
这种情况下删除操作是很简单的，我们只需要用z的左孩子或右孩子替代z就行了；然后y表示z，x表示z的左孩子或右孩子，ycolor表示z的颜色。
(1).如果z的颜色为红；那么这种替代以后红黑树不会有任何性质被违反，所以就不需要进行调整。
(2).如果z的颜色为黑；那么就意味着有一个黑色结点被覆盖了，这时如果替代z的x是黑色，那么就意味着黑高减少，性质5被破坏了，这时我们可以在x上再人为的”增添”一重黑色,此时x变成双重黑色的结点，但是性质5恢复了；如果x是红色，那么如果z的父结点是红色的，那么性质4和性质5都就会被破坏，这时我们就可以将x染成红色，这样性质4，性质5都可以恢复了。情况2：z有左右儿子，并且其右儿子就是其后继结点
我们知道一个结点的后继就是将所有结点按关键字从小到大的排序后，排在其后面的那一个结点。z的右儿子就是z的后继，说明z的右儿子的左子树为空 香港云主机。此时y表示z的右儿子，而x表示y的右儿子。删除过程应该是用 y 替代 z, 然后 x 替代 y，并且将y染成z原来的颜色，ycolor表示y原来的颜色。现在因为y替代z以后被染成z原来的颜色，所以至z以上红黑树的所有性质都不会变，唯一有可能会影响红黑树性质的地方在x替代y这一点。所以其实情况有返回到情况1了，下面按y的颜色进行分类讨论：
(1).y的颜色为红；那么无论x的颜色为红还是为黑，x替换y以后都不会影响任何性质。
(2).y的颜色为黑；这时与上面的情况1是相似的，如果x为黑，则性质5会被违反，我们通过将其染成双重黑色解决。如果x为红，则性质4,5都会被违反，但是我们可以通过将x染成黑色恢复。情况3：z有左右儿子，并且z的后继不是其右儿子
其实这种情况和情况2是基本一样的，唯一不同的点在于y的位置会变。在情况2中y是z的右儿子，而在这里我们需要用一个查找后继的函数查找到y，然后x仍然表示y的右儿子，ycolor表示y的颜色。同样的x取代y，然后y取代z并被染成z原来的颜色。所以我们还是只需要关注x取代y的过程。接下来按y的颜色讨论，其实与上面情况2是一模一样的：
(1).如果y的颜色为红色；那么无论x为红还是为黑，替换都不会影响任何性质，无需调整。
(2).y的颜色为黑；如果x为黑，则性质5会被违反，我们通过将其染成双重黑色解决。如果x为红，则性质4,5都会被违反，但是我们可以通过将x染成黑色恢复。上面的所有情况讨论完了以后，我们就发现如果ycolor为红，则删除以后不需要任何的调整。否则如果ycolor为黑，红黑树的性质就会被违反，需要进入调整函数中调整恢复性质。并且进入调整函数时，如果x为红，那么我们简单的将其染成黑色就可以恢复性质了；如果x为黑，那么进入调整函数是我们就将其看成带有双重黑色的情况，调整函数中需要消除那重额外的黑色。对于x为双重黑色的情况，还有一点需要注意：如果此时x为根结点，我们可以简单的去掉一重黑色就行了(其实就是不需要做任何操作)，这时黑高是不会受影响的。所以我们下面集中精力来讨论如何调整双重黑色的情况。(1).w的颜色为红
此时x的父结点一定是黑色的，我们可以通过将w染成黑色，x的父结点染成红色，然后对x的父结点进行左旋变成下面w为黑的情况(旋转以后要重新指定w)。变化为(2)的问题。(2).w的颜色为黑
此时又需要按照w的左右儿子的颜色进行分类讨论
1).w的左右儿子都为黑色：此时我们可以将w染成红色，x移动为x的父结点，将x在树中上移一层,如果x->p是根结点或x->p原来是红色则结束循环,否 则转成情况(1).
2).w的右儿子为黑(左孩子为红)：此时我们可以通过染色和选择转成w的右孩子为红的情况(具体的操作见代码) 变化为4 的情况 继续执行
3).w的右儿子为红：这种情况下，我们是可以通过选择和染色去掉x的双重黑色，结束循环的(具体操作见代码) 4变化以后 结束循环至此我们就将调整函数中所有的情况讨论完了，下面给出调整函数的代码：
下面给出一份带注释和 测试
数据的完整红黑树代码：

感谢各位的阅读，以上就是“RBtree删除怎么实现”的内容了，经过本文的学习后，相信大家对RBtree删除怎么实现这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是开发云，小编将为大家推送更多相关知识点的文章，欢迎关注！

相关推荐: redis中如何解决分布式幂等问题

这篇文章给大家分享的是 香港云主机有关redis中如何解决分布式幂等问题的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。分布式系统由众多微服务组成，微服务之间必然存在大量的网络调用。下图是一个服务间调用异常的例子，用户提交订单之后，请…