红黑树定义和性质

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
从性质5又可以推出：
性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点

红黑树插入节点处理

image.png

其中节点名称定义如下

image.png

情景4.1.1

image.png

情景 4.2.1

image.png
情景4.2.2

image.png
情景 4.3.1

image.png
情景4.3.2

image.png

红黑树删除节点处理

红黑树节点删除分为两步

查找到要删除的目标节点
删除节点后自平衡

二叉树删除结点找替代结点有3种情情景：

1. 无子节点时，删除节点可能为红色或者黑色；
  1.1 如果为红色，直接删除即可，不会影响黑色节点的数量；
  1.2 如果为黑色，则需要进行删除平衡的操作了；
1. 只有一个子节点时，删除节点只能是黑色，其子节点为红色，否则无法满足红黑树的性质了。此时用删除节点的子节点接到父节点，且将子节点颜色涂黑，保证黑色数量。
1. 有两个子节点时，与二叉搜索树一样，使用后继节点作为替换的删除节点，情形转至为1或2处理。
情景1图示

image.png
情景2图示

image.png

情景3图示

image.png

通过上面讨论,得知红黑树删除节点只需要关注情景1,2,其中2和1.1比较简单,后面重点关注1.2 删除黑色的叶子节点
因为一旦该节点被拿掉，红黑树中通过该节点的路径黑色节点数量将会减1，而且无法像情形2那样将子节点涂黑来达到平衡。此时只能自底向上进行平衡操作。

情景1.2删除节点后再平衡

约定节点名称

image.png
约定 h(A->B->叶子)表示从A走到B再走到某一个叶子路径的黑色节点数量（A与B，B与叶子之间可能间隔了多个节点）

本文余下内容均指的是删除黑色的叶子节点后引发的一系列平衡操作。比如P->D->N，删除D（黑色）后，N接至父节点：P->N。
因为删除了一个黑色节点（N的父节点D），经过N的路径的黑色数量减1，即h(P->N->叶子) 比 h(P->S->叶子) 少1。

平衡的方式有：
（1）h(P->N->叶子)不变，h(P->S->叶子)减1，此时已经子平衡；然而h(GP->P->叶子)还是会比h(GP -> U ->叶子)少1。此时需要将P当作新的N，向上递归处理；

（2）h(P->N->叶子)加1，h(P->S->叶子)不变，也就是恢复了原来的状态，此时已经平衡，因为h(GP->P->叶子)=h(GP -> U ->叶子)。

删除平衡情形，主要根据 [兄节点的位置/颜色]、[兄的子节点的颜色]、[父节点颜色] 进行分类

7779607-e1716801d002f2b1.png

情景1 当前节点为根节点（父节点为NULL）
比较特殊的情况，无需平衡操作。因为经过根节点的黑色数量少一个，意味着所有路径都少一个，已然平衡。
情景2 兄弟为黑色节点（S=黑）
- 情景 2.1 兄弟的子节点全黑（SL/SR=黑）
  兄弟节点的子节点全为黑色，也就意味着兄弟节点（S）可以涂红而不会和子冲突。S涂红后，也就实现了子平衡，
  这时候我们看父节点是红是黑，再做处理。
  - 情形2.1.1 父节点为黑色（P=黑）
    此时将S涂红，父节点作为新的平衡节点N，递归上去处理。
    这个也就是之前提到的h(P->N->叶子)不变，h(P->S->叶子)减1；而h(GP->P->叶子)，依然会比h(GP -> U ->叶子)少1，所以要递归上去处理。
    
    image.png
  - 情形2.1.2 父节点为红色（P=红）
    此时将S涂红，P涂黑，平衡结束。
    S涂红后，h(P->N->叶子)不变，h(P->S->叶子)-1，实现子平衡；
    因为P节点是红色的，如果将它涂黑，h(P->N->叶子)和h(P->S->叶子)均会+1，就可以恢复原来的状态了，而不用递归上去。
    
    image.png
- 情形2.2 兄弟的子节点不全黑
  所谓的不全黑包括：[SL红, SR红]、[SL黑，SR红]、[SL红，SR黑]。
  如果其中一个为黑，另外一个肯定是红。
  以全黑/非全黑作为分类，是因为全黑时无论N是在左子还是右子，其处理方式是一样的。
  而非全黑则要看N所处的位置（或者说S所处的位置）进行特定方向的旋转。
  为了方便理解和记忆，以S进行分组：
  S为左子时（即N为右子），主要分两组 [SL=红]、[SL=黑]。
  S为右子时（即N为左子），主要分两组 [SR=红]、[SR=黑]。
  【S为左子，SL红】与【S为右子，SR红】处理方式对称；
  【S为左子，SL黑】与【S为右子，SR黑】处理方式对称。
  - 情形2.2.1 S为左子，SL红；S为右子，SR红
    - 情形(1) S为黑色，S为左子，SL红时：
      以P为支点右旋；交换P和S颜色，SL涂黑；平衡结束。
      这里的平衡思路其实就是：h(P->S->叶子)不变（因为SL涂黑补回来了），h(P->N->叶子)+1（因为多了个黑色P）。
      
      image.png
      
      通常旋转后，新的P节点往往都会涂成原P的颜色：一是为了让GP-P不会颜色冲突；二是保持经过P的路径黑色数量不变。
    - 对称的情形(2)：S为黑色，S为右子，SR红时：
      以P为支点左旋；交换P和S颜色（S涂为P原颜色，P涂黑），SR涂黑；平衡结束。
      
      image.png
  - 情形2.2.2 S为左子，SL黑；S为右子，SR黑
    - 情形(1) S为黑色，S为左子，SL黑
      以S为支点左旋，交换S和SL颜色（SL涂黑，S涂红），此时转至情形2.2.1-(1) S左-SL红进行处理。
      
      image.png
      
      S涂红是为了使h(原S->SR->叶子)不变。
    - 对称的情形(2) S为黑色，S为右子，SR黑
      以S为支点右旋，交换S和SL颜色（SL涂黑，S涂红），此时转至2.2.1-(1) S右-SR红进行处理。
      
      image.png
情形3 兄弟节点为红色（S=红)
- 情形(1) S为左子时，以P进行右旋；
- 情形(2) S为右子时，以P进行左旋；
  旋转后交换P和S的颜色（S涂红，P涂黑），此时以P作为当前平衡节点N，进入情形2-兄弟节点为黑色进行处理。
  
  image.png