AVL(2)                                                     AVL(2)

     NAME
          avlcreate, avlinsert, avldelete, avllookup, avlnext, avlprev
          - Balanced binary search tree routines

     SYNOPSIS
          #include <u.h>
          #include <libc.h>
          #include <avl.h>

          typedef struct Avl Avl;
          typedef struct Avltree Avltree;

          struct Avl {
                 Avl *c[2];      /* children */
                 Avl *p;         /* parent */
                 schar balance;  /* balance factor */
          };
          struct Avltree {
                 int (*cmp)(Avl*, Avl*);
                 Avl *root;
          };

          Avltree *avlcreate(int(*cmp)(Avl*, Avl*));
          Avl     *avlinsert(Avltree *tree, Avl *new);
          Avl     *avldelete(Avltree *tree, Avl *key);
          Avl     *avllookup(Avltree *tree, Avl *key);
          Avl     *avlnext(Avl *n);
          Avl     *avlprev(Avl *n);

     DESCRIPTION
          These routines allow creation and maintenance of in-memory
          balanced binary search trees.

          An empty tree is created by calling avlcreate with a compar-
          ison function as an argument.  The comparison function must
          take two pointers to Avl structures and return an integer
          less than, equal to, or greater than 0 as the first is
          respectively less than, equal to, or greater than the sec-
          ond.

          Avlinsert adds a new node into the tree and returns an
          existing node with the same key that has been removed from
          the tree and may be freed.  Avllookup returns the node that
          matches the key or nil if no node matches.  Avldelete
          removes the node matching the key from the tree and returns
          it. It returns nil of no matching key is found.

          Avlnext returns the next Avl node in an in-order walk of the
          AVL tree and avlprev returns the previous node.

     AVL(2)                                                     AVL(2)

     EXAMPLES
          Intended usage is to embed the Avl structure anonymously.
          For example, the following will create a key-value store
          with strings as keys and integers as values.

               typedef struct Node {
                      Avl;
                      char *key;
                      int val;
               } Node;

               int
               nodecmp(Avl *la, Avl *lb)
               {
                      Node *a, *b;

                      a = (Node*)la;
                      b = (Node*)lb;
                      return strcmp(a->key, b->key);
               }

               int
               get(Avltree *t, char *key)
               {
                      Node *h, n;

                      n.key = key;
                      h = (Node*)avllookup(t, &n);
                      return h ? h->val : -1;
               }
               ...
                      Avltree *t = avlcreate(nodecmp);

     SOURCE
          /sys/src/libavl

     SEE ALSO
          Donald Knuth, ``The Art of Computer Programming'', Volume 3. Section 6.2.3

     DIAGNOSTICS
          Avlcreate returns nil on error.

     HISTORY
          This implementation was written for 9front (Dec, 2016).