src/avl.c

   1 /*
   2  * ANSI C Library for maintainance of AVL Balanced Trees
   3  *
   4  * ref.:
   5  *  G. M. Adelson-Velskij & E. M. Landis
   6  *  Doklady Akad. Nauk SSSR 146 (1962), 263-266
   7  *
   8  * see also:
   9  *  D. E. Knuth: The Art of Computer Programming Vol.3 (Sorting and Searching)
  10  *
  11  * (C) 2000 Daniel Nagy, Budapest University of Technology and Economics
  12  * Released under GNU General Public License (GPL) version 2
  13  *
  14  */
  15
  16 #ifdef HAVE_CONFIG_H
  17 #include <config.h>
  18 #endif
  19 #include "avl.h"
  20
  21 /* Private methods */
  22
  23 /* Swing to the left
  24  * Warning: no balance maintainance
  25  */
  26 void avl_swl(avl** root) {
  27         avl* a = *root;
  28         avl* b = a->right;
  29         *root = b;
  30         a->right = b->left;
  31         b->left = a;
  32 }
  33
  34 /* Swing to the right
  35  * Warning: no balance maintainance
  36  */
  37 void avl_swr(avl** root) {
  38         avl* a = *root;
  39         avl* b = a->left;
  40         *root = b;
  41         a->left = b->right;
  42         b->right = a;
  43 }
  44
  45 /* Balance maintainance after especially nasty swings
  46  */
  47 void avl_nasty(avl* root) {
  48         switch (root->balance) {
  49         case -1:
  50                 root->left->balance = 0;
  51                 root->right->balance = 1;
  52                 break;
  53         case 1:
  54                 root->left->balance = -1;
  55                 root->right->balance = 0;
  56                 break;
  57         case 0:
  58                 root->left->balance = 0;
  59                 root->right->balance = 0;
  60         }
  61         root->balance = 0;
  62 }
  63
  64 /* Public methods */
  65
  66 /* Insert element a into the AVL tree t
  67  * returns 1 if the depth of the tree has grown
  68  * Warning: do not insert elements already present
  69  */
  70 int avl_insert(avl_tree* t, avl* a) {
  71         /* initialize */
  72         a->left = 0;
  73         a->right = 0;
  74         a->balance = 0;
  75         /* insert into an empty tree */
  76         if (!t->root) {
  77                 t->root = a;
  78                 return 1;
  79         }
  80
  81         if (t->compar(t->root, a) > 0) {
  82                 /* insert into the left subtree */
  83                 if (t->root->left) {
  84                         avl_tree left_subtree;
  85                         left_subtree.root = t->root->left;
  86                         left_subtree.compar = t->compar;
  87                         if (avl_insert(&left_subtree, a)) {
  88                                 switch (t->root->balance--) {
  89                                 case 1:
  90                                         return 0;
  91                                 case 0:
  92                                         return 1;
  93                                 }
  94                                 if (t->root->left->balance < 0) {
  95                                         avl_swr(&(t->root));
  96                                         t->root->balance = 0;
  97                                         t->root->right->balance = 0;
  98                                 } else {
  99                                         avl_swl(&(t->root->left));
 100                                         avl_swr(&(t->root));
 101                                         avl_nasty(t->root);
 102                                 }
 103                         } else
 104                                 t->root->left = left_subtree.root;
 105                         return 0;
 106                 } else {
 107                         t->root->left = a;
 108                         if (t->root->balance--)
 109                                 return 0;
 110                         return 1;
 111                 }
 112         } else {
 113                 /* insert into the right subtree */
 114                 if (t->root->right) {
 115                         avl_tree right_subtree;
 116                         right_subtree.root = t->root->right;
 117                         right_subtree.compar = t->compar;
 118                         if (avl_insert(&right_subtree, a)) {
 119                                 switch (t->root->balance++) {
 120                                 case -1:
 121                                         return 0;
 122                                 case 0:
 123                                         return 1;
 124                                 }
 125                                 if (t->root->right->balance > 0) {
 126                                         avl_swl(&(t->root));
 127                                         t->root->balance = 0;
 128                                         t->root->left->balance = 0;
 129                                 } else {
 130                                         avl_swr(&(t->root->right));
 131                                         avl_swl(&(t->root));
 132                                         avl_nasty(t->root);
 133                                 }
 134                         } else
 135                                 t->root->right = right_subtree.root;
 136                         return 0;
 137                 } else {
 138                         t->root->right = a;
 139                         if (t->root->balance++)
 140                                 return 0;
 141                         return 1;
 142                 }
 143         }
 144 }
 145
 146 /* Remove an element a from the AVL tree t
 147  * returns -1 if the depth of the tree has shrunk
 148  * Warning: if the element is not present in the tree,
 149  *          returns 0 as if it had been removed succesfully.
 150  */
 151 int avl_remove(avl_tree* t, avl* a) {
 152         int b;
 153         if (t->root == a)
 154                 return avl_removeroot(t);
 155         b = t->compar(t->root, a);
 156         if (b >= 0) {
 157                 /* remove from the left subtree */
 158                 int ch;
 159                 avl_tree left_subtree;
 160                 if ((left_subtree.root = t->root->left)) {
 161                         left_subtree.compar = t->compar;
 162                         ch = avl_remove(&left_subtree, a);
 163                         t->root->left = left_subtree.root;
 164                         if (ch) {
 165                                 switch (t->root->balance++) {
 166                                 case -1:
 167                                         return -1;
 168                                 case 0:
 169                                         return 0;
 170                                 }
 171                                 switch (t->root->right->balance) {
 172                                 case 0:
 173                                         avl_swl(&(t->root));
 174                                         t->root->balance = -1;
 175                                         t->root->left->balance = 1;
 176                                         return 0;
 177                                 case 1:
 178                                         avl_swl(&(t->root));
 179                                         t->root->balance = 0;
 180                                         t->root->left->balance = 0;
 181                                         return -1;
 182                                 }
 183                                 avl_swr(&(t->root->right));
 184                                 avl_swl(&(t->root));
 185                                 avl_nasty(t->root);
 186                                 return -1;
 187                         }
 188                 }
 189         }
 190         if (b <= 0) {
 191                 /* remove from the right subtree */
 192                 int ch;
 193                 avl_tree right_subtree;
 194                 if ((right_subtree.root = t->root->right)) {
 195                         right_subtree.compar = t->compar;
 196                         ch = avl_remove(&right_subtree, a);
 197                         t->root->right = right_subtree.root;
 198                         if (ch) {
 199                                 switch (t->root->balance--) {
 200                                 case 1:
 201                                         return -1;
 202                                 case 0:
 203                                         return 0;
 204                                 }
 205                                 switch (t->root->left->balance) {
 206                                 case 0:
 207                                         avl_swr(&(t->root));
 208                                         t->root->balance = 1;
 209                                         t->root->right->balance = -1;
 210                                         return 0;
 211                                 case -1:
 212                                         avl_swr(&(t->root));
 213                                         t->root->balance = 0;
 214                                         t->root->right->balance = 0;
 215                                         return -1;
 216                                 }
 217                                 avl_swl(&(t->root->left));
 218                                 avl_swr(&(t->root));
 219                                 avl_nasty(t->root);
 220                                 return -1;
 221                         }
 222                 }
 223         }
 224         return 0;
 225 }
 226
 227 /* Remove the root of the AVL tree t
 228  * Warning: dumps core if t is empty
 229  */
 230 int avl_removeroot(avl_tree* t) {
 231         int ch;
 232         avl* a;
 233         if (!t->root->left) {
 234                 if (!t->root->right) {
 235                         t->root = 0;
 236                         return -1;
 237                 }
 238                 t->root = t->root->right;
 239                 return -1;
 240         }
 241         if (!t->root->right) {
 242                 t->root = t->root->left;
 243                 return -1;
 244         }
 245         if (t->root->balance < 0) {
 246                 /* remove from the left subtree */
 247                 a = t->root->left;
 248                 while (a->right)
 249                         a = a->right;
 250         } else {
 251                 /* remove from the right subtree */
 252                 a = t->root->right;
 253                 while (a->left)
 254                         a = a->left;
 255         }
 256         ch = avl_remove(t, a);
 257         a->left = t->root->left;
 258         a->right = t->root->right;
 259         a->balance = t->root->balance;
 260         t->root = a;
 261         if (a->balance == 0)
 262                 return ch;
 263         return 0;
 264 }
 265
 266 /* Iterate through elements in t from a range between a and b (inclusive)
 267  * for each element calls iter(a) until it returns 0
 268  * returns the last value returned by iterator or 0 if there were no calls
 269  * Warning: a<=b must hold
 270  */
 271 int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl* a), avl** ret) {
 272         int x, c = 0;
 273         if (!t->root)
 274                 return 0;
 275         x = t->compar(t->root, a);
 276         if (a != b) {
 277                 if (x < 0) {
 278                         x = t->compar(t->root, b);
 279                         if (x > 0)
 280                                 x = 0;
 281                 }
 282         }
 283         if (x >= 0) {
 284                 /* search in the left subtree */
 285                 avl_tree left_subtree;
 286                 if ((left_subtree.root = t->root->left)) {
 287                         left_subtree.compar = t->compar;
 288                         if (!(c = avl_range(&left_subtree, a, b, iter, ret)))
 289                                 if (x > 0)
 290                                         return 0;
 291                 }
 292         }
 293         if (x == 0) {
 294                 if (!(c = iter(t->root))) {
 295                         if (ret)
 296                                 *ret = t->root;
 297                         return 0;
 298                 }
 299         }
 300         if (x <= 0) {
 301                 /* search in the right subtree */
 302                 avl_tree right_subtree;
 303                 if ((right_subtree.root = t->root->right)) {
 304                         right_subtree.compar = t->compar;
 305                         if (!(c = avl_range(&right_subtree, a, b, iter, ret)))
 306                                 if (x < 0)
 307                                         return 0;
 308                 }
 309         }
 310         return c;
 311 }
 312
 313 /* Iterate through elements in t equal to a
 314  * for each element calls iter(a) until it returns 0
 315  * returns the last value returned by iterator or 0 if there were no calls
 316  */
 317 int avl_search(avl_tree* t, avl* a, int (*iter)(avl* a), avl** ret) {
 318         return avl_range(t, a, a, iter, ret);
 319 }