***

***
まず前言を見てみることをお勧めします.http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html
この1編は赤黒樹の結点削除についてです.
依然として前編の挿入と同様にBSTの削除ノード関数を先に用い,それから相応の調整を行う.
しかし、ここの調整構想は斬新だ.
または、少し変更された削除ノード関数を見てみましょう.

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

Node* RBTreeDelete(RBTree T, Node *z)
{
	Node *x, *y;
	// z       , y    z   
	if(z->lchild == NULL || z->rchild == NULL)   
		y = z;   //      z       ， y=z；
	else
		y = RBTreeSuccessor(z);  // y z   
	if(y->lchild != NULL)
		x = y->lchild;  
	else
		x = y->rchild;
	//      p[x] = p[y]
	x->parent = y->parent;  
	if(y->parent == NULL)   
		T = x;
	else if(y == y->parent->lchild)   
		y->parent->lchild = x;
	else
		y->parent->rchild = x;
	if(y != z)
		z->key = y->key;
	if(y->color == BLACK)
		RBDeleteFixup(T, x);
	return y;
}

注意コードの最後から2行目と3行目は、後続ノードyの色が黒である場合にのみ調整されます.
これにより、いくつかの問題が発生します.
1.問:yの色が黒の場合、なぜ調整するのかを考える.yの色が赤と黒の時、性質を破壊することができますか?
  答え:ここで私は最初は葛藤していましたが、BSTの削除を何度も繰り返し見て、納得しました.BSTでは、ノードzを削除して、本当にzを削除したわけではありませんが、実は削除したのはzではなく、yです!zは終始動いていないので、yを削除してyのkeyをzのkeyに割り当てます.したがって,赤黒樹ではzの色は変わらず,依然として赤黒の性質に合致している.△ここではまずy->colorもz->colorに値をつけなければならないと理解し始めました.汗..
2.問:yが黒であることを考えると、どの赤黒の性質を破壊しますか.
   答え:yが根であるとき、yの一人の子供が赤くて、もしこの子が根の結点になったら.———>性質を破壊した
        xとp[y]が共に赤色である場合.                                                    ———>性質を破壊した
        yを含む経路では,黒の高さが減少した.                                      ———>性質を破壊した
解決方法:
前編で説明したように、性質5は木全体に及んでおり、コントロールしにくい.
したがって、xの色を黒に変更すると、次のようになります.
①. x元の色がREDの場合->xはREDとBLACKの2色を含む
②. x元の色がBLACKの場合—>xはBLACK、BLACKの2色を含む.
このとき性質5は解決するが、また性質1を破壊する.
次は回復性1,2,4です.
xがルートまたは赤いノードになるまで、追加の黒をツリーに沿って上に移動します.
具体的な実装コードを見てみましょう.

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

void RBDeleteFixup(RBTree &T, Node *x)
{
	while(x != T && x->color == BLACK)
	{
		if(x == x->parent->lchild)
		{
			Node *w = x->parent->rchild;
			///////////// Case 1 /////////////
			if(w->color == RED)
			{
				w->color = BLACK;
				x->parent->color = RED;
				LeftRotate(T, x->parent);
				w = x->parent->rchild;
			}
			///////////// Case 2 /////////////
			if(w->lchild->color == BLACK && w->rchild->color == BLACK)
			{
				w->color = RED;
				x = x->parent;
			}
			else
			{
				///////////// Case 3 /////////////
				if(w->rchild->color == BLACK)
				{
					w->lchild->color = BLACK;
					w->color = RED;
					RightRotate(T, w);
					w = x->parent->rchild;
				}
				///////////// Case 4 /////////////
				w->color = x->parent->color;
				x->parent->color = BLACK;
				w->rchild->color = BLACK;
				LeftRotate(T, x->parent);
				x = T;
			}
		}
		else
		{
			Node *w = x->parent->lchild;
			if(w->color == RED)
			{
				w->color = BLACK;
				x->parent->color = RED;
				RightRotate(T, x->parent);
				w = x->parent->lchild;
			}
			if(w->lchild->color == BLACK && w->rchild->color == BLACK)
			{
				w->color = RED;
				x = x->parent;
			}
			else
			{
				if(w->lchild->color == BLACK)
				{
					w->rchild->color = BLACK;
					w->color = RED;
					LeftRotate(T, w);
					w = x->parent->lchild;
				}
				w->color = x->parent->color;
				x->parent->color = BLACK;
				w->lchild->color = BLACK;
				RightRotate(T, x->parent);
				x = T;
			}
		}
	}
	x->color = BLACK;
}

削除の调整については、8つの场合(左右対称各4つ)について、ここではP 175の面で详しく说明しているので、私も図を描かないで、みんなは自分でペンを持って草稿纸に1つ描くことができます.
私の独立したブログの原文:http://www.wutianqi.com/?p=2449
みんなが互いに討論することを歓迎して、いっしょに進歩します!