00001
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036 #ifndef _AVL_H_
00037 #define _AVL_H_
00038
00039 #include "comparable.h"
00040
00041
00042 template <class Key>
00043 class AVL_tree;
00044
00045 template <class Key>
00046 class AVL_node {
00047 Comparable<Key> *element;
00048 AVL_node<Key> *left, *right;
00049 AVL_node<Key> *next, *prev;
00050 unsigned int height;
00051
00052 friend class AVL_tree<Key>;
00053
00054 public:
00055 inline AVL_node() { element = 0; left = right = prev = next = 0; };
00056 inline AVL_node(Comparable<Key> *e) {
00057 element = e;
00058 left = right = prev = next = 0;
00059 };
00060 inline ~AVL_node() {
00061 if (left != 0) delete left;
00062 if (right != 0) delete right;
00063 };
00064
00065 inline Comparable<Key> *elt() { return element; };
00066 inline AVL_node *get_next() { return next; };
00067 inline unsigned int get_height() { return height; };
00068 };
00069
00070
00071 template <class Key>
00072 class AVL_tree {
00073 AVL_node<Key> *root;
00074 unsigned int tree_size;
00075
00076 int _get_height(AVL_node<Key> *node);
00077 AVL_node<Key> *_rotate(AVL_node<Key> *node, int direction);
00078 AVL_node<Key> *_double_rotate(AVL_node<Key> *node, int direction);
00079 AVL_node<Key> *__avl_ins(Comparable<Key> *elt, Key key,
00080 AVL_node<Key> *tree, AVL_node<Key> *parent,
00081 int direction, int *error);
00082 AVL_node<Key> *__avl_del(Comparable<Key> *elt, Key key,
00083 AVL_node<Key> *tree, AVL_node<Key> *parent,
00084 int direction, int *error);
00085 void __avl_print(AVL_node<Key> *tree, int direction, int indent);
00086
00087 public:
00088 inline AVL_tree() { root = 0; };
00089 ~AVL_tree();
00090
00091 unsigned int get_size();
00092 inline unsigned long get_height() { return root->height; };
00093 AVL_node<Key> *find(Comparable<Key> key);
00094 Comparable<Key> *retrieve(Comparable<Key> key);
00095 AVL_node<Key> *find_min();
00096 AVL_node<Key> *find_max();
00097 int insert_elt(Comparable<Key> *elt);
00098 int delete_elt(Comparable<Key> *elt);
00099
00100 void print();
00101 void print_list();
00102
00103
00104 inline void defoliate() { if (root != 0) delete root; };
00105 void burn() {
00106 while (find_min() != 0) {
00107 AVL_node<Key> *list = find_min();
00108 Comparable<Key> *elt = list->elt();
00109 delete_elt(elt);
00110 if (elt != 0)
00111 delete elt;
00112 }
00113 };
00114 };
00115
00116
00117
00118
00119
00120
00121 enum { LEFT = 0, RIGHT = 1 };
00122
00123
00124 static inline int _maximum(int a, int b)
00125 {
00126 return a > b ? a : b;
00127 }
00128
00129 template <class Key>
00130 inline int AVL_tree<Key>::_get_height(AVL_node<Key> *node)
00131 {
00132 if (node == 0)
00133 return 0;
00134 return node->get_height();
00135 }
00136
00137
00138 template <class Key>
00139 AVL_tree<Key>::~AVL_tree()
00140 {
00141 AVL_node<Key> *min;
00142 while ((min = find_min()) != 0) {
00143 Comparable<Key> *me = min->element;
00144 delete_elt(me);
00145 delete me;
00146 }
00147 }
00148
00149
00150 template <class Key>
00151 AVL_node<Key> *AVL_tree<Key>::_rotate(AVL_node<Key> *node, int direction)
00152 {
00153 AVL_node<Key> *child;
00154 if (node == 0)
00155 return 0;
00156
00157 if (direction == LEFT) {
00158 child = node->right;
00159 node->right = child->left;
00160 child->left = node;
00161 } else {
00162 child = node->left;
00163 node->left = child->right;
00164 child->right = node;
00165 }
00166
00167 node->height = 1 + _maximum(_get_height(node->left),
00168 _get_height(node->right));
00169 child->height = 1 + _maximum(_get_height(child->left),
00170 _get_height(child->right));
00171
00172 return child;
00173 }
00174
00175
00176 template <class Key>
00177 AVL_node<Key> *AVL_tree<Key>::_double_rotate(AVL_node<Key> *node,
00178 int direction)
00179 {
00180 AVL_node<Key> *child, *parent;
00181 if (node == 0)
00182 return 0;
00183
00184 if (direction == LEFT) {
00185 child = node->right;
00186 parent = child->left;
00187 child->left = parent->right;
00188 parent->right = child;
00189 node->right = parent->left;
00190 parent->left = node;
00191 } else {
00192 child = node->left;
00193 parent = child->right;
00194 child->right = parent->left;
00195 parent->left = child;
00196 node->left = parent->right;
00197 parent->right = node;
00198 }
00199 parent->height = 1 + _maximum(_get_height(parent->left),
00200 _get_height(parent->right));
00201 node->height = 1 + _maximum(_get_height(node->left),
00202 _get_height(node->right));
00203 child->height = 1 + _maximum(_get_height(child->left),
00204 _get_height(child->right));
00205 return parent;
00206 }
00207
00208
00209
00210
00211 template <class Key>
00212 unsigned int AVL_tree<Key>::get_size()
00213 {
00214 unsigned int i = 0;
00215 AVL_node<Key> *list = find_min();
00216
00217 if (list == 0)
00218 return 0;
00219
00220 for (; list != 0; list = list->next)
00221 i++;
00222
00223 return i;
00224 }
00225
00226
00227 template <class Key>
00228 AVL_node<Key> *AVL_tree<Key>::find(Comparable<Key> key)
00229 {
00230 int i = 0;
00231 AVL_node<Key> *node;
00232
00233 node = root;
00234
00235 while (node != 0) {
00236 if (key == *node->element)
00237 break;
00238 if (key < *node->element)
00239 node = node->left;
00240 else if (key > *node->element)
00241 node = node->right;
00242 i++;
00243 }
00244 return node;
00245 }
00246
00247
00248 template <class Key>
00249 Comparable<Key> *AVL_tree<Key>::retrieve(Comparable<Key> key)
00250 {
00251 AVL_node<Key> *node;
00252 if ((node = find(key)) == 0)
00253 return 0;
00254 return node->element;
00255 }
00256
00257
00258 template <class Key>
00259 AVL_node<Key> *AVL_tree<Key>::find_min()
00260 {
00261 AVL_node<Key> *node;
00262
00263 node = root;
00264 if (node == 0)
00265 return 0;
00266
00267 while (node->left != 0)
00268 node = node->left;
00269
00270 return node;
00271 }
00272
00273
00274 template <class Key>
00275 AVL_node<Key> *AVL_tree<Key>::find_max()
00276 {
00277 AVL_node<Key> *node;
00278
00279 node = root;
00280 if (node == 0)
00281 return 0;
00282
00283 while (node->right != 0)
00284 node = node->right;
00285
00286 return node;
00287 }
00288
00289
00290
00291 template <class Key>
00292 AVL_node<Key> *AVL_tree<Key>::__avl_ins(Comparable<Key> *elt, Key key,
00293 AVL_node<Key> *tree, AVL_node<Key> *parent,
00294 int direction, int *error)
00295 {
00296 if (tree == 0) {
00297 tree = new AVL_node<Key>(elt);
00298 if (tree == 0) {
00299 *error = 1;
00300 return 0;
00301 }
00302
00303 if (direction == LEFT) {
00304 tree->next = parent;
00305 tree->prev = parent->prev;
00306 if (parent->prev != 0)
00307 parent->prev->next = tree;
00308 parent->prev = tree;
00309 } else if (direction == RIGHT) {
00310 tree->next = parent->next;
00311 tree->prev = parent;
00312 if (parent->next != 0)
00313 parent->next->prev = tree;
00314 parent->next = tree;
00315 } else {
00316 tree->next = tree->prev = 0;
00317 }
00318 } else if (key < tree->element->key) {
00319 tree->left = __avl_ins(elt, key, tree->left, tree,
00320 LEFT, error);
00321
00322 if (_get_height(tree->left) - _get_height(tree->right) >= 2) {
00323 if (_get_height(tree->left->left) -
00324 _get_height(tree->left->right) >= 1)
00325 tree = _rotate(tree, RIGHT);
00326 else if (_get_height(tree->left->right) -
00327 _get_height(tree->left->left) >= 1)
00328 tree = _double_rotate(tree, RIGHT);
00329 }
00330 } else if (key > tree->element->key) {
00331 tree->right = __avl_ins(elt, key, tree->right, tree,
00332 RIGHT, error);
00333 if (_get_height(tree->right) - _get_height(tree->left) >= 2) {
00334 if (_get_height(tree->right->right) -
00335 _get_height(tree->right->left) >= 1)
00336 tree = _rotate(tree, LEFT);
00337 else if (_get_height(tree->right->left) -
00338 _get_height(tree->right->right) >= 1)
00339 tree = _double_rotate(tree, LEFT);
00340 }
00341 } else if (key == tree->element->key) {
00342 *error = 1;
00343 }
00344
00345 tree->height = 1 + _maximum(_get_height(tree->left),
00346 _get_height(tree->right));
00347 return tree;
00348 }
00349
00350
00351 template <class Key>
00352 int AVL_tree<Key>::insert_elt(Comparable<Key> *elt)
00353 {
00354 int error = 0;
00355 if (elt == 0)
00356 return -1;
00357
00358 root = __avl_ins(elt, elt->key, root, 0, -1, &error);
00359 return error;
00360 }
00361
00363 template <class Key>
00364 AVL_node<Key> *AVL_tree<Key>::__avl_del(Comparable<Key> *elt, Key key,
00365 AVL_node<Key> *tree, AVL_node<Key> *parent,
00366 int direction, int *error)
00367 {
00368 if (tree == 0) {
00369 *error = 1;
00370 return 0;
00371 } else if (key == tree->element->key) {
00372 AVL_node<Key> *shifted;
00373 if (direction == LEFT && parent != 0) {
00374 if (tree->left == 0)
00375 parent->left = tree->right;
00376 else if (tree->right == 0)
00377 parent->left = tree->right;
00378 } else if (direction == RIGHT && parent !=0) {
00379 if (tree->left == 0)
00380 parent->right = tree->right;
00381 else if (tree->right == 0)
00382 parent->right = tree->right;
00383 }
00384
00385 if (tree->left == 0)
00386 shifted = tree->right;
00387 else if (tree->right == 0)
00388 shifted = tree->left;
00389 else {
00390 if (tree->prev != 0) {
00391 tree->element = tree->prev->element;
00392 key = tree->element->key;
00393 } else {
00394 tree->element = tree->next->element;
00395 key = tree->element->key;
00396 }
00397 return __avl_del(elt, key, tree, parent,
00398 direction, error);
00399 }
00400
00401 if (tree->next != 0)
00402 tree->next->prev = tree->prev;
00403 if (tree->prev != 0)
00404 tree->prev->next = tree->next;
00405 tree->left = tree->right = 0;
00406 delete tree;
00407
00408 if (shifted != 0)
00409 shifted->height--;
00410 return shifted;
00411 } else if (key < tree->element->key) {
00412 tree->left = __avl_del(elt, key, tree->left, tree,
00413 LEFT, error);
00414
00415 if (_get_height(tree->left) - _get_height(tree->right) >= 2) {
00416 if (_get_height(tree->left->left) -
00417 _get_height(tree->left->right) >= 1)
00418 tree = _rotate(tree, RIGHT);
00419 else if (_get_height(tree->left->right) -
00420 _get_height(tree->left->left) >= 1)
00421 tree = _double_rotate(tree, RIGHT);
00422 }
00423 } else if (key > tree->element->key) {
00424 tree->right = __avl_del(elt, key, tree->right, tree,
00425 RIGHT, error);
00426
00427 if (_get_height(tree->right) - _get_height(tree->left) >= 2) {
00428 if (_get_height(tree->right->right) -
00429 _get_height(tree->right->left) >= 1)
00430 tree = _rotate(tree, LEFT);
00431 else if (_get_height(tree->right->left) -
00432 _get_height(tree->right->right) >= 1)
00433 tree = _double_rotate(tree, LEFT);
00434 }
00435 }
00436
00437 tree->height = 1 + _maximum(_get_height(tree->left),
00438 _get_height(tree->right));
00439 return tree;
00440 }
00441
00442
00443 template <class Key>
00444 int AVL_tree<Key>::delete_elt(Comparable<Key> *elt)
00445 {
00446 int error = 0;
00447
00448 root = __avl_del(elt, elt->key, root, 0, -1, &error);
00449 return error;
00450 }
00451
00452
00453
00454
00455 #include <stdio.h>
00456
00457 template <class Key>
00458 void AVL_tree<Key>::__avl_print(AVL_node<Key> *tree,
00459 int direction, int indent)
00460 {
00461 int i;
00462 char format[MAX_FORMAT_STRING];
00463
00464 if (tree != 0) {
00465 __avl_print(tree->right, RIGHT, indent + 1);
00466
00467 for (i = 0; i < indent - 1; i++)
00468 fprintf(stderr, " ");
00469 if (indent) {
00470 if (direction == LEFT)
00471 fprintf(stderr, " \\-- ");
00472 else
00473 fprintf(stderr, " /-- ");
00474 }
00475 sprintf(format, "%s\n", tree->element->key_format_string);
00476 fprintf(stderr, format, tree->element->key);
00477
00478 __avl_print(tree->left, LEFT, indent + 1);
00479 }
00480 }
00481
00482
00483 template <class Key>
00484 void AVL_tree<Key>::print()
00485 {
00486 fprintf(stderr, "AVL tree: \n");
00487 __avl_print(root, -1, 0);
00488 }
00489
00490
00491 template <class Key>
00492 void AVL_tree<Key>::print_list()
00493 {
00494 int i;
00495 char format[MAX_FORMAT_STRING];
00496 AVL_node<Key> *list = find_min();
00497
00498 fprintf(stderr, "Linked list: ");
00499 if (list == 0)
00500 goto end;
00501
00502 sprintf(format, "%s ", list->element->key_format_string);
00503 fprintf(stderr, format, list->element->key_value());
00504 for (i = 1, list = list->next; list != 0; list = list->next, i++) {
00505 sprintf(format, "-> %s ", list->element->key_format_string);
00506 fprintf(stderr, format, list->element->key);
00507 }
00508 end:
00509 fprintf(stderr, "\n\n");
00510 }
00511
00512
00513 #endif // _AVL_H_