红黑树 vs AVL树

AVL是严格的平衡二叉树，无论是执行插入还是删除只要不满足要求都会进行选择，而旋转时非常耗时的，所以AVL树更适合插入和删除比较少，但查找多的情况。红黑树是一种弱平衡二叉树，他的旋转次数较AVL少许多，因此应用场景也相对广一些。

特性

  1. 每个结点都是红色的或是黑色的
  2. 根结点是黑色的
  3. 每个叶结点是黑色的
  4. 如果一个结点是红色的，则它的两个子结点都是黑色的

  5. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色节点

    插入

  6. 如果父结点为黑色结点，那么插入的红色结点不会影响平衡，跳过。

  7. 如果父结点为红色结点

    1. 如果叔结点为红色结点
      1. 父结点和叔结点变为黑色，祖父结点如果不是根结点则变红色
      2. 继续平衡祖父结点
    2. 如果叔结点不存在或是黑色结点
      1. 先进行旋转（同 AVL 树4种旋转方式）
      2. 父结点和祖父节点换颜色
      3. 继续平衡祖父结点

        删除

  8. 找到替换结点：左子树的最大值结点 or 右子树的最小值结点（类似于二叉查找树的删除结点）

  9. 情景1：如果替换结点是红色，那么直接将替换节点值赋给删除结点，并删除替换结点。

  10. 如果替换结点是黑色：

    1. 情景2：如果替换结点是其父结点的左结点
      1. 情景2.1：如果替换结点的兄弟结点是红色，删除黑结点会导致左侧黑色结点少一，此时通过交换兄弟结点和父结点颜色并左旋解决image.png
      2. 情景2.2：如果替换结点的兄弟结点是黑色，兄弟结点右结点为红色，左结点为任意颜色，此时不能通过情景2.1那样左旋达到平衡，而是需要将红色右子结点”借“过来。兄弟结点和父结点颜色对调，右子结点变为黑色，并进行左旋。image.png
      3. 情景2.3：兄弟结点右结点为黑色，左结点为红色。此时左结点与兄弟结点交换颜色，并右旋。再进行情景2.2image.png
      4. 情景2.4：兄弟结点子结点均为黑色。此时兄弟结点没有结点可以借了，只能向父结点借，把兄弟结点设为红色，将父结点作为新的替代结点，自底向上处理。 image.png

b. 情景3：如果替换结点是其父结点的右结点，与左节点情况镜像

参考