建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
推薦在看算法導(dǎo)論的這一章之前先看看嚴(yán)蔚敏老師在《數(shù)據(jù)結(jié)構(gòu)》上的二叉查找樹。
整體來說二叉查找樹不難，就是插入和刪除節(jié)點(diǎn)時(shí)讓人糾結(jié)，我就是在刪除節(jié)點(diǎn)時(shí)各種糾結(jié)了。
二叉樹執(zhí)行基本操作的時(shí)間與樹的高度成正比。
首先說下二叉查找樹的性質(zhì)：
設(shè)x為二叉查找樹中的一個(gè)結(jié)點(diǎn)。如果y是x的左子樹中的一個(gè)結(jié)點(diǎn)，則key[y]<=key[x];如果y是x的右子樹的一個(gè)結(jié)點(diǎn)，則key[y]>=key[x]。
注意這個(gè)性質(zhì)，和堆對(duì)比下，還是有區(qū)別的，并且這個(gè)性質(zhì)表示二叉查找樹的根節(jié)點(diǎn)的左子樹中所有結(jié)點(diǎn)都小于根結(jié)點(diǎn)，所有右子樹的結(jié)點(diǎn)都大于根結(jié)點(diǎn)。所以根據(jù)這個(gè)性質(zhì)，可以用中序訪問二叉查找數(shù)來實(shí)現(xiàn)從小大到排列。
首先看看這個(gè)二叉查找樹(P151圖12-1(a))：
圖1
按中序遍歷結(jié)果為：
2->3->5->5->7->8
接下來說說二叉查找樹的幾個(gè)操作：
SEARCH:查找關(guān)鍵字等于key的結(jié)點(diǎn)
MINIMUM:找出關(guān)鍵字最小的結(jié)點(diǎn)
MAXIMUM:找出關(guān)鍵字最大的結(jié)點(diǎn)
SUCCESSOR:找出結(jié)點(diǎn)x的后繼y
INSERT:在二叉查找樹中插入結(jié)點(diǎn)z
DELETE:在二叉查找樹中刪除結(jié)點(diǎn)z
里面就INSERT和DELETE麻煩一些。
首先逐步分析代碼：
①.BST的數(shù)據(jù)結(jié)構(gòu)：
1
2
3
4
|
typedef struct Node{
int key;
Node *lchild, *rchild, *parent;
}Node, *BSTree;
|
②.BST的中序遍歷：
根據(jù)BST的性質(zhì)，對(duì)于一個(gè)根結(jié)點(diǎn)x，所以比x小的結(jié)點(diǎn)都在x的左子樹中，所有比x大的結(jié)點(diǎn)都在x的右子樹中，并且沒一個(gè)結(jié)點(diǎn)都滿足這個(gè)性質(zhì)，所以可以利用中序遍歷，按從小到大的順序輸出這個(gè)BST。
代碼如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
// 遞歸版本
Node * BSTreeSearch(BSTree T, int k)
{
if(T == NULL || k == T->key)
return T;
if(k < T->key)
return BSTreeSearch(T->lchild, k);
else
return BSTreeSearch(T->rchild, k);
}
// 非遞歸版本
BSNode * IterativeBSTreeSearch(BSTree T, int k)
{
while(T != NULL && k != T->key)
{
if(k < T->lchild->key);
x = T->lchild;
else
x = T->rchild;
}
return x;
}
|
③.BST的最大值與最小值：
依然是利用BST的左子樹結(jié)點(diǎn)，根結(jié)點(diǎn)，右子樹結(jié)點(diǎn)的大小關(guān)系，不解釋。。。
代碼如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
Node * BSTreeMinimum(BSTree T)
{
while(T->lchild != NULL)
T = T->lchild;
return T;
}
Node * BSTreeMaximum(BSTree T)
{
while(T->rchild != NULL)
T = T->rchild;
return T;
}
|
下面開始有些麻煩了。
④.BST的后繼：
這是其偽代碼：
1
2
3
4
5
6
7
8
|
TREE-SUCCESSOR(x)
1 if right[x] ≠ NIL
2 then return TREE-MINIMUM (right[x])
3 y ← p[x]
4 while y ≠ NIL and x = right[y]
5 do x ← y
6 y ← p[y]
7 return y
|
根據(jù)其后繼的特性，結(jié)點(diǎn)x的后繼是具有大于key[x]中的關(guān)鍵字最小者的那個(gè)結(jié)點(diǎn)。
第1~2行，x的右子樹的結(jié)點(diǎn)都是大于key[x]的結(jié)點(diǎn)，所以如果x有右子樹，則在右子樹中尋找最小值
第3~6行，如果沒有右子樹，則其后繼y,是x的父親結(jié)點(diǎn)的第一個(gè)右子樹(考慮為什么呢？根據(jù)特性：結(jié)點(diǎn)x的后繼是具有大于key[x]中的關(guān)鍵字最小者的那個(gè)結(jié)點(diǎn)。因?yàn)閤沒有右子樹，所以這時(shí)，按中序遍歷的x下一個(gè)結(jié)點(diǎn)即后繼，應(yīng)該是這樣一個(gè)子樹的根結(jié)點(diǎn)y，x的祖先是其左孩子，這樣，y就大于其左子樹所有結(jié)點(diǎn)，并且因?yàn)閤是y的左子樹中最大的結(jié)點(diǎn)了)。這個(gè)說著肯定是云里霧里，還是看圖分析最好了，依然利用上面的圖1：
葉子結(jié)點(diǎn)5的后繼是根結(jié)點(diǎn)5.
具體代碼如下：
1
2
3
4
5
6
7
8
9
10
11
12
|
Node *BSTreeSuccessor(Node *x)
{
if(x->rchild != NULL)
return BSTreeMinimum(x->rchild);
Node *y = x->parent;
while(y != NULL && x == y->rchild)
{
x = y;
y = y->parent;
}
return y;
}
|
⑤.BST的插入：
比如要把結(jié)點(diǎn)z插入二叉查找數(shù)T中，分以下幾步：
1.將key[z]從根結(jié)點(diǎn)x開始比較，并用y記錄x的父親結(jié)點(diǎn)，直到到達(dá)最后一層某一葉節(jié)點(diǎn)比較完,此時(shí)y指向某一葉節(jié)點(diǎn),x是NULL。
2.如果此時(shí)y是NULL，則證明是空樹，于是根結(jié)點(diǎn)就是z
3.否則如果key[z]小于key[y]，則讓left[y] = z；當(dāng)key[z]大于或等于key[y]，則讓right[y] = z。
插入就是那么簡(jiǎn)單。
看看偽代碼，就是按這個(gè)步驟來的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
TREE-INSERT(T, z)
1 y ← NIL
2 x ← root[T]
3 while x ≠ NIL
4 do y ← x
5 if key[z] < key[x]
6 then x ← left[x]
7 else x ← right[x]
8 p[z] ← y
9 if y = NIL
10 then root[T] ← z // Tree T was empty
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z
|
具體的代碼如下：
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
|
void BSTreeInsert(BSTree &T, int k)
{
Node *y = NULL;
Node *x = T;
Node *z = new Node;
z->key = k;
z->lchild = z->parent = z->rchild = NULL;//////////
while(x != NULL)
{
y = x;
if(k < x->key)
x = x->lchild;
else
x = x->rchild;
}
z->parent = y;
if(y == NULL)
{
T = z;
}
else
if(k < y->key)
y->lchild = z;
else
y->rchild = z;
}
|
⑥.BST的刪除：
比如要把二叉查找數(shù)T中的z結(jié)點(diǎn)刪除掉，這是要分三種情況：
1.z沒有左子樹和右子樹：
汗，這個(gè)就是直接刪除z，把z的父親結(jié)點(diǎn)parent[z]指向z的子樹設(shè)置為NULL。
如圖，直接刪除z，并讓結(jié)點(diǎn)12的右子樹為NULL。
2.z只有左子樹或者只有右子樹：
這個(gè)是讓z的子樹與其父親結(jié)點(diǎn)相連，刪除z即可。
如圖，此時(shí)直接刪除z，并讓z的子樹20的父親結(jié)點(diǎn)變成z的父親結(jié)點(diǎn)15。
3.z既有左子樹又有右子樹：
這是先用SUCCESSOR找到z的后繼y，因?yàn)閥一定沒有左子樹(考慮為什么？下面解釋)，所以可以刪除y，并讓y的父親結(jié)點(diǎn)成為y的右子樹的父親結(jié)點(diǎn)(類似第2中情況)，并用y的key代替z的key。
如圖,y的右子樹7成為10的子樹，并且y取代了z的未知。
這是我們來考慮一個(gè)關(guān)鍵問題，y為何一定沒有左子樹？(習(xí)題12.2-5)
答：因?yàn)閥是z的后繼，所以y是z的右子樹中最小的一個(gè)結(jié)點(diǎn)，如果y還有左子樹，則y的左子樹中的結(jié)點(diǎn)一定比y小！
具體代碼如下：
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* BSTreeDelete(BSTree T, Node *z)
{
Node *x, *y;
// z是要?jiǎng)h除的節(jié)點(diǎn),而y是要替換z的節(jié)點(diǎn)
if(z->lchild == NULL || z->rchild == NULL)
y = z; // 當(dāng)要?jiǎng)h除的z至多有一個(gè)子樹，則y=z；
else
y = BSTreeSuccessor(z); // y是z的后繼
if(y->lchild != NULL)
x = y->lchild;
else
x = y->rchild;
if(x != NULL)
x->parent = y->parent; //如果y至多只有一個(gè)子樹，則使y的子樹成為y的父親節(jié)點(diǎn)的子樹
if(y->parent == NULL) // 如果y沒有父親節(jié)點(diǎn)，則表示y是根節(jié)點(diǎn)，詞典其子樹x為根節(jié)點(diǎn)
T = x;
else if(y == y->parent->lchild)
// 如果y是其父親節(jié)點(diǎn)的左子樹，則y的子樹x成為其父親節(jié)點(diǎn)的左子樹，
// 否則成為右子樹
y->parent->lchild = x;
else
y->parent->rchild = x;
if(y != z)
z->key = y->key;
return y;
}
|
下面是整個(gè)二叉查找樹的實(shí)現(xiàn)：
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
/*
* Author: Tanky Woo
* Blog: www.WuTianQi.com
* Description: 《算法導(dǎo)論》第12章 BST
*/
#include <iostream>
#define NULL 0
using namespace std;
// ①
typedef struct Node{
int key;
Node *lchild, *rchild, *parent;
}Node, *BSTree;
// ②
Node * BSTreeSearch(BSTree T, int k)
{
if(T == NULL || k == T->key)
return T;
if(k < T->key)
return BSTreeSearch(T->lchild, k);
else
return BSTreeSearch(T->rchild, k);
}
/*
BSNode * IterativeBSTreeSearch(BSTree T, int k)
{
while(T != NULL && k != T->key)
{
if(k < T->lchild->key);
x = T->lchild;
else
x = T->rchild;
}
return x;
}
*/
// ③
Node * BSTreeMinimum(BSTree T)
{
while(T->lchild != NULL)
T = T->lchild;
return T;
}
Node * BSTreeMaximum(BSTree T)
{
while(T->rchild != NULL)
T = T->rchild;
return T;
}
// ④
Node *BSTreeSuccessor(Node *x)
{
if(x->rchild != NULL)
return BSTreeMinimum(x->rchild);
Node *y = x->parent;
while(y != NULL && x == y->rchild)
{
x = y;
y = y->parent;
}
return y;
}
// ⑤
void BSTreeInsert(BSTree &T, int k)
{
Node *y = NULL;
Node *x = T;
Node *z = new Node;
z->key = k;
z->lchild = z->parent = z->rchild = NULL;
while(x != NULL)
{
y = x;
if(k < x->key)
x = x->lchild;
else
x = x->rchild;
}
z->parent = y;
if(y == NULL)
{
T = z;
}
else
if(k < y->key)
y->lchild = z;
else
y->rchild = z;
}
// ⑤
Node* BSTreeDelete(BSTree T, Node *z)
{
Node *x, *y;
// z是要?jiǎng)h除的節(jié)點(diǎn),而y是要替換z的節(jié)點(diǎn)
if(z->lchild == NULL || z->rchild == NULL)
y = z; // 當(dāng)要?jiǎng)h除的z至多有一個(gè)子樹，則y=z；
else
y = BSTreeSuccessor(z); // y是z的后繼
if(y->lchild != NULL)
x = y->lchild;
else
x = y->rchild;
if(x != NULL)
x->parent = y->parent; //如果y至多只有一個(gè)子樹，則使y的子樹成為y的父親節(jié)點(diǎn)的子樹
if(y->parent == NULL) // 如果y沒有父親節(jié)點(diǎn)，則表示y是根節(jié)點(diǎn)，詞典其子樹x為根節(jié)點(diǎn)
T = x;
else if(y == y->parent->lchild)
// 如果y是其父親節(jié)點(diǎn)的左子樹，則y的子樹x成為其父親節(jié)點(diǎn)的左子樹，
// 否則成為右子樹
y->parent->lchild = x;
else
y->parent->rchild = x;
if(y != z)
z->key = y->key;
return y;
}
void InBSTree(BSTree T)
{
if(T != NULL)
{
InBSTree(T->lchild);
cout << T->key << " ";
InBSTree(T->rchild);
}
}
int main()
{
int m;
BSTree T = NULL;
for(int i=0; i<6; ++i)
{
cin >> m;
BSTreeInsert(T, m);
cout << "二叉查找樹中序查找：";
InBSTree(T);
cout << endl;
}
cout << "刪除根節(jié)點(diǎn)后：";
BSTreeDelete(T, T);
InBSTree(T);
}
|
結(jié)果如圖：
OK,BST分析完了，這一章一定要搞懂，否則下一章的Red-Black-Tree就會(huì)一抹黑了~~
在我獨(dú)立博客上的原文：http://www.wutianqi.com/?p=2430
歡迎大家互相學(xué)習(xí)，互相討論！