MAN.9FRONT.ORG RTFM


     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, int dir);
          Avl     *avlmin(Avltree *tree);
          Avl     *avlmax(Avltree *tree);
          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 searches for a given
          key and returns the closest node less than the given key,
          equal to, or the closest node greater than the key depending
          on whether dir is less than, equal to, or greater than zero,
          respectively. If dir is zero and there is no matching key,

     AVL(2)                                                     AVL(2)

          it returns nil.  Avldelete removes the node matching the key
          from the tree and returns it. It returns nil if no matching
          key is found.

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

     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.

     AVL(2)                                                     AVL(2)

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