红黑树删除问题~
删除修正有这样一种情况:
情况3:当前节点是黑色,且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。
解法:把父节点染成红色,把兄弟结点染成黑色,之后重新进入算法(我们只讨论当前节点是其父节点左孩子时的情况)。
然后,针对父节点做一次左旋。此变换后原红黑树性质5不变,而把问题转化为兄弟节点为黑色的情况。
3.变化前:
3.变化后:
仔细看了这两张图,我觉得,似乎不用修正!修正前也补违背红黑树的性质吧?
[解决办法]
有点断章取义啊,原文这段是指删除当前结点。
上图中删除A节点会导致失衡,下图中可以直接删除A结点。