《算法导论》学习总结 — 14. 第13章红黑树(3)

港控/mmm° 2021-12-11 04:15 216阅读 0赞

建议先看看前言：[http://www.cnblogs.com/tanky\_woo/archive/2011/04/09/2010263.html][http_www.cnblogs.com_tanky_woo_archive_2011_04_09_2010263.html]

这一篇是关于红黑树的结点删除。

依然和上一篇的插入一样，先用到了BST的删除结点函数，然后做相应的调整。

不过，这里的调整思路颇为新颖。

还是来看看略微改变后的删除结点函数：

注意代码倒数第二和第三行，只有当后继结点y的颜色是黑色时，才做调整。

由此，引导出几个问题：

1.问：考虑为何当y的颜色是黑色时，才调整？当y的颜色是红黑时，会不会破坏性质4？

答：这里我一开始纠结了，后来反复看了几次BST的删除，再算想通。在BST中，删除结点z，并不是真的把z给移除了，其实删除的不是z，而是y！因为z始终没有动过，只是把y删除了，然后把y的key赋值给z的key。所以，在红黑树中，z的颜色没有变，依然符合红黑性质。（这里我先开始理解为y->color也要赋值给z->color，汗。。。）

2.问：考虑y为黑色时，破坏了哪几条红黑性质？

答：当y是根时，且y的一个孩子是红色，若此时这个孩子成为根结点。———>破坏了性质2

当x和p\[y\]都是红色时。                                                    ———>破坏了性质4

包含y的路径中，黑高度都减少了。                                      ———>破坏了性质5

解决方法：

上一篇我解释过，性质五涉及到了整棵树，难以控制。

因此将x的颜色增加一重黑色，那么当:

①.x原先颜色为RED时——->x包含RED和BLACK两颜色

②.x原先颜色是BLACK时—–>x包含BLACK, BLACK两颜色。

此时性质5解决，但是又破坏了性质1.

接下来就是恢复性质1，2，4了。

将额外的一重黑色一直沿树向上移，直到x是根或者是红色结点。

看看具体的实现代码：

<table style="border-right:rgb(204,204,204) 1px solid;border-top:rgb(204,204,204) 1px solid;border-left:rgb(204,204,204) 1px solid;border-bottom:rgb(204,204,204) 1px solid;border-collapse:collapse;"> 
 <tbody> 
 <tr> 
 <td style="border-right:rgb(204,204,204) 1px solid;border-top:rgb(204,204,204) 1px solid;vertical-align:top;border-left:rgb(204,204,204) 1px solid;color:#808080;border-bottom:rgb(204,204,204) 1px solid;text-align:right;"><pre style="clear:none;font-size:12px;line-height:1.333;">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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
</pre></td> 
 <td style="border-right:rgb(204,204,204) 1px solid;border-top:rgb(204,204,204) 1px solid;vertical-align:top;border-left:rgb(204,204,204) 1px solid;border-bottom:rgb(204,204,204) 1px solid;"><pre><code>void RBDeleteFixup(RBTree &amp;T, Node *x)
{ 
	while(x != T &amp;&amp; x-&gt;color == BLACK)
	{ 
		if(x == x-&gt;parent-&gt;lchild)
		{ 
			Node *w = x-&gt;parent-&gt;rchild;
			/ Case 1 /
			if(w-&gt;color == RED)
			{ 
				w-&gt;color = BLACK;
				x-&gt;parent-&gt;color = RED;
				LeftRotate(T, x-&gt;parent);
				w = x-&gt;parent-&gt;rchild;
			}
			/ Case 2 /
			if(w-&gt;lchild-&gt;color == BLACK &amp;&amp; w-&gt;rchild-&gt;color == BLACK)
			{ 
				w-&gt;color = RED;
				x = x-&gt;parent;
			}
			else
			{ 
				/ Case 3 /
				if(w-&gt;rchild-&gt;color == BLACK)
				{ 
					w-&gt;lchild-&gt;color = BLACK;
					w-&gt;color = RED;
					RightRotate(T, w);
					w = x-&gt;parent-&gt;rchild;
				}
				/ Case 4 /
				w-&gt;color = x-&gt;parent-&gt;color;
				x-&gt;parent-&gt;color = BLACK;
				w-&gt;rchild-&gt;color = BLACK;
				LeftRotate(T, x-&gt;parent);
				x = T;
			}
		}
		else
		{ 
			Node *w = x-&gt;parent-&gt;lchild;
			if(w-&gt;color == RED)
			{ 
				w-&gt;color = BLACK;
				x-&gt;parent-&gt;color = RED;
				RightRotate(T, x-&gt;parent);
				w = x-&gt;parent-&gt;lchild;
			}
			if(w-&gt;lchild-&gt;color == BLACK &amp;&amp; w-&gt;rchild-&gt;color == BLACK)
			{ 
				w-&gt;color = RED;
				x = x-&gt;parent;
			}
			else
			{ 
				if(w-&gt;lchild-&gt;color == BLACK)
				{ 
					w-&gt;rchild-&gt;color = BLACK;
					w-&gt;color = RED;
					LeftRotate(T, w);
					w = x-&gt;parent-&gt;lchild;
				}
				w-&gt;color = x-&gt;parent-&gt;color;
				x-&gt;parent-&gt;color = BLACK;
				w-&gt;lchild-&gt;color = BLACK;
				RightRotate(T, x-&gt;parent);
				x = T;
			}
		}
	}
	x-&gt;color = BLACK;
}</code></pre></td> 
 </tr> 
 </tbody> 
</table>

对于删除的调整，共八种情况(左右对称各四种)，这里在书上P175面讲的很详细，所以我也就不再画图了，大家可以自己拿起笔在草稿纸上画一画。

在我独立博客上的原文：[http://www.wutianqi.com/?p=2449][http_www.wutianqi.com_p_2449]

欢迎大家互相学习，互相进步！

转载于:https://www.cnblogs.com/tanky\_woo/archive/2011/05/11/2043064.html

[http_www.cnblogs.com_tanky_woo_archive_2011_04_09_2010263.html]: http://www.cnblogs.com/tanky_woo/archive/2011/04/09/2010263.html
[http_www.wutianqi.com_p_2449]: http://www.wutianqi.com/?p=2449