term% ls -F
term% cat index.txt
AVL(2)                        System Calls Manual                       AVL(2)

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

       #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*));

       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

       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 negative, 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.

       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.

       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 {
                     uchar  score[VtScoreSize];
                     int    type;
              } Node;
              Avltree *tree;
              Avl *res;
              Node *np;
                     res = lookupavl(tree, np);


       G. M. Adelson-Velsky, E. M. Landis, ``An algorithm for the organization
       of information'', Soviet Mathematics, Vol. 3, pp. 1256รข1263.

       Functions returning pointers return nil on error.