子节点都是非 null 节点

这种情况下，第一步：找到该节点的前驱或者后继。

前驱：左子树中值最大的节点(可得出其最多只有一个非 null 子节点，可能都为 null)。

后继：右子树中值最小的节点(可得出其最多只有一个非 null 子节点，可能都为 null)。

前驱和后继都是值最接近该节点值的节点，类似于该节点.prev=前驱，该节点.next=后继。

第二步：将前驱或者后继的值复制到该节点中，然后删掉前驱或者后继。

如果删除的是左节点，则将前驱的值复制到该节点中，然后删除前驱;如果删除的是右节点，则将后继的值复制到该节点中，然后删除后继。

这相当于是一种“取巧”的方法，我们删除节点的目的是使该节点的值在红黑树上不存在。

因此专注于该目的，我们并不关注删除节点时是否真是我们想删除的那个节点，同时我们也不需考虑树结构的变化，因为树的结构本身就会因为自动平衡机制而经常进行调整。

前面我们已经说了，我们要删除的实际上是前驱或者后继，因此我们就以前驱为主线来讲解。

后继的学习可参考前驱，包括下面几种情况：

①前驱为黑色节点，并且有一个非 null 子节点

分析：因为要删除的是左节点 64，找到该节点的前驱 63;然后用前驱的值 63替换待删除节点的值 64，此时两个节点(待删除节点和前驱)的值都为 63;

删除前驱 63，此时成为上图过程中间环节，但我们发现其不符合红黑树规则 4，因此需要进行自动平衡调整。这里直接通过【变色】即可完成。

②前驱为黑色节点，同时子节点都为 null

分析：因为要删除的是左节点 64，找到该节点的前驱 63;然后用前驱的值 63 替换待删除节点的值 64，此时两个节点(待删除节点和前驱)的值都为 63。

删除前驱 63，此时成为上图过程中间环节，但我们发现其不符合红黑树规则 5，因此需要进行自动平衡调整。这里直接通过【变色】即可完成。

③前驱为红色节点，同时子节点都为 null

分析：因为要删除的是左节点 64，找到该节点的前驱 63;然后用前驱的值 63替换待删除节点的值 64，此时两个节点(待删除节点和前驱)的值都为 63;删除前驱 63，树的结构并没有打破规则。

红黑树删除总结

红黑树删除的情况比较多，但也就存在以下情况：

• 删除的是根节点，则直接将根节点置为 null。
• 待删除节点的左右子节点都为 null，删除时将该节点置为 null。
• 待删除节点的左右子节点有一个有值，则用有值的节点替换该节点即可。
• 待删除节点的左右子节点都不为 null，则找前驱或者后继，将前驱或者后继的值复制到该节点中，然后删除前驱或者后继。
• 节点删除后可能会造成红黑树的不平衡，这时我们需通过【变色】 【旋转】的方式来调整，使之平衡，上面也给出了例子，建议大家多多练习，而不必背下来。

总结

本文主要介绍了红黑树的相关原理，首先红黑树的基础二叉搜索树，我们先简单说了一下二叉搜索树，并且讲了一下搜索的流程。

然后就针对红黑树的六大规则特点，红黑树的插入操作，删除操作，都使用了大量的图形来加以说明。

技术都是练出来的，有时候很多似是而非的地方，当动笔去写的时候，其实很好理解。

红黑树的使用非常广泛，如 TreeMap 和 TreeSet 都是基于红黑树实现的，而 JDK8 中 HashMap 当链表长度大于 8 时也会转化为红黑树。

红黑树比较复杂，本人也是还在学习过程中，如果有不对的地方请批评指正，望共同进步谢谢。

作者：梁洪

简介：网名工匠初心，热爱技术，喜欢钻研与分享，6 年 Java 开发经验，专注于 Java 以及 Spring 生态圈，同时也喜欢研究物联网、大数据、AI 等前沿技术，带过 15 人以下的小团队，做过项目管理，现在是一家软件公司的部门经理。

【51CTO原创稿件，合作站点转载请注明原文作者和出处为51CTO.com】