红黑树之删除节点

若删除节点是双支节点,就用后继节点替代(值换,色不换)

然后问题变成删除后继节点


1、如果后继节点是单分支,那只有B-R的情况,再用后继节点替代

最后直接删除红色叶子节点


2、如果后继节点是叶子节点,只在黑色节点下才需要修复

2.1、该叶子节点的兄弟节点为红,为了确保兄弟变为黑,

需要将父节点与兄节点颜色互换,再以兄弟为轴RR/LL


2.2、兄弟节点为黑色,且远侄子节点为红色

和上述操作一样,再把远侄子变黑

∴父和远侄子在同一级且都为黑

直接删除父下的黑叶子节点不会有影响


2.3、兄弟节点为黑色,远侄子节点也为黑色,但近侄子节点为红色

将兄弟和近侄子颜色互换,再右旋/左旋,问题变为2.2


2.4、兄弟为黑,远近侄子都黑,但父节点为红

将父节点改黑,兄弟变红,再删除叶子节点


2.5、兄弟,远近侄子,父节点都为黑

将兄弟变红,删除叶子节点,还需以父节点向上迭代

以确保根节点的左右两分支的黑高一致

总结:先看待删除的节点的颜色,再看兄弟节点的颜色,

再看侄子节点的颜色(侄子节点先看远侄子再看近侄子),最后看父亲节点的颜色。

原文地址:https://www.cnblogs.com/mo-jian-ming/p/13944603.html