547.删除
第一步:将红黑树当作一颗二叉查找树,将节点删除。
这和"删除常规二叉查找树中删除节点的方法是一样的"。分 3 种情况:
- 被删除节点没有儿子,即为叶节点。那么,直接将该节点删除就 OK 了。
- 被删除节点只有一个儿子。那么,直接删除该节点,并用该节点的唯一子节点顶替它的位置。
- 被删除节点有两个儿子。那么,先找出它的后继节点;然后把“它的后继节点的内容”复制给“该节点的内容”;之后,删除“它的后继节点”。
第二步:通过"旋转和重新着色"等一系列来修正该树,使之重新成为一棵红黑树。
因为"第一步"中删除节点之后,可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树,使之重新成为一棵红黑树。
选择重着色 3 种情况。
-
情况说明:x 是“红+黑”节点。
处理方法:直接把 x 设为黑色,结束。此时红黑树性质全部恢复。 -
情况说明:x 是“黑+黑”节点,且 x 是根。
处理方法:什么都不做,结束。此时红黑树性质全部恢复。 -
情况说明:x 是“黑+黑”节点,且 x 不是根。
处理方法:这种情况又可以划分为 4 种子情况。这 4 种子情况如下表所示:
参考:https://www.jianshu.com/p/038585421b73
代码实现:https://www.cnblogs.com/skywang12345/p/3624343.html