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