COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/glpavl.c @ 2:4c8956a7bdf4

Last change on this file since 2:4c8956a7bdf4 was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 11.1 KB
Line 
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
27AVL *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
41int 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
47static AVLNODE *rotate_subtree(AVL *tree, AVLNODE *node);
48
49AVLNODE *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
112void avl_set_node_type(AVLNODE *node, int type)
113{     /* assign the type field of specified node */
114      node->type = type;
115      return;
116}
117
118void avl_set_node_link(AVLNODE *node, void *link)
119{     /* assign the link field of specified node */
120      node->link = link;
121      return;
122}
123
124AVLNODE *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
137int avl_get_node_type(AVLNODE *node)
138{     /* retrieve the type field of specified node */
139      return node->type;
140}
141
142void *avl_get_node_link(AVLNODE *node)
143{     /* retrieve the link field of specified node */
144      return node->link;
145}
146
147static 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
173void 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      }
213skip: /* 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
270static 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
350void avl_delete_tree(AVL *tree)
351{     /* delete AVL tree */
352      dmp_delete_pool(tree->pool);
353      xfree(tree);
354      return;
355}
356
357/* eof */
Note: See TracBrowser for help on using the repository browser.