数据结构——红黑树(RB-Tree)

╰半夏微凉° 2022-08-10 16:59 136阅读 0赞

## 定义： ##

红黑树本质上是一棵二叉查找树，但在二叉查找树的基础上，每个节点增加了一位存储来表示节点的颜色。有关二叉查找树的介绍在前面博文《[二叉查找树][Link 1]》已经介绍过了，这里不再进行讲解。

### 红黑树的性质： ###

1.  每个节点或是红色的，或是黑色的。
2.  根节点是黑色的。
3.  每个叶节点（NULL）是黑色的。
4.  如果一个节点是红色的，则它的两个孩子节点都是黑色的。
5.  对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

### 红黑树的结构图： ###

![SouthEast][]

## 旋转 ##

当对红黑树进行插入和删除操作时，会违背红黑树的性质，为了维护这些性质，必须要改变树中某些节点的颜色以及指针结构。指针结构的修改时通过旋转来完成的，这是一种能保持二叉查找树性质的查找树局部操作。

### 左旋转： ###

当在某个节点x上做左旋转操作时，假设它的右孩子为y而不是NULL，左旋转以x到y的链为“支轴”进行。它使y成为该子树的新的根节点，x成为y的左孩子，y的左孩子成为x的右孩子。

LEFT_ROTATE(T,x)
        y = right[x]   //获取右孩子
        rihgt[x] = left[y]  //设置x的右孩子为y的左孩子
        if left[y] != NIL
           then parent[left[y]] = x
        parent[y] = parent[x]  //设置y的父节点为x的父节点
        if parent[x] == NIL
           then root[T] = y
        else if x==left[parent[x]
                then left[parent[x]] = y
             else  right[[parent[x]] = y
        left[y] = x  //设置y的左孩子为x
        parent[x] =y

### 右旋转： ###

右旋转与左旋转的描述差不多，具体见下面结构图

![SouthEast 1][]

RIGHT_ROTATE(T,y)
         x = left[y]    //获取左孩子
         left[y] = right[x] //设置y的左孩子为x的右孩子
         if right[x] != NIL
            then parent[right[x]] = y
         parent[x] = parent[y]  //设为x的父节点为y的父结点
         if parent[y] == NIL
             then root = x
         else if y== left[parent[y]]
                 then left[parent[y]] = x
              else  right[parent[y]] = x
         right[x] = y //设置x的右孩子为y
         parent[y] = x

## 插入操作： ##

红黑树的插入操作类似于二叉查找树的插入操作，只是在它的基础上进行改进，先把节点按照二叉查找树的插入方法进行插入，再把该插入的节点标记为红色（为了满足性质5），为了保证插入节点后能够维持红黑树的性质，我们必须调用一个辅助程序RB\_INSERT\_FIXUP来对结点重新着色并旋转，使得满足红黑树的性质。

RB_INSERT(T,z)
      y = NIL
      x =root(T)
      while x != NIL
           do y=x
               if key[z]<key[x]
                 then x=left[x]
                 else  x=right[x]
      parent[z] = y
      if y =NIL
         then root =z
         else if key[z] < key[y]
                then left[y] =z
                else  right[y] =z
       left[z] = NIL
       right[z] =NIL
       color[z] = RED  //新插入结点标记为红色
       RB_INSERT_FIXUP(T,z)  //进行调整，使得满足红黑树性质

插入节点后，如果会破坏红黑树的性质时，只能破坏性质2或者性质4，其他性质不会被破坏。若破坏了性质2，则新插入的节点必定为根节点，此时只需修改该节点的颜色即可。

因为在插入新结点z之前，红黑树的性质没有被破坏。若插入结点z后违反性质4，必定是因为z和其父亲结点parent\[z\]都是红色的。假设新插入结点z，导致红黑树性质4被破坏，此时z和其父节点parent\[z\]都是红色，由于在插入结点z之前红黑树的性质没有被破坏，parent\[z\]是红色，很容易推出z的祖父结点parent\[parent\[z\]\]必定是黑色。此时根据parent\[z\]是parent\[parent\[z\]\]的左孩子还是右孩子进行讨论。因为左右之间是对称的，这里只给出了parent\[z\]作为parent\[parent\[z\]\]的左孩子进行讨论的，然后给出了三种可能的情况。

情况1：z的叔叔节点y是红色的

此时parent\[z\]和y都是红色的，解决办法是将z的父节点parent\[z\]和叔叔结点y都着为黑色，而将z的祖父结点parent\[parent\[z\]\]着为红色，然后从祖父结点parent\[parent\[z\]\]继续向上判断是否破坏红黑树的性质。

![SouthEast 2][]

情况2：z的叔叔节点y是黑色且z是一个右孩子

情况3：z的叔叔节点y是黑色且z是一个左孩子

情况2和情况3中y都是黑色的，通过z是parent\[z\]的左孩子还是右孩子进行区分的。情况2中z是右孩子，可以在parent\[z\]结点将情况2通过左旋转为情况3，使得z变为左孩子。无论是间接还是直接的通过情况2进入到情况3，z的叔叔y总是黑色的。在情况3中，将parent\[z\]着为黑色，parent\[parent\[z\]\]着为红色，然后从parent\[parent\[z\]\]处进行一次右旋转。情况2、3修正了对性质4的违反，修正过程不会导致其他的红黑性质被破坏。

![SouthEast 3][]

![SouthEast 4][]

RB_INSERT_FIXUP(T,z)
      while color[parent[z]] = RED
        do if parent[z] == left[parent[parent[z]]]
              then y = right[parent[parent[z]]]
    	//情况1，z的叔叔为红色
                  if color[y] == RED    
                     then color[parent[z]] = BLACK		//case 1
                          color[y] = BLACK			//case 1
                          color[parent[parent[z]]=RED 	//case 1
                          z= parent[parent[z]]		//case 1
    	//情况2，z的叔叔为黑色，z为右孩子
                  else if z == right[parent[z]]    		//case 2
                          then z = parent[z]		//case 2
                               LEFT_ROTATE(T,z)
    	//情况3，z的叔叔为黑色，z为左孩子
                          color[parent[z]]=BLACK    	//case 3
                          color[parent[parent[z]] = RED	//case 3
                          RIGHT_ROTATE(T, parent[parent[z]])//case 3
                      else (same as then clause with “right” and “left” exchanged)
      color(root(T)) = BLACK; //将根结点设置为黑色

## 删除操作： ##

红黑树的删除操作是在二叉查找树删除的基础上进行改进，主要是因为删除节点时可能会破坏红黑树的性质。如果被删除的节点y是红色的，则删除后不会破坏红黑树的性质，既不需要修改。原因如下：

1.  树中的黑高没有变化
2.  不存在两个相邻的红节点
3.  如果y是红色，就不可能是根节点，所以根节点仍然是黑色

如果被删除的节点y是黑色，则会破坏红黑树的性质，具体破坏了哪些性质我们进行讨论：

1.  如果y是原来的根节点，而y的一个红色的孩子节点成为了新的根节点，这就违背了性质2。
2.  如果x和parent\[y\]（此时parent\[x\] = parent\[y\]）都是红色，就违反了性质4。
3.  删除y将会导致先前包含y的任何路径上黑结点个数减少1，违反了性质5。改正这一问题的方法是将现在占有y原来位置的节点x视为还有一重额外的黑色。即将任意包含结点x的路径上黑结点个数加1，这样可以保证性质5成立。  
    
4.  当将黑色结点y被删除时，将其黑色“下推”至其子结点，导致问题变成为结点x可能即不是红，又不是黑，从而违反性质1。因为给x增加了一种颜色，即结点x是双重黑色或者是红黑色。这样就分别给包含x的路径上黑结点个数贡献2个或1个。但是x的color属性仍然是RED（如果x是红黑的）或BLACK（如果x是双重黑色）。换而言之，一个结点额外的黑色反映在x指向它，而不是它的color属性。

RB_TRANSPLANT(T,u,v)
    1	if u.p == T.nil
    2		T.root = v
    3	elseif u == u.p.left
    4			u.p.left = v
    5		else u.p.right = v
    6	v.p = u.p

RB_DELETE(T,z)
    1	y = z
    2	y_original.color = y.color
    3	if z.left == T.nil
    4		x = z.right
    5		RB_TRANSPLANT(T,z,z.right)
    6	else if z.right == T.nil
    7			x - z.left
    8			RB_TRANSPLANT(T,z,z.left)
    9		else y = TREE_MINIMUN(z.right)
    10			y_original.color = y.color
    11			x = y.right
    12			if y.p == z
    13				x.p = y
    14			else RB_TRANSPLANT(T,y,y.right)
    15				y.right = z.right
    16				y.right.p = y
    17			RB_TRANSPLANT(T,z,y)
    18			y.left = z.left
    19			y.left.p = y
    20			y.color = z.color
    21	if y_original.color == BLACK
    22		RB_DELETE_FIXUP(T,x)

或者

RB_DELETE(T,z)
         if left[z] ==NIL or right[z] == NIL
            then y=z
            else  y=TREE_SUCCESSOR(z)
        if left[y] != NIL
            then x=left[y]
            else  x=right[y]
        parent[x] = parent[y]
        if p[y] ==NIL
           then root[T] =x
           else if y = left[[prarnt[y]]
                       then left[parent[y]] = x
                       else  right[parent[y]] =x
         if y!=z
             then key[z] = key[y]
                   copy y's data into z
         if color[y] == BLACK    //当被删除结点为黑色时候进行调整
             then RB_DELETE_FIXUP(T,x)
          return y

过程RB\_DELETE\_FIXUP恢复性质1，2，4。对于恢复性质2、4很简单，因为x是红色，所有直接将x结点着为黑色即可。这里着重介绍了如何恢复性质1。此时x是黑色，需要根据x是左孩子还是右孩子两种情况进行恢复，因为左右是对称的，这里只给出了x是左孩子的恢复过程。将x作为第一个额外的黑色结点，从x结点开始循环，将额外的黑色结点沿着树向上移，直到：

1.  x指向红黑节点，将x着为单黑色
2.  x指向根节点，此时移除额外的黑色
3.  执行适当的旋转和重新着色，退出循环

在循环过程中，x总是指向一个具有双重黑色的非根结点。设w是x的兄弟结点，因为x是双重黑色的，故w不可能是NIL。

RB_DELETE_FIXUP(T,x)
    1　while x!= root[T] and color[x] ==BLACK
    2     do if x == left[parent[x]]
    3           then w = right[parent[x]]
    4           if color[w] == RED												 
    5               then color[w] = BLACK							//case 1 
    6                   color[parent[x]] = RED						//case 1 
    7                    LEFT_ROTATE(T,PARENT[x])					//case 1 
    8                   w = right[parent[x]]						//case 1 
    9            if color[left[w]] == BLACK and color[right[w]] = BLACK
    10               then color[w] = RED							//case 2
    11                    x = parent[x]								//case 2
    12            else if color[right[w]] =BLACK
    13               then color[left[w]] = BLACK					//case 3
    14                    color[w] = RED							//case 3
    15                    RIGHT_ROTATE(T,w)							//case 3
    16                    w = right[parent[x]]						//case 3
    17				color[w] = color[parent[x]]						//case 4
    18                color[parent[x]] = BLACK						//case 4
    19                color[right[w]] = BLACK						//case 4
    20                LEFT_ROTATE(T,parent[x])						//case 4
    21                x=root(T)										//case 4
    22     else(same as then clasue with “right” and “left” exchanged)
    23  color[x]=BLACK

情况1：x的兄弟节点w是红色的。

因为w必须有黑色子节点，所以改变w及parent\[x\]的颜色,并对parent\[x\]做一次左旋转。现在x的新兄弟节点是旋转之前w的某个子节点，其颜色为黑色。这样情况1转换为情况2、3或4处理。

4           if color[w] == RED												 
    5               then color[w] = BLACK							//case 1 
    6                   color[parent[x]] = RED						//case 1 
    7                    LEFT_ROTATE(T,PARENT[x])					//case 1 
    8                   w = right[parent[x]]						//case 1

![SouthEast 5][]

情况2：x的兄弟节点w是黑色的，而且w的两个子节点都是黑色的。

因为w是黑色的，所以从x和w上去掉一重黑色，使得x只有一重黑色，而w为红色，为了补偿从x和w上去掉的一重黑色，在原来是红色或黑色的parent\[x\]上新增一重额外的黑色，通过将parent\[x\]作为新节点x来重复while循环。

9            if color[left[w]] == BLACK and color[right[w]] = BLACK
    10               then color[w] = RED							//case 2
    11                    x = parent[x]								//case 2

![SouthEast 6][]

情况3：x的兄弟节点w是黑色的，w的左孩子节点是红色的，右孩子节点是黑色的。

可以交换w和其左孩子left\[w\]的颜色，然后对w进行右旋转。现在x的新兄弟节点w是一个有着红色右孩子的黑色节点，这样将情况3转换为情况4。

12            else if color[right[w]] =BLACK
    13               then color[left[w]] = BLACK					//case 3
    14                    color[w] = RED							//case 3
    15                    RIGHT_ROTATE(T,w)							//case 3
    16                    w = right[parent[x]]						//case 3

![SouthEast 7][]

情况4：x的兄弟节点w是黑色的，且w的右孩子节点是红色的。

将w颜色设置为parent\[x\]的颜色，parent\[x\]设置为黑色，w的右孩子right\[w\]设置为黑色，并对parent\[x\]做一次右旋转，最后把root设置为x。

17				color[w] = color[parent[x]]						//case 4
    18                color[parent[x]] = BLACK						//case 4
    19                color[right[w]] = BLACK						//case 4
    20                LEFT_ROTATE(T,parent[x])						//case 4
    21                x=root(T)										//case 4

![SouthEast 8][]

参考：http://www.cnblogs.com/Anker/archive/2013/01/30/2882773.html

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md

[Link 1]: http://blog.csdn.net/chenhanzhun/article/details/21990545
[SouthEast]: /images/20220810/75352f6ffdb34e83947cb3155d5c45eb.png
[SouthEast 1]: /images/20220810/08ff8b5a000b45f6855f967f83da1088.png
[SouthEast 2]: /images/20220810/6e1eaf878ffc46058d67d08d0dcf00fc.png
[SouthEast 3]: /images/20220810/1ab64bf20ece4f56bdb251b84638e130.png
[SouthEast 4]: /images/20220810/acaf21128b254e46942158e3b09eb3ed.png
[SouthEast 5]: /images/20220810/08f15c0db78f4d6eae2a7c11c0987b9a.png
[SouthEast 6]: /images/20220810/b2beacae0c9b4183ab8b8758435f506b.png
[SouthEast 7]: /images/20220810/b9808095a6b847aa9ad1f247e9426ad9.png
[SouthEast 8]: /images/20220810/d7ec9b095a0d44c2afe7f6ec4a8f27f9.png