src/avl.h

   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 #ifndef _AVL_H
  17 #define _AVL_H 1
  18
  19 /* Data structures */
  20
  21 /* One element of the AVL tree */
  22 typedef struct avl {
  23         struct avl* left;
  24         struct avl* right;
  25         signed char balance;
  26 } avl;
  27
  28 /* An AVL tree */
  29 typedef struct avl_tree {
  30         avl* root;
  31         int (*compar)(void* a, void* b);
  32 } avl_tree;
  33
  34 /* Public methods */
  35
  36 /* Insert element a into the AVL tree t
  37  * returns 1 if the depth of the tree has grown
  38  * Warning: do not insert elements already present
  39  */
  40 int avl_insert(avl_tree* t, avl* a);
  41
  42 /* Remove an element a from the AVL tree t
  43  * returns -1 if the depth of the tree has shrunk
  44  * Warning: if the element is not present in the tree,
  45  *          returns 0 as if it had been removed succesfully.
  46  */
  47 int avl_remove(avl_tree* t, avl* a);
  48
  49 /* Remove the root of the AVL tree t
  50  * Warning: dumps core if t is empty
  51  */
  52 int avl_removeroot(avl_tree* t);
  53
  54 /* Iterate through elements in t from a range between a and b (inclusive)
  55  * for each element calls iter(a) until it returns 0
  56  * returns the last value returned by iterator or 0 if there were no calls
  57  * Warning: a<=b must hold
  58  */
  59 int avl_range(avl_tree* t, avl* a, avl* b, int (*iter)(avl* a), avl** ret);
  60
  61 /* Iterate through elements in t equal to a
  62  * for each element calls iter(a) until it returns 0
  63  * returns the last value returned by iterator or 0 if there were no calls
  64  */
  65 int avl_search(avl_tree* t, avl* a, int (*iter)(avl* a), avl** ret);
  66
  67 #endif /* avl.h */