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 
avl_create_tree(int (* fcmp)(void * info,const void * key1,const void * key2),void * info)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 
avl_strcmp(void * info,const void * key1,const void * key2)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 
avl_insert_node(AVL * tree,const void * key)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 
avl_set_node_type(AVLNODE * node,int type)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 
avl_set_node_link(AVLNODE * node,void * link)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 
avl_find_node(AVL * tree,const void * key)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 
avl_get_node_type(AVLNODE * node)137 int avl_get_node_type(AVLNODE *node)
138 {     /* retrieve the type field of specified node */
139       return node->type;
140 }
141 
avl_get_node_link(AVLNODE * node)142 void *avl_get_node_link(AVLNODE *node)
143 {     /* retrieve the link field of specified node */
144       return node->link;
145 }
146 
find_next_node(AVL * tree,AVLNODE * node)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 
avl_delete_node(AVL * tree,AVLNODE * node)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 
rotate_subtree(AVL * tree,AVLNODE * node)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 
avl_delete_tree(AVL * tree)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 */
358