4.5.2 AVL-Tree

The VRRLIB implements the AVL-Tree data structure for effective manipulation with ordered sets. In each node of this binary tree, the height of the left and the right subtrees differ at most by one. It can be easily prooved that the height of such a tree is O(log n).

The following example describes a basic usage:

     /* normal header file */
     #include "lib/avltree.h"
     
     /* node structure (1) */
     struct mynode {
       struct avlnode avlnode;
       int key;
     };
     
     /* code generator */
     #define AVLTREE_TYPE int
     #define AVLTREE_KEY(x) ((mynode *)x)->key
     #include "lib/avltreegen.h"
     
     int main(void)
     {
       struct avltree tree;
       struct mynode node;
     
       /* structure initialization */
       avltree_init(&tree);
     
       /* insertion example (2) */
       node.key = 100;
       avltree_insert(&tree, &node.avlnode);
     
       /* ... */
     }

Two header files have to be included. The first (lib/avltree.h) is a classical header file with independent structure definitions and function headers. The second one (lib/avltreegen.h) is somewhat special. Is reads macros as parameters to generate a specialized code of some functions. The full description of supported macros can be found in the first header file.

Each inserted item must contain the avlnode as a substructure (1) and is accessed through its address (2) in AVL-Tree routines. For each tree, there must be also one instance of the avltree structure with a pointer to the root.

The implementation includes many standard functions for ordered sets like data insertion, deletion or key searching with usually logarithmic time complexity. If no key is given in the macro parameters, no searching routines are generated.