lemon-project-template-glpk
view deps/glpk/src/glpavl.c @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
line source
1 /* glpavl.c (binary search tree) */
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, 2011 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 ***********************************************************************/
25 #include "glpavl.h"
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 }
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 }
47 static AVLNODE *rotate_subtree(AVL *tree, AVLNODE *node);
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 }
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 }
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 }
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 }
137 int avl_get_node_type(AVLNODE *node)
138 { /* retrieve the type field of specified node */
139 return node->type;
140 }
142 void *avl_get_node_link(AVLNODE *node)
143 { /* retrieve the link field of specified node */
144 return node->link;
145 }
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 }
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 }
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 }
350 void avl_delete_tree(AVL *tree)
351 { /* delete AVL tree */
352 dmp_delete_pool(tree->pool);
353 xfree(tree);
354 return;
355 }
357 /* eof */