二叉の並べ替えツリーの削除、検索、挿入の繰り返しが実現されます.
50313 ワード
同前
@Author:張海抜
@Update:2014-01-24
@Link: http://www.cnblogs.com/zhanghaiba/p/3532885.html
反復実装の難しさは削除操作です.
難点1は、様々な状況における削除(論理的難点)を明確にしたい場合であり、難点2は反復実施中の削除操作において、一般的にポインタに関するポインタ(C言語実現困難点)である.
難点1解答――
削除に伴う検索プロセスは、削除すべき点が見つからない場合は操作を無視し、削除すべきノードDが見つかったら、3つの状況に分けられる.
1)Dに左の子供がいるなら、BSTシーケンス(中のシーケンス:小さいから大きいまで)では、Dは少なくとも直接の前駆ノードCが存在し、Cは必ずDノードの左のサブツリーの中の値が一番大きいノードであると説明する.
「直接」という条件を満たすためには、CはDの左側に近いので、CはDノードの左サブツリーの最大ノードであることが必要である.
左の子の木もBSTで、左の子の木の自身が右の子供がないならば木の根は最大です.左の子の木の一番右の子が一番大きいです.
言い換えれば、CはDの左の子供かDの左の子供の右の子供です.(右の子供がいないのがCの特徴です.さもなければ最大ではないです.)
Cを指すポインタが得られ、DにCの値が割り当てられます.配列[2,3,5,7,9,11,13]のように[2,3,5,5,9,11,13]が[D=7]に変化します.
この時、CとDの両方の結点交換位置があると考えられます.(Cを削除してもBSTです.)ので、問題は削除Dから削除Cに変換されます.(Cは固定的な特徴があるので)
私たちはCを指すポインタqを持っていますが、Cの特徴は右の子供がいない(左の子供がいるとは限らない)ことです.Cの直接の先駆者はその左の子供です.
したがって、残りの作業は、Cを指していたポインタqをCの左の子供に向け、Cノードメモリを解放することである.
2)Dが左の子供がいないが、右の子供がいる場合、BST順序では、Dは直接的な後継ノードEが存在し、Eは必ずDノードの右のサブツリーの中の最小ノードであると説明する.
次の解析は1)の解析と対称である.
3)Dが葉っぱであれば、Dを直接削除し、Dを指すポインタをNULLにセットします.
難点2解答――
ポインタの針を使わないとき、ポインタpを削除すべき点Dに向けます.このpはDの親ノードのnextポインタのコピーにすぎません.
Dノードを解放するためには問題はないが、pをNULLにセットし、Dの親ノードのnextをNULLにセットしていない.
これは、葉を削除するという簡単な状況では、ほぼ間違いが発生します(不正メモリにアクセスしました).
ですから、まずrootを保存してください.link*p=&rootを設定して、常にポインタの針を保存します.
C(本当に削除するノード)を見つけた時(Cが満たす条件は(*p)->right==NULL)、＊pがCの親ノードのnextです.これで正しい修正ができます.
また、BSTの最後のノードが削除された後に、まだrootであればエラーが発生します.rootと**pはノードメモリを共有しています.
この場合は、*pだけでなくNULLに置く必要があります.rootもNULLにするので、コードを追加します.
言及に値するのは、
ここでは、「二叉並べ替えツリーの削除、検索、挿入の再帰的な実現」を繰り返します. link(public) ",削除操作は正しいですが、具体的には違いがあります.
下の木を見て、50のノードを削除するとき――
再帰的に実現すると、50を削除すると38(50は38になる)を再帰的に削除し、38を削除して再帰的に36を削除する(38は36になる).最後に36の葉を削除することにまとめる(元の36).
反復実装では、50を削除すると38は50に割り当てられ、38(元の38)を直接削除し、38を指すポインタ(ルートノードのnextポインタ)を元の38ノードを指す左の子供に変更します.
次の二叉の順序付けツリーの完全な反復実装と削除状況が十分に多いテストの例示.
テストのモデル:
同前
@Author:張海抜
@Update:2014-01-24
@Link: http://www.cnblogs.com/zhanghaiba/p/3532885.html
反復実装の難しさは削除操作です.
難点1は、様々な状況における削除(論理的難点)を明確にしたい場合であり、難点2は反復実施中の削除操作において、一般的にポインタに関するポインタ(C言語実現困難点)である.
難点1解答――
削除に伴う検索プロセスは、削除すべき点が見つからない場合は操作を無視し、削除すべきノードDが見つかったら、3つの状況に分けられる.
1)Dに左の子供がいるなら、BSTシーケンス(中のシーケンス:小さいから大きいまで)では、Dは少なくとも直接の前駆ノードCが存在し、Cは必ずDノードの左のサブツリーの中の値が一番大きいノードであると説明する.
「直接」という条件を満たすためには、CはDの左側に近いので、CはDノードの左サブツリーの最大ノードであることが必要である.
左の子の木もBSTで、左の子の木の自身が右の子供がないならば木の根は最大です.左の子の木の一番右の子が一番大きいです.
言い換えれば、CはDの左の子供かDの左の子供の右の子供です.(右の子供がいないのがCの特徴です.さもなければ最大ではないです.)
Cを指すポインタが得られ、DにCの値が割り当てられます.配列[2,3,5,7,9,11,13]のように[2,3,5,5,9,11,13]が[D=7]に変化します.
この時、CとDの両方の結点交換位置があると考えられます.(Cを削除してもBSTです.)ので、問題は削除Dから削除Cに変換されます.(Cは固定的な特徴があるので)
私たちはCを指すポインタqを持っていますが、Cの特徴は右の子供がいない(左の子供がいるとは限らない)ことです.Cの直接の先駆者はその左の子供です.
したがって、残りの作業は、Cを指していたポインタqをCの左の子供に向け、Cノードメモリを解放することである.
2)Dが左の子供がいないが、右の子供がいる場合、BST順序では、Dは直接的な後継ノードEが存在し、Eは必ずDノードの右のサブツリーの中の最小ノードであると説明する.
次の解析は1)の解析と対称である.
3)Dが葉っぱであれば、Dを直接削除し、Dを指すポインタをNULLにセットします.
難点2解答――
ポインタの針を使わないとき、ポインタpを削除すべき点Dに向けます.このpはDの親ノードのnextポインタのコピーにすぎません.
Dノードを解放するためには問題はないが、pをNULLにセットし、Dの親ノードのnextをNULLにセットしていない.
これは、葉を削除するという簡単な状況では、ほぼ間違いが発生します(不正メモリにアクセスしました).
ですから、まずrootを保存してください.link*p=&rootを設定して、常にポインタの針を保存します.
C(本当に削除するノード)を見つけた時(Cが満たす条件は(*p)->right==NULL)、＊pがCの親ノードのnextです.これで正しい修正ができます.
また、BSTの最後のノードが削除された後に、まだrootであればエラーが発生します.rootと**pはノードメモリを共有しています.
この場合は、*pだけでなくNULLに置く必要があります.rootもNULLにするので、コードを追加します.
言及に値するのは、
ここでは、「二叉並べ替えツリーの削除、検索、挿入の再帰的な実現」を繰り返します. link(public) ",削除操作は正しいですが、具体的には違いがあります.
下の木を見て、50のノードを削除するとき――
50
___|___
| |
38 65
_|__ _|__
| | | |
35 70
_|__ _|__
| | | |
36 68
_|__ _|__
| | | |
67
_|__
| |
/* 50 BST*/
38
___|___
| |
36 65
_|__ _|__
| | | |
35 70
_|__ _|__
| | | |
68
_|__
| |
67
_|__
| |
/* 50 BST*/
38
___|___
| |
35 65
_|__ _|__
| | | |
36 70
_|__ _|__
| | | |
68
_|__
| |
67
_|__
| |再帰的に実現すると、50を削除すると38(50は38になる)を再帰的に削除し、38を削除して再帰的に36を削除する(38は36になる).最後に36の葉を削除することにまとめる(元の36).
反復実装では、50を削除すると38は50に割り当てられ、38(元の38)を直接削除し、38を指すポインタ(ルートノードのnextポインタ)を元の38ノードを指す左の子供に変更します.
次の二叉の順序付けツリーの完全な反復実装と削除状況が十分に多いテストの例示.
1 /*
2 *Author: ZhangHaiba
3 *Date: 2014-1-24
4 *File: binary_search_tree_iter.c
5 *
6 *this demo shows how to build a BST data structure
7 *and support some command line to operate this BST
8 *such like i(insert), d(delete), s(search), q(quit) etc
9 *interestingly, this demo use tree module which written by Greg Lee
10 *making BST data structure and it's opreation visualization
11 *
12 *hint: implementation iterative
13 */
14
15 #include <stdio.h>
16 #include <stdlib.h>
17 #include <stdbool.h>
18 #define MOD 256
19 #define CMD_LEN 128
20
21 typedef struct node* link;
22
23 typedef struct node {
24 int item;
25 link left;
26 link right;
27 }node;
28
29 //public
30 link NODE(int item, link left, link right); //as constructor
31 link bst_insert(link root, int item);
32 link bst_delete(link root, int item);
33 link bst_search(link root, int item);
34 void bst_inorder(link root);
35 void bst_show_by_tree(link root);
36 //private
37 link* pre(link root);
38 link* next(link root);
39 void inorder(link root); //included in bst_inorder()
40 void tree_print(link root, FILE* fd); //included in bst_show_by_tree()
41
42 int main(void)
43 {
44
45 link r = NULL; //BST root
46
47 //operating this the BST r
48
49 /*** Command Line Manual ***/
50 /*
51 * "i 100" means insert item which value 100
52 * "d 200" means delete item which value 200
53 * "s 300" means search item which value 300
54 * "p" means call the tree module to print the BST tree
55 * "l" means list the inorder list of BST
56 * "q" means quit
57 */
58
59 while (true) {
60 char cmd[CMD_LEN];
61
62 scanf("%s", cmd);
63 if (cmd[0] == 'q')
64 break;
65 else if (cmd[0] == 'i' || cmd[0] == 'd' || cmd[0] == 's') {
66 int item;
67 scanf("%d", &item);
68 if (cmd[0] == 'i')
69 r = bst_insert(r, item);
70 else if (cmd[0] == 'd')
71 r = bst_delete(r, item);
72 else {
73 link aim_link = bst_search(r, item);
74 if (aim_link == NULL)
75 printf("Not Found!
");
76 else
77 printf("Found: %d
", aim_link->item);
78 }
79 }
80 else if (cmd[0] == 'p')
81 bst_show_by_tree(r);
82 else if (cmd[0] == 'l')
83 bst_inorder(r);
84 else
85 ; //ingnore illegal command line
86 }
87 return 0;
88 }
89
90 link NODE(int item, link left, link right)
91 {
92 link born = malloc(sizeof (node));
93 born->item = item;
94 born->left = left;
95 born->right = right;
96 return born;
97 }
98
99 link bst_insert(link root, int item)
100 {
101 if (root == NULL)
102 return NODE(item, NULL, NULL);
103 link p = root;
104 while (true) {
105 if (item < p->item) {
106 if (p->left != NULL)
107 p = p->left;
108 else {
109 p->left = NODE(item, NULL, NULL);
110 return root;
111 }
112 } else if (item > p->item) {
113 if (p->right != NULL)
114 p = p->right;
115 else {
116 p->right = NODE(item, NULL, NULL);
117 return root;
118 }
119 } else
120 return root;
121 }
122 }
123
124 link bst_delete(link root, int item)
125 {
126 if (root == NULL)
127 return NULL;
128 link save = root;
129 link *p = &root;
130 while (true) {
131 if (item < (*p)->item) {
132 if ((*p)->left != NULL)
133 p = &((*p)->left);
134 else
135 return save; //if search failed then delete nothing
136 } else if (item > (*p)->item) {
137 if ((*p)->right != NULL)
138 p = &((*p)->right);
139 else
140 return save;
141 } else {
142 if ((*p)->left != NULL) {
143 link *q = pre(*p);
144 (*p)->item = (*q)->item;
145 link del = *q;
146 *q = (*q)->left;
147 free(del);
148 } else if ((*p)->right != NULL) {
149 link *q = next(*p);
150 (*p)->item = (*q)->item;
151 link del = *q;
152 *q = (*q)->right;
153 free(del);
154 } else {
155 free(*p);
156 if (*p == save) //guarantee delete correctly in case: BST those have only one node
157 save = NULL;
158 *p = NULL;
159 }
160 return save;
161 }
162 }
163 }
164
165 link bst_search(link root, int item)
166 {
167 if (root == NULL)
168 return NULL;
169 link p = root;
170 while (true) {
171 if (item < p->item) {
172 if (p->left != NULL)
173 p = p->left;
174 else
175 return NULL;
176 } else if (item > p->item) {
177 if (p->right != NULL)
178 p = p->right;
179 else
180 return NULL;
181 } else
182 return p;
183 }
184 }
185
186 //guarantee root != NULL
187 link* pre(link root)
188 {
189 link *p = &(root->left);
190
191 while ((*p)->right != NULL)
192 p = &((*p)->right);
193 return p;
194 }
195
196 //guarantee root != NULL
197 link* next(link root)
198 {
199 link *p = &(root->right);
200
201 while ((*p)->left != NULL)
202 p = &((*p)->left);
203 return p;
204 }
205
206 void bst_inorder(link root)
207 {
208 inorder(root);
209 printf("
");
210 }
211
212 void inorder(link root)
213 {
214 if (root == NULL)
215 return;
216 inorder(root->left);
217 printf("%d ", root->item);
218 inorder(root->right);
219 }
220
221 void bst_show_by_tree(link root)
222 {
223 char cmd[CMD_LEN];
224
225 sprintf(cmd, "rm -f ./tree_src.txt");
226 system(cmd);
227
228 FILE *fd = fopen("./tree_src.txt", "a+");
229 fprintf(fd, "
\t\\tree");
230 tree_print(root, fd);
231 fprintf(fd, "
");
232 fclose(fd);
233
234 sprintf(cmd, "cat ./tree_src.txt | ~/tree/tree");
235 system(cmd);
236 }
237
238 void tree_print(link root, FILE *fd)
239 {
240 fprintf(fd, "(");
241 if (root != NULL) {
242 fprintf(fd, "%d", root->item);
243 tree_print(root->left, fd);
244 tree_print(root->right, fd);
245 }
246 fprintf(fd, ")");
247 }テストのモデル:
ZhangHaiba-MacBook-Pro:code apple$ ./a.out
p
i 50
p
50
_|__
| |
i 45 i 55
p
50
___|___
| |
45 55
_|__ _|__
| | | |
i 35 i 36 i 39 i 38
l
35 36 38 39 45 50 55
i 70 i 68 i 61 i 65 i 62 i 67
p
50
____|____
| |
45 55
_|__ __|___
| | | |
35 70
_|__ _|__
| | | |
36 68
_|__ _|__
| | | |
39 61
_|__ _|__
| | | |
38 65
_|__ ___|___
| | | |
62 67
_|__ _|__
| | | |
l
35 36 38 39 45 50 55 61 62 65 67 68 70
s 66
Not Found!
s 62
Found: 62
s 39
Found: 39
s 37
Not Found!
d 62
p
50
____|____
| |
45 55
_|__ __|___
| | | |
35 70
_|__ _|__
| | | |
36 68
_|__ _|__
| | | |
39 61
_|__ _|__
| | | |
38 65
_|__ _|__
| | | |
67
_|__
| |
d 45
p
50
____|____
| |
39 55
_|__ __|___
| | | |
35 70
_|__ _|__
| | | |
36 68
_|__ _|__
| | | |
38 61
_|__ _|__
| | | |
65
_|__
| |
67
_|__
| |
d 55
p
50
____|____
| |
39 61
_|__ __|___
| | | |
35 70
_|__ _|__
| | | |
36 68
_|__ _|__
| | | |
38 65
_|__ _|__
| | | |
67
_|__
| |
d 39
p
50
___|___
| |
38 61
_|__ _|__
| | | |
35 70
_|__ _|__
| | | |
36 68
_|__ _|__
| | | |
65
_|__
| |
67
_|__
| |
d 61
p
50
___|___
| |
38 65
_|__ _|__
| | | |
35 70
_|__ _|__
| | | |
36 68
_|__ _|__
| | | |
67
_|__
| |
d 50
p
38
___|___
| |
35 65
_|__ _|__
| | | |
36 70
_|__ _|__
| | | |
68
_|__
| |
67
_|__
| |
d 38 d 68 d 70 d 35 d 36 d 67
p
65
_|__
| |
d 65
p
i 99
p
99
_|__
| |
q同前