读书人

红黑树删除有关问题

发布时间: 2012-03-14 12:01:12 作者: rapoo

红黑树删除问题~
删除修正有这样一种情况:


情况3:当前节点是黑色,且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。
解法:把父节点染成红色,把兄弟结点染成黑色,之后重新进入算法(我们只讨论当前节点是其父节点左孩子时的情况)。
然后,针对父节点做一次左旋。此变换后原红黑树性质5不变,而把问题转化为兄弟节点为黑色的情况。

3.变化前:





3.变化后:


仔细看了这两张图,我觉得,似乎不用修正!修正前也补违背红黑树的性质吧?

[解决办法]
有点断章取义啊,原文这段是指删除当前结点。
上图中删除A节点会导致失衡,下图中可以直接删除A结点。

读书人网 >C++

热点推荐