文章首发于：clawhub.club

这篇文章学习红黑树的删除操作，阅读分析了几篇关于红黑树删除的文章，好复杂。
贴出红黑树的性质：

  1. 每个结点要么是红的，要么是黑的。
  2. 根结点是黑的。
  3. 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
  4. 如果一个结点是红的，那么它的俩个儿子都是黑的。
  5. 对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

红黑树的删除操作分为两步：
一、按照普通的二叉查找树删除节点。

  1. 如果删除的节点下只有一个非空子节点，则直接删除这个节点，用它唯一的子节点顶替它的位置。
  2. 如果它是叶子节点，直接删除。
  3. 如果它有两个子节点且都不为空。则把它的中序遍历后的直接后继节点内容复制到它的位置，它的后继节点不可能有两个非空子节点，这样就转化成上面两种情况了，直接删除这个后继节点。

二、修正红黑树
在删除节点之后，红黑树的性质可能遭到破坏，如果删除的是红色节点，对原树没有影响。
如果删除的结点是黑色结点，原红黑树的性质可能会被改变，我们要对其做修正操作。

  • 如果删除结点不是树唯一结点，那么删除结点的那一个支的到各叶结点的黑色结点数会发生变化，此时性质5被破坏。
  • 如果被删结点的唯一非空子结点是红色，而被删结点的父结点也是红色，那么性质4被破坏。
  • 如果被删结点是根结点，而它的唯一非空子结点是红色，则删除后新根结点将变成红色，违背性质2。

以下就懵逼了！！！
参考下面两篇文章
https://zhuanlan.zhihu.com/p/24367771这个吧。
https://www.cnblogs.com/skywang12345/p/3624343.html

删除黑色节点的时候，修复工作忒复杂，等以后闲了的时候再分析。