man(1) Manual page archive


     AVL(3)                                                     AVL(3)

     NAME
          mkavltree, insertavl, lookupavl, deleteavl, avlwalk,
          avlnext, avlprev, endwalk - AVL tree routines

     SYNOPSIS
          #include <u.h>
          #include <libc.h>
          #include <avl.h>
          typedef struct Avl Avl;
          struct Avl
          {
                 Avl    *p;           /* parent */
                 Avl    *n[2];        /* children */
                 int    bal;          /* balance bits */
          };
          Avl    *avlnext(Avlwalk *walk);
          Avl    *avlprev(Avlwalk *walk);
          Avlwalk       *avlwalk(Avltree *tree);
          void   deleteavl(Avltree *tree, Avl *key, Avl **oldp);
          void   endwalk(Avlwalk *walk);
          void   insertavl(Avltree *tree, Avl *new, Avl **oldp);
          Avl    *lookupavl(Avltree *tree, Avl *key);
          Avl    *searchavl(Avltree *tree, Avl *key, int neighbor);
          Avltree       *mkavltree(int(*cmp)(Avl*, Avl*));

     DESCRIPTION
          An AVL tree is a self-balancing binary search tree.  These
          routines allow creation and maintenance of in-memory AVL
          trees.

          An empty AVL tree is created by calling mkavltree with a
          comparison function as argument.  This function should take
          two pointers to Avl objects and return -1, 0 or 1 as the
          first is respectively less than, equal to, or greater than,
          the second.  Insertavl adds a new tree node into tree. If
          oldp is non-nil upon return, it points to storage for an old
          node with the same key that may now be freed.  Lookupavl
          returns the tree node that matches key by tree's comparison
          function, or nil if none.

          Searchavl returns the tree node that matches key by tree's
          comparison function, if it exists.  If it does not, and
          neighbor is positive, it returns the nearest node whose key
          is greater or nil if there is none and, if neighbor is nega-
          tive, it returns the nearest node whose key is less or nil
          if there is none.  It is an error to set neighbor to values
          other than -1, 0, or +1.

          Deleteavl removes the node matching key from tree; oldp is
          handled as per insertavl.

     AVL(3)                                                     AVL(3)

          Avlwalk returns a pointer to a newly-allocated Avlwalk
          object.  Endwalk frees such an object.  Avlnext and avlprev
          walk the tree associated with walk, returning the next
          (respectively, previous) tree node in the comparison order
          defined by the comparison function associated with the tree
          associated with walk.

     EXAMPLES
          Intended usage seems to be to make an anonymous Avl the
          first member of the application's tree-node structure, then
          pass these routines tree-node pointers instead of Avl*s.

               typedef struct Node {
                      Avl;
                      uchar  score[VtScoreSize];
                      int    type;
               } Node;
               Avltree *tree;
               Avl *res;
               Node *np;
               ...
                      res = lookupavl(tree, np);

     SOURCE
          /src/libavl

     SEE ALSO
          G. M. Adelson-Velsky, E. M. Landis, ``An algorithm for the
          organization of information'', Soviet Mathematics, Vol. 3,
          pp. 12561263.

     DIAGNOSTICS
          Functions returning pointers return nil on error.