glenda.party
term% ls -F
term% pwd
$home/manuals/9front/2/avl
term% cat index.txt
AVL(2)                        System Calls Manual                       AVL(2)



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 al‐
       low 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 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.

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
       /sys/src/libavl

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

DIAGNOSTICS
       Functions returning pointers return nil on error.



                                                                        AVL(2)