一、红黑树的性质

  • 每个节点要么是红色要么是黑色
  • 根节点为黑色，叶节点（NIL）为黑色
  • 每个节点到其任一子孙节点的每一条简单路径黑色节点的数量相同
  • 红色节点的孩子节点均为黑色

二、红黑树的操作（插入、删除）

旋转操作不会改变节点的颜色。同时旋转操作同AVL树，不再赘述。

插入和删除操作都可能使得红黑树的性质遭到破坏，所以需要进行相应的改变（颜色的变化或是节点的旋转）

1. 插入

将插入节点的颜色定义为红色。如此，如果待插入节点的父节点为黑色，那么直接进行插入操作即可。需要讨论的是当待插入节点的父节点为红色的情况，仅以左孩子为例。

（1）插入到左孩子，此时

插入时第一种情况

（2）插入到右孩子

插入时第二种情况

只需要对待插入节点的父节点进行一次左旋操作，即可转化为（1）

下面进行实战分析

假定有一组数【12，15，19，25，27，35，37】，需要插入16，红黑树如下图所示

插入举例1

此时考虑情况（1）的第一种形式

插入举例2

接下来考虑情况（2）

插入举例3

最后考虑情况（1）的第二种形式，得到最后的结果如下图所示

插入举例4

 2. 删除

（1）只有一个子节点

（2）左右孩子均存在，若待删除节点的后继节点（右子树最左侧的节点）为红色，则无论待删除节点为什么颜色，直接将后继节点的value赋值给当前节点，然后删除后继节点即可。

（3）后继节点为黑色

  1.  后继节点为其父节点的左节点
    1.  后继节点的兄弟节点为红色，将其兄弟节点与父节点颜色互换，对父节点左旋，将其父节点与其父节点的右节点颜色互换。

      后继节点的兄弟节点为红色

    2.  后继节点的兄弟节点为黑色，其兄弟节点右节点存在，将其兄弟节点与父节点的颜色互换，令其兄弟节点的右节点为黑色，对其父节点进行左旋即可。

    3.  后继节点的兄弟节点为黑色，其兄弟节点右节点不存在，将其兄弟节点与兄弟节点的左节点颜色互换，对其兄弟节点右旋，转化为b

  2.  后继节点为其父节点的右节点
    1.  后继节点的兄弟节点为红色，转换同I-a

    2.  后继节点的兄弟节点为黑色，左节点存在，转换同I-b

    3.  后继节点的兄弟节点为黑色，左节点不存在，转换同I-c

    4.  后继节点的兄弟节点为黑色，无孩子节点，待删除节点为红色

  3.  会改变深度的情况
    1. 待删除节点为黑色，其子节点均为黑色  

版权声明：本文为fanzhongjie原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/fanzhongjie/p/10141502.html