红黑树

红黑树图
Java在实现TreeMap中用到了红黑树，在此记录自己的理解。

定义

红黑树是二叉搜索树的一种实现方式，任意一条到叶结点的路径不会比其他路径长出2倍。

性质

红黑树一共有5点性质：

1. 每个结点是红色或者黑色的
2. 根结点是黑色的
3. 叶结点是黑色的
4. 如果一个结点是红色的，那么它的儿子结点都是黑色的
5. 每一个结点到其叶结点的所有路径中，黑色结点的个数相同

红黑树的一个结点如果没有儿子，那么它将指向一个NIL结点，该NIL结点为叶结点。同理，根结点的父亲也指向NIL结点。NIL结点为黑色的，其left、right、p、key可以为任何值。

为了便于在红黑树执行增加或删除操作时的边界处理，使用一个哨兵结点T.nil代表NIL。

操作

一个二叉树的基本操作有增加、删除和查询。红黑树的基本操作时间复杂度为O(lgn)。为了保证红黑树进行增加或删除操作后仍然保持其性质，需要在基本操作之后进行处理，使其满足特性。

旋转

旋转是修改红黑树结构的一种方法。

红黑树_旋转.jpg

增加

往红黑树中增加一个结点z，z结点被设为红色，并且占据了原某一叶子结点的位置。由于在加入z结点之前红黑树满足性质，在加入z结点后，树可能不满足的性质为性质4，即出现某一红色结点的儿子仍为红色结点。此时需要处理该红色z结点，主要方法为在满足其余性质的情况下，不断将红色上移（不是移动结点，而是不断更改相邻结点的颜色），直到根结点为红色，将根结点变为黑色或者在某一步上移中，红色移动到了满足所有性质的位置。

当z结点的父亲结点为黑色时，不存在不满足的性质，以下讨论z结点的父亲为红色时的情况。我们不妨另z为其父结点的左儿子，对于z为其父结点右儿子的情况，可以通过旋转将其变为左儿子。

增加_右儿子变左儿子.jpg

假设z.p=z.p.p.left，另一种情况与此相似。此时只需要按照z.p.p.right，即z的叔结点的颜色进行分类讨论即可。

1. 叔结点为红色

   
   叔结点为红色.png

将z.p和z.p.p.right变为黑色，将z.p.p变为红色。经过上述操作后，原z结点满足性质4，另z'=z.p.p，继续以处理z的方式处理z'。

2. 叔结点为黑色

   
   增加_叔结点是黑色.png

将z.p.p设为红色，将z.p设为黑色，将z.p.p进行左旋转。这里对p结点进行右旋转后，由于q结点不再是z的父辈结点，导致z路径上的黑色结点减少一个，将p变为黑色后满足，此时满足性质4，完成处理。

删除

红黑树的删除基于TRANSPLANT操作，以下为其实现。

RB-TRANSPLANT(T,u,v)
    if(u.p==T.nil)
        T.root=v
    else if u==u.p.left
        u.p.left=v
    else 
        u.p.right=v
    v.p=u.p       

在红黑树上删除一个结点z后，我们用其子树上的y结点连接z的父结点，并将y结点的颜色设为与z结点相同，这里需要分类讨论z的儿子结点个数。

1. 当左儿子为NIL时，y结点为z的右儿子。

   
   删除_左左儿子为nil.png

2. 当右儿子为NIL时，y结点为z的左儿子。

   
   删除_右儿子为nil.png

3. 当左、右儿子均不为NIL时，y结点为树中比z结点大的最小结点，即z结点右子树中的最小结点。

   
   删除_左右儿子非nil.png

在第1或第2的情况下下，如果z结点为黑色，将y放置到z的位置后，y父辈到叶结点的路径上的黑色结点个数减一；或者情况3下y结点为黑色，将y放置到z的位置后，y的右儿子的父辈到叶结点的路径到上的黑色结点个数减一。为了保证红黑树的性质5，我们暂时增加该结点（情况1、2为y结点，情况3为x结点）的“黑色的程度”，即计算路径上的黑色结点时多计算一次该结点的黑色次数。

我们处理该多余黑色次数的主要办法与之前的方法相似，不断将该黑色次数上移，直到遇到一个红色结点，将其变为黑色或将黑色次数上移到根节点再清除。

统一另增加了黑色程度的结点为x，不妨令x=x.p.left，对于x=x.p.right的情况与之相似。

1. x结点为红色
   只需要将x结点变为黑色，即可使树满足性质5。

2. x结点为黑色，x兄弟结点w为红色（此时x的父结点为黑色）
   将x.p设为红色，将x兄弟结点w设为黑色，并对x.p进行左旋转，即可通过下面的分类进行处理。

   
   删除_case2.png

3. x结点为黑色，x兄弟结点w为黑色，且w的儿子均为黑色
   将x多余的黑色次数上移给x.p，并将w结点设为红色。令x'=x.p，继续循环。

   
   删除_case3.png

4. x结点为黑色，x兄弟结点w为黑色，且w左儿子为红色，w右儿子为黑色
   将w设为红色，w左儿子设为黑色，对w进行右旋转，使用下面的分类进行处理。

   
   删除_case4.png
5. x结点为黑色，x兄弟结点w为黑色，且w右儿子为红色

• 若x.p为黑色，x.p左旋转，消除黑色次数

  
  删除_case5_1.png

• 若x.p为红色，x.p设为黑色，w设为红色，x.p左旋转，消除黑色次数

  
  删除_case5_2.png