红黑树-转载整理

发表于 | 分类于 | 评论数： | 阅读次数：

前言

红黑树是一种自平衡二叉查找树，其每个结点都有一个存储位来表示结点的颜色，RED或者BLACK。红黑树的实现结构复杂，但是在红黑树上的查找，增加和删除的时间复杂度都为O(logn)，因此红黑树的应用广泛，如Java的HashMap当冲突链表长度大于8时，转为红黑树；TreeMap使用红黑树结构等。

二叉查找树

在了解红黑树之前要先明白二叉查找树，因为红黑树是特殊的二叉查找树，有着二叉查找树特点。

性质

二叉查找树上的结点必须按二叉查找树的性质进行存储：

  • 如果一个结点拥有左子树，则左子树上的所有结点的值都小于该结点的值
  • 如果一个结点拥有右子树，则右子树上的所有结点的值都大于该结点的值

表示

  • T：树的头结点
  • 每个结点都有key、left、right、p属性，分别代表结点值、左结点、右结点和父结点

查找

由于二叉查找树的性质，如果查找值比结点的值小进入左子树查找，否则进入右子树查找

1
2
3
4
5
6
7
8
9
10
TREE-SEARCH(T, k)
	x = T
	while x != NULL
		if x.key == k
			return x
		else if x.key > k
			x = x.right
		else 
			x = x.left
	return NULL

插入

同样是根据二叉查找树的性质，找到合适的叶子节点插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TREE-INSERT(T, z)
	x = T
	// y记录要插入的父节点
	while x != NULL
		y = x
		else if x.key > z.key
			x = x.right
		else 
			x = x.left
	z.p = y
	if y == NULL
		T = z
	else if z.key > y.key
		y.right = z
	else
		y.left = z

删除

删除分三种情况：

  • 如果删除的节点是叶子节点，则直接删除
  • 如果删除的节点只有一个孩子节点，则将孩子节点代替删除的节点位置
  • 如果删除的节点有左右子树，则找到其前驱节点或者后继节点代替删除节点位置，前驱节点或者后继节点必定只有一个孩子节点，接着按照情况2删除前驱节点或者后继节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 用y结点代替x结点
REPLACE(T, x, y)
	if x.p == NULL
		T = y
	else if x.p.left == x
		x.p.left = y
	else
		x.p.right = y
	if y != NULL
		y.p = x.p
		
		
// 删除z结点
TREE-DELETE(T, z)
	if z.right == NULL
		REPLACE(T, z, z.left)
	else if z.left == NULL
		REPLACE(T, z, z.right)
    else
        y = z.right
        while y.left != NULL
        	y = y.left
        REPLACE(T, y, y.right)
        y.right = z.right
        y.right.p = y
        REPLACE(T, z, y)
        y.left = z.left
        y.left.p = y

红黑树

讲完二叉查找树终于轮到我们在主角，红黑树。由于当二叉查找树插入的节点值按照顺序，则形成的二叉树和链表相同，无法提高查找的效率，因此引入红黑树。

red_black_tree

性质

  • 每个结点都有颜色属性，不是黑色就是红色

  • 根节点是黑色的

  • 每一个叶结点都是黑色的，叶结点值为NULL，不存储值

  • 如果一个结点是红色的，则它的两个叶子结点都是黑色的
  • 对于每一个结点，从该结点到其所有后代叶结点的路径经过的黑结点数目相同（黑结点的数目称为该节点的黑高）

一棵有n个结点的红黑树的高度至多为2lg(n+1)

表示

在二叉查找树的基础上每个结点加入color属性，表示结点的颜色。

认为所有的叶子结点都为NULL，就是指向空指针，颜色可以人为认为为黑色。

旋转

子树的左旋转和右旋转是红黑树中的常用操作,分为左旋转和右旋转，如下图

Tree_rolation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 左旋转
LEFT-ROTAET(T, p)
    y = p.right
    p.right = y.left
    if y.left != NULL
    	y.left.p = p
    y.p = p.p
    if p.p == NULL
    	T = y
    else if p == p.p.left
    	p.p.left = y
    else p.p.right = y
    y.left = p
    p.p = y

右旋的代码和左旋的差不多，就是left换成right

查找

红黑树的查找和二叉查找树的查找过程是一样的，由于一棵有n个结点的红黑树的高度至多为2lg(n+1)，所以查找的时间复杂度为Olg(n)

插入

红黑是的插入而二叉查找树的插入是一样的，但是插入到红黑树的节点的颜色赋值为RED，这样有可能会破坏红黑树的性质，需要进行后续的修复。

1
2
3
TREE-INSERT(T, z)
z.color = RED
RB-INSERT-FIXUP(T, z)

修复

之所以需要修复是因为将插入的节点颜色变为红色，可能会违反红黑树的性质，需要修复的情况只会出现在插入的点是根节点或者插入节点的父节点是红色，违反了红黑树的第二条和第四条性质。如果插入的节点父节点是黑色，不会违反任何性质。

插入修复分四种情况：

  • 情况1：如果插入为根节点
  • 情况2：如果当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色
  • 情况3：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子
  • 情况4：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
RB-INSERT-FIXUP(T, z)
    while z.p.color == RED
        if z.p == z.p.p.left
        	y = z.p.p.right						//y始终指向其叔叔节点
            if y.color == RED
                z.p.color = BLACK               //Case 2
                y.color = BLACK                 //Case 2
                z.p.p.color = RED               //Case 2
                z = z.p.p                       //Case 2
            else if z == z.p.right
                z = z.p                         //Case 3
                LEFT-ROTATE(T, z)               //Case 3
            z.p.color = BLACK                   //Case 4
            z.p.p.color = RED                   //Case 4
            RIGHT-ROTATE(T, z.p.p)              //Case 4
        else (same as then clause with "right" and "left" exchanged)
        // 如果当前节点的父节点是祖父节点的右节点，情况一样，调换left和right即可
    T.root.color ← BLACK						//Case1

  • 如果插入为根节点

    直接将其颜色改为黑色即可，代码的最后一句

  • 如果当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色

    当前节点的父节点和叔叔节点涂黑，祖父结点涂红，由于把祖父节点变红，这样又是一个将节点变红需要修复问题，所有针对祖父节点再次判断情况（z指向z的祖父重新进入循环）。

    1
    2
    3
    4
    5
    if y.color == RED
       z.p.color = BLACK               //Case 2
       y.color = BLACK                 //Case 2
       z.p.p.color = RED               //Case 2
       z = z.p.p                       //Case 2

    示意图插入节点4

    red-black-insert1

  • 当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子

    当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。这样就会将该情况转为情况4

    示意图：再插入节点4后经过情况2的处理，转为对4的祖父进行修复，进入当前(情况3)修复，转为情况4

    red-black-insert2

  • 当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左子

    父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋

    示意图由情况三旋转转为当前情况后处理

    red-black-insert3

删除

红黑树的删除和二叉查找树的删除几乎相同，不同的是需要处理颜色，当删除节点无左子树或右子树时，直接删除，而当删除节点有左子树和右子树时，需要将后继节点代替删除节点，同时颜色赋值为删除节点的颜色，后继节点直接删除，相当于删除的是后继节点。

当删除的节点（当删除节点有左子树和右子树时，删除的是其后继节点）颜色是黑色时需要修复，因为删除黑色的节点必定会破坏性质5，除非树中只有一个根节点。

修复

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
RB-DELETE-FIXUP(T, x)
while x != T and x.color == BLACK  
	if x == x.p.eft 
    	w = x.p.right
        	if w.color == RED  
            	color[w] = BLACK                      //Case 1  
            	x.p.color = RED                       //Case 1  
            	LEFT-ROTATE(T, x.p)                   //Case 1  
             	w = x.p.right                         //Case 1  
			if w.left.color = BLACK and w.right.color = BLACK  
            	w.color = RED                         //Case 2  
            	x = p[x]                              //Case 2  
			else if w.right.color = BLACK  
					w.left.color = BLACK          	  //Case 3  
					w.color = RED                     //Case 3  
					RIGHT-ROTATE(T, w)                //Case 3  
					w = right[p[x]]                   //Case 3  
				w.color = color[p[x]]                 //Case 4  
                x.p.color = BLACK                     //Case 4  
                w.right.color = BLACK                 //Case 4  
                LEFT-ROTATE(T, p[x])                  //Case 4 
                x = T                                 //Case 4  
       else (same as then clause with "right" and "left" exchanged)  
x.color = BLACK

“我们从被删节点后来顶替它的那个节点开始调整，并认为它有额外的一重黑色。这里额外一重黑色是什么意思呢，我们不是把红黑树的节点加上除红与黑的另一种颜色，这里只是一种假设，我们认为我们当前指向它，因此空有额外一种黑色，可以认为它的黑色是从它的父节点被删除后继承给它的，它现在可以容纳两种颜色，如果它原来是红色，那么现在是红+黑，如果原来是黑色，那么它现在的颜色是黑+黑。有了这重额外的黑色，原红黑树性质5就能保持不变。现在只要恢复其它性质就可以了，做法还是尽量向根移动和穷举所有可能性。”–saturnman。

先解决两种简单的情况：

  • 当前节点颜色是红+黑，直接将该节点改为黑色
  • 当前节点颜色是黑+黑且是根节点， 那么就可以结束

接下里重点解决下面三种情况：

  • 情况1：当前节点颜色是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)

    (01) 将兄弟节点设为黑色。

    (02) 将父节点设为红色。

    (03) 对父节点进行左旋。

    (04) 左旋后，重新设置兄弟节点为新的当前节点。

    这样做可以将情况1转为情况2、3或4

    示意图：

    red-black-delete1

  • 情况2：当前节点颜色是黑+黑且兄弟是黑色且兄弟节点的两个子节点全为黑色

    (01) 将兄弟节点设为红色。

    (02) 设置父节点为新的当前节点

    示意图：

    red-black-delete2

  • 情况3：当前节点颜色是黑+黑，兄弟节点是黑色，兄弟的左子是红色，右子是黑色

    (01) 将兄弟节点的左孩子设为“黑色”。

    (02) 将兄弟节点设为“红色”。

    (03) 对兄弟节点进行右旋。

    (04) 右旋后，重新设置兄弟节点为新的当前节点。

    示意图：

    red-black-delete3

  • 情况4：当前节点颜色是黑+黑色，它的兄弟节点是黑色，但是兄弟节点的右子是红色，兄弟节点左子的颜色任意

    (01) 将父节点的颜色赋值给 兄弟节点。

    (02) 将父节点设为黑色。

    (03) 将兄弟节点的右子节点设为黑色。

    (04) 对父节点进行左旋。

    (05) 把根节点设置成新的当前节点，处理完毕

    示意图：

    red-black-delete4

红黑树的复杂度

一棵有n个结点的红黑树的高度至多为2lg(n+1)，因此查找的时间复杂度为O(lg n)

红黑树在最坏情况下基本动态集合操作的时间复杂度是O(lgn)

红黑树与AVL树（平衡二叉树）

AVL树是严格的平衡二叉树，必须满足左右子树的高度差不超过1，因此维持平衡的代价要高于红黑树，但是由于AVL树的平衡性好于二叉树，因此在查找方面要由于红黑树。

因此如果插入删除不频繁，只是对查找要求较高，那么AVL是较优于红黑树的。

如果插入删除较为频繁，红黑树维持平衡的代价要远小于AVL树，红黑树具有优势。

参考

《算法导论》

https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91

https://my.oschina.net/edwardge/blog/1833893

https://blog.csdn.net/v_july_v/article/details/6105630

0%