理解红黑树插入与删除

综述

红黑树是一个自平衡的二叉查找树，在插入和删除等可能破坏树的平衡时需要自动调整平衡，红黑树的定义就是红黑树是一种含有红黑结点并能自平衡的二叉查找树。

红黑树的性质

• ①、每个节点要么是红色的要么是黑色的；
• ②、根节点是黑色的；
• ③、每个叶子节点(NIL)都是黑色的；
• ④、每个红色节点的两个子节点一定都是黑色的；
• ⑤、任意一节点到每个叶子节点的路径都包含相同数量的黑色节点

从性质⑤可推出结论：如果一个节点存在黑色的子节点，那么这个节点肯定有两个子节点。

关于左旋和右旋问题，以下面两张图为例进行理解：


旋转节点也就是旋转的支点。
左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。
右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。

1、插入操作

插入的节点都是红色的，这可以保证黑色平衡，插入之后不需要做自平衡操作。

①、红黑树为空
直接把插入节点作为根节点，并把根节点颜色置为黑色。

②、插入结点的key已经存在
查找到存在节点的key，并更新值为新的value。

③、插入节点的父节点为黑色
由于插入的节点是红色的，并不会对平衡产生影响，所以直接插入即可。

④、插入节点的父节点为红色
如果插入节点的父节点为红色，那么插入节点肯定不是根节点，而且插入节点肯定有祖父节点，这点对于后续旋转很重要。

分情况讨论第④类

• 叔叔节点存在并且为红色节点
  对于这种情况， 因为待插入节点的叔叔节点为红色的，因此其祖父节点一定为黑色的，此时插入形成黑红红，我们要做的就是把它转换为红黑红，如下面两张图：
  
  
  解释：
  I 为插入节点；
  把PP设为当前插入节点的含义是类似向上递归这种情况，知道平衡为止，红黑树的生长是自底向上的不同于普通的二叉树是自顶向下的；

  如果当PP刚好为根节点时，那我们还需要将PP颜色设置为黑色，这也是唯一一种会增加红黑树黑色节点层数的插入情况

• 叔叔节点为黑色或者不存在，并且插入节点的父节点为祖父节点的左子节点
  对于这种情况来说，因为插入节点的父节点为红色的而叔叔节点为黑色的，所以叔叔节点所在的子树的黑色节点就比父节点所在子树黑色节点多，不满足性质⑤，因此要旋转调整平衡，此时也存在两种情况：

  • 插入节点是父节点的左子节点
    
    对于这一种情况也可以将I和PP置为黑色的，而P设置为红色的，这时会导致之前插入节点父节点为红色的问题，比较麻烦。
  • 插入节点时父节点的右子节点
    

• 叔叔节点不存在或者为黑色节点，并且插入节点的父节点为祖父节点的右子节点
  这种情况对应上一大类知识方向发生了变化

  • 插入节点时其父节点的左子节点
    
  • 插入节点是父节点的右子节点
    

2、删除操作

对于二叉搜索树的删除操作，一般删除该节点，为了平衡会拿取该节点的右子树的最小值来顶上该节点，当然也可以使用左子树的最大值，前者使用较多，因此可以将删除操作看为替换操作。
R为替换节点

• 删除情景一：替换节点为红色的节点
  此种情况直接删除即可
• 删除情景二：替换节点为黑色节点
  • 删除情景2.1：替换结点是其父结点的左子结点
    • 删除情景2.1.1：替换结点的兄弟结点是红结点
      此种情况下替换节点的兄弟节点的父节点和子节点肯定都是红色，处理方法如下图：
      
    • 删除情景2.1.2：替换结点的兄弟结点是黑结点
      此种情况下因为替换节点的兄弟节点是黑色节点，其父节点和子节点颜色是不确定的，所以要分情况讨论
      • 删除情景2.1.2.1：替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色
        此种情况下我们即将删除左子树的一个黑色节点，而兄弟节点右子树存在红色节点，我们可以将这个红色节点“借”过来充当删除的黑色节点，此时存在旋转操作，处理方法如下图：
        
      • 删除情景2.1.2.2：替换结点的兄弟结点的右子结点为黑结点，左子结点为红结点
        兄弟节点所在子树存在红色节点，我们总是可以拿来借的，如下图：
        
      • 删除情景2.1.2.3：替换结点的兄弟结点的子结点都为黑结点
        此种情况下兄弟帮不了了只能找父母，这种情况我们把兄弟节点设置为红色，再把父节点当作替代节点自底向上处理，去找父亲节点的兄弟节点去借，至于将兄弟节点设置为红色的原因就是，替代节点即将删除一个黑色节点，为了保证P所在子树的平衡，处理如下图：
        
  • 删除情景2.2：替换结点是其父结点的右子结点
    这种情况和2.1相反
    • 删除情景2.2.1：替换结点的兄弟结点是红结点
      
    • 删除情景2.2.2：替换结点的兄弟结点是黑结点
      • 删除情景2.2.2.1：替换结点的兄弟结点的左子结点是红结点，右子结点任意颜色
        
      • 删除情景2.2.2.2：替换结点的兄弟结点的左子结点为黑结点，右子结点为红结点
        
      • 删除情景2.2.2.3：替换结点的兄弟结点的子结点都为黑结点
        

上述内容总结自：
30张图带你彻底理解红黑树

动态生成红黑树地址：
Red/Black Tree