|
1 /* glpavl.c (binary search tree) */ |
|
2 |
|
3 /*********************************************************************** |
|
4 * This code is part of GLPK (GNU Linear Programming Kit). |
|
5 * |
|
6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, |
|
7 * 2009, 2010 Andrew Makhorin, Department for Applied Informatics, |
|
8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved. |
|
9 * E-mail: <mao@gnu.org>. |
|
10 * |
|
11 * GLPK is free software: you can redistribute it and/or modify it |
|
12 * under the terms of the GNU General Public License as published by |
|
13 * the Free Software Foundation, either version 3 of the License, or |
|
14 * (at your option) any later version. |
|
15 * |
|
16 * GLPK is distributed in the hope that it will be useful, but WITHOUT |
|
17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
|
18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public |
|
19 * License for more details. |
|
20 * |
|
21 * You should have received a copy of the GNU General Public License |
|
22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>. |
|
23 ***********************************************************************/ |
|
24 |
|
25 #include "glpavl.h" |
|
26 |
|
27 AVL *avl_create_tree(int (*fcmp)(void *info, const void *key1, |
|
28 const void *key2), void *info) |
|
29 { /* create AVL tree */ |
|
30 AVL *tree; |
|
31 tree = xmalloc(sizeof(AVL)); |
|
32 tree->pool = dmp_create_pool(); |
|
33 tree->root = NULL; |
|
34 tree->fcmp = fcmp; |
|
35 tree->info = info; |
|
36 tree->size = 0; |
|
37 tree->height = 0; |
|
38 return tree; |
|
39 } |
|
40 |
|
41 int avl_strcmp(void *info, const void *key1, const void *key2) |
|
42 { /* compare character string keys */ |
|
43 xassert(info == info); |
|
44 return strcmp(key1, key2); |
|
45 } |
|
46 |
|
47 static AVLNODE *rotate_subtree(AVL *tree, AVLNODE *node); |
|
48 |
|
49 AVLNODE *avl_insert_node(AVL *tree, const void *key) |
|
50 { /* insert new node into AVL tree */ |
|
51 AVLNODE *p, *q, *r; |
|
52 short int flag; |
|
53 /* find an appropriate point for insertion */ |
|
54 p = NULL; q = tree->root; |
|
55 while (q != NULL) |
|
56 { p = q; |
|
57 if (tree->fcmp(tree->info, key, p->key) <= 0) |
|
58 { flag = 0; |
|
59 q = p->left; |
|
60 p->rank++; |
|
61 } |
|
62 else |
|
63 { flag = 1; |
|
64 q = p->right; |
|
65 } |
|
66 } |
|
67 /* create new node and insert it into the tree */ |
|
68 r = dmp_get_atom(tree->pool, sizeof(AVLNODE)); |
|
69 r->key = key; r->type = 0; r->link = NULL; |
|
70 r->rank = 1; r->up = p; |
|
71 r->flag = (short int)(p == NULL ? 0 : flag); |
|
72 r->bal = 0; r->left = NULL; r->right = NULL; |
|
73 tree->size++; |
|
74 if (p == NULL) |
|
75 tree->root = r; |
|
76 else |
|
77 if (flag == 0) p->left = r; else p->right = r; |
|
78 /* go upstairs to the root and correct all subtrees affected by |
|
79 insertion */ |
|
80 while (p != NULL) |
|
81 { if (flag == 0) |
|
82 { /* the height of the left subtree of [p] is increased */ |
|
83 if (p->bal > 0) |
|
84 { p->bal = 0; |
|
85 break; |
|
86 } |
|
87 if (p->bal < 0) |
|
88 { rotate_subtree(tree, p); |
|
89 break; |
|
90 } |
|
91 p->bal = -1; flag = p->flag; p = p->up; |
|
92 } |
|
93 else |
|
94 { /* the height of the right subtree of [p] is increased */ |
|
95 if (p->bal < 0) |
|
96 { p->bal = 0; |
|
97 break; |
|
98 } |
|
99 if (p->bal > 0) |
|
100 { rotate_subtree(tree, p); |
|
101 break; |
|
102 } |
|
103 p->bal = +1; flag = p->flag; p = p->up; |
|
104 } |
|
105 } |
|
106 /* if the root has been reached, the height of the entire tree is |
|
107 increased */ |
|
108 if (p == NULL) tree->height++; |
|
109 return r; |
|
110 } |
|
111 |
|
112 void avl_set_node_type(AVLNODE *node, int type) |
|
113 { /* assign the type field of specified node */ |
|
114 node->type = type; |
|
115 return; |
|
116 } |
|
117 |
|
118 void avl_set_node_link(AVLNODE *node, void *link) |
|
119 { /* assign the link field of specified node */ |
|
120 node->link = link; |
|
121 return; |
|
122 } |
|
123 |
|
124 AVLNODE *avl_find_node(AVL *tree, const void *key) |
|
125 { /* find node in AVL tree */ |
|
126 AVLNODE *p; |
|
127 int c; |
|
128 p = tree->root; |
|
129 while (p != NULL) |
|
130 { c = tree->fcmp(tree->info, key, p->key); |
|
131 if (c == 0) break; |
|
132 p = (c < 0 ? p->left : p->right); |
|
133 } |
|
134 return p; |
|
135 } |
|
136 |
|
137 int avl_get_node_type(AVLNODE *node) |
|
138 { /* retrieve the type field of specified node */ |
|
139 return node->type; |
|
140 } |
|
141 |
|
142 void *avl_get_node_link(AVLNODE *node) |
|
143 { /* retrieve the link field of specified node */ |
|
144 return node->link; |
|
145 } |
|
146 |
|
147 static AVLNODE *find_next_node(AVL *tree, AVLNODE *node) |
|
148 { /* find next node in AVL tree */ |
|
149 AVLNODE *p, *q; |
|
150 if (tree->root == NULL) return NULL; |
|
151 p = node; |
|
152 q = (p == NULL ? tree->root : p->right); |
|
153 if (q == NULL) |
|
154 { /* go upstairs from the left subtree */ |
|
155 for (;;) |
|
156 { q = p->up; |
|
157 if (q == NULL) break; |
|
158 if (p->flag == 0) break; |
|
159 p = q; |
|
160 } |
|
161 } |
|
162 else |
|
163 { /* go downstairs into the right subtree */ |
|
164 for (;;) |
|
165 { p = q->left; |
|
166 if (p == NULL) break; |
|
167 q = p; |
|
168 } |
|
169 } |
|
170 return q; |
|
171 } |
|
172 |
|
173 void avl_delete_node(AVL *tree, AVLNODE *node) |
|
174 { /* delete specified node from AVL tree */ |
|
175 AVLNODE *f, *p, *q, *r, *s, *x, *y; |
|
176 short int flag; |
|
177 p = node; |
|
178 /* if both subtrees of the specified node are non-empty, the node |
|
179 should be interchanged with the next one, at least one subtree |
|
180 of which is always empty */ |
|
181 if (p->left == NULL || p->right == NULL) goto skip; |
|
182 f = p->up; q = p->left; |
|
183 r = find_next_node(tree, p); s = r->right; |
|
184 if (p->right == r) |
|
185 { if (f == NULL) |
|
186 tree->root = r; |
|
187 else |
|
188 if (p->flag == 0) f->left = r; else f->right = r; |
|
189 r->rank = p->rank; r->up = f; |
|
190 r->flag = p->flag; r->bal = p->bal; |
|
191 r->left = q; r->right = p; |
|
192 q->up = r; |
|
193 p->rank = 1; p->up = r; p->flag = 1; |
|
194 p->bal = (short int)(s == NULL ? 0 : +1); |
|
195 p->left = NULL; p->right = s; |
|
196 if (s != NULL) s->up = p; |
|
197 } |
|
198 else |
|
199 { x = p->right; y = r->up; |
|
200 if (f == NULL) |
|
201 tree->root = r; |
|
202 else |
|
203 if (p->flag == 0) f->left = r; else f->right = r; |
|
204 r->rank = p->rank; r->up = f; |
|
205 r->flag = p->flag; r->bal = p->bal; |
|
206 r->left = q; r->right = x; |
|
207 q->up = r; x->up = r; y->left = p; |
|
208 p->rank = 1; p->up = y; p->flag = 0; |
|
209 p->bal = (short int)(s == NULL ? 0 : +1); |
|
210 p->left = NULL; p->right = s; |
|
211 if (s != NULL) s->up = p; |
|
212 } |
|
213 skip: /* now the specified node [p] has at least one empty subtree; |
|
214 go upstairs to the root and adjust the rank field of all nodes |
|
215 affected by deletion */ |
|
216 q = p; f = q->up; |
|
217 while (f != NULL) |
|
218 { if (q->flag == 0) f->rank--; |
|
219 q = f; f = q->up; |
|
220 } |
|
221 /* delete the specified node from the tree */ |
|
222 f = p->up; flag = p->flag; |
|
223 q = p->left != NULL ? p->left : p->right; |
|
224 if (f == NULL) |
|
225 tree->root = q; |
|
226 else |
|
227 if (flag == 0) f->left = q; else f->right = q; |
|
228 if (q != NULL) q->up = f, q->flag = flag; |
|
229 tree->size--; |
|
230 /* go upstairs to the root and correct all subtrees affected by |
|
231 deletion */ |
|
232 while (f != NULL) |
|
233 { if (flag == 0) |
|
234 { /* the height of the left subtree of [f] is decreased */ |
|
235 if (f->bal == 0) |
|
236 { f->bal = +1; |
|
237 break; |
|
238 } |
|
239 if (f->bal < 0) |
|
240 f->bal = 0; |
|
241 else |
|
242 { f = rotate_subtree(tree, f); |
|
243 if (f->bal < 0) break; |
|
244 } |
|
245 flag = f->flag; f = f->up; |
|
246 } |
|
247 else |
|
248 { /* the height of the right subtree of [f] is decreased */ |
|
249 if (f->bal == 0) |
|
250 { f->bal = -1; |
|
251 break; |
|
252 } |
|
253 if (f->bal > 0) |
|
254 f->bal = 0; |
|
255 else |
|
256 { f = rotate_subtree(tree, f); |
|
257 if (f->bal > 0) break; |
|
258 } |
|
259 flag = f->flag; f = f->up; |
|
260 } |
|
261 } |
|
262 /* if the root has been reached, the height of the entire tree is |
|
263 decreased */ |
|
264 if (f == NULL) tree->height--; |
|
265 /* returns the deleted node to the memory pool */ |
|
266 dmp_free_atom(tree->pool, p, sizeof(AVLNODE)); |
|
267 return; |
|
268 } |
|
269 |
|
270 static AVLNODE *rotate_subtree(AVL *tree, AVLNODE *node) |
|
271 { /* restore balance of AVL subtree */ |
|
272 AVLNODE *f, *p, *q, *r, *x, *y; |
|
273 xassert(node != NULL); |
|
274 p = node; |
|
275 if (p->bal < 0) |
|
276 { /* perform negative (left) rotation */ |
|
277 f = p->up; q = p->left; r = q->right; |
|
278 if (q->bal <= 0) |
|
279 { /* perform single negative rotation */ |
|
280 if (f == NULL) |
|
281 tree->root = q; |
|
282 else |
|
283 if (p->flag == 0) f->left = q; else f->right = q; |
|
284 p->rank -= q->rank; |
|
285 q->up = f; q->flag = p->flag; q->bal++; q->right = p; |
|
286 p->up = q; p->flag = 1; |
|
287 p->bal = (short int)(-q->bal); p->left = r; |
|
288 if (r != NULL) r->up = p, r->flag = 0; |
|
289 node = q; |
|
290 } |
|
291 else |
|
292 { /* perform double negative rotation */ |
|
293 x = r->left; y = r->right; |
|
294 if (f == NULL) |
|
295 tree->root = r; |
|
296 else |
|
297 if (p->flag == 0) f->left = r; else f->right = r; |
|
298 p->rank -= (q->rank + r->rank); |
|
299 r->rank += q->rank; |
|
300 p->bal = (short int)(r->bal >= 0 ? 0 : +1); |
|
301 q->bal = (short int)(r->bal <= 0 ? 0 : -1); |
|
302 r->up = f; r->flag = p->flag; r->bal = 0; |
|
303 r->left = q; r->right = p; |
|
304 p->up = r; p->flag = 1; p->left = y; |
|
305 q->up = r; q->flag = 0; q->right = x; |
|
306 if (x != NULL) x->up = q, x->flag = 1; |
|
307 if (y != NULL) y->up = p, y->flag = 0; |
|
308 node = r; |
|
309 } |
|
310 } |
|
311 else |
|
312 { /* perform positive (right) rotation */ |
|
313 f = p->up; q = p->right; r = q->left; |
|
314 if (q->bal >= 0) |
|
315 { /* perform single positive rotation */ |
|
316 if (f == NULL) |
|
317 tree->root = q; |
|
318 else |
|
319 if (p->flag == 0) f->left = q; else f->right = q; |
|
320 q->rank += p->rank; |
|
321 q->up = f; q->flag = p->flag; q->bal--; q->left = p; |
|
322 p->up = q; p->flag = 0; |
|
323 p->bal = (short int)(-q->bal); p->right = r; |
|
324 if (r != NULL) r->up = p, r->flag = 1; |
|
325 node = q; |
|
326 } |
|
327 else |
|
328 { /* perform double positive rotation */ |
|
329 x = r->left; y = r->right; |
|
330 if (f == NULL) |
|
331 tree->root = r; |
|
332 else |
|
333 if (p->flag == 0) f->left = r; else f->right = r; |
|
334 q->rank -= r->rank; |
|
335 r->rank += p->rank; |
|
336 p->bal = (short int)(r->bal <= 0 ? 0 : -1); |
|
337 q->bal = (short int)(r->bal >= 0 ? 0 : +1); |
|
338 r->up = f; r->flag = p->flag; r->bal = 0; |
|
339 r->left = p; r->right = q; |
|
340 p->up = r; p->flag = 0; p->right = x; |
|
341 q->up = r; q->flag = 1; q->left = y; |
|
342 if (x != NULL) x->up = p, x->flag = 1; |
|
343 if (y != NULL) y->up = q, y->flag = 0; |
|
344 node = r; |
|
345 } |
|
346 } |
|
347 return node; |
|
348 } |
|
349 |
|
350 void avl_delete_tree(AVL *tree) |
|
351 { /* delete AVL tree */ |
|
352 dmp_delete_pool(tree->pool); |
|
353 xfree(tree); |
|
354 return; |
|
355 } |
|
356 |
|
357 /* eof */ |