sys/man/2/avl

   1 .TH AVL 2
   2 .SH NAME
   3 avlcreate,
   4 avlinsert,
   5 avldelete,
   6 avllookup,
   7 avlnext,
   8 avlprev \- Balanced binary search tree routines
   9 .SH SYNOPSIS
  10 .ta 0.75i 1.5i 2.25i 3i 3.75i 4.5i
  11 .\" .ta 0.7i +0.7i +0.7i +0.7i +0.7i +0.7i +0.7i
  12 .EX
  13 #include <u.h>
  14 #include <libc.h>
  15 #include <avl.h>
  16
  17 typedef struct Avl Avl;
  18 typedef struct Avltree Avltree;
  19
  20 struct Avl {
  21         Avl *c[2];      /* children */
  22         Avl *p;         /* parent */
  23         schar balance;  /* balance factor */
  24 };
  25 struct Avltree {
  26         int (*cmp)(Avl*, Avl*);
  27         Avl *root;
  28 };
  29
  30 Avltree *avlcreate(int(*cmp)(Avl*, Avl*));
  31 Avl     *avlinsert(Avltree *tree, Avl *new);
  32 Avl     *avldelete(Avltree *tree, Avl *key);
  33 Avl     *avllookup(Avltree *tree, Avl *key);
  34 Avl     *avlnext(Avl *n);
  35 Avl     *avlprev(Avl *n);
  36
  37 .EE
  38 .SH DESCRIPTION
  39 These routines allow creation and maintenance of in-memory balanced
  40 binary search trees.
  41 .PP
  42 An empty tree is created by calling
  43 .I avlcreate
  44 with a comparison function as an argument.
  45 The comparison function must take two pointers to
  46 .B Avl
  47 structures and return an integer less than, equal to, or
  48 greater than 0 as the first is
  49 respectively less than,
  50 equal to, or greater than the second.
  51 .PP
  52 .I Avlinsert
  53 adds a new
  54 node into the tree and returns an existing
  55 node with the same key that has been removed
  56 from the tree and may be freed.
  57 .I Avllookup
  58 returns the
  59 node that matches the key or
  60 .B nil
  61 if no node matches.
  62 .I Avldelete
  63 removes the node matching the key from the tree and returns
  64 it. It returns nil of no matching key is found.
  65 .PP
  66 .I Avlnext
  67 returns the next
  68 .B Avl
  69 node in an in-order walk of the AVL tree
  70 and
  71 .I avlprev
  72 returns the previous node.
  73 .SH EXAMPLES
  74 Intended usage is to embed the
  75 .B Avl
  76 structure anonymously.
  77 For example, the following will create a key-value store
  78 with strings as keys and integers as values.
  79 .IP
  80 .EX
  81 typedef struct Node {
  82         Avl;
  83         char *key;
  84         int val;
  85 } Node;
  86
  87 int
  88 nodecmp(Avl *la, Avl *lb)
  89 {
  90         Node *a, *b;
  91
  92         a = (Node*)la;
  93         b = (Node*)lb;
  94         return strcmp(a->key, b->key);
  95 }
  96
  97 int
  98 get(Avltree *t, char *key)
  99 {
 100         Node *h, n;
 101
 102         n.key = key;
 103         h = (Node*)avllookup(t, &n);
 104         return h ? h->val : -1;
 105 }
 106 \fI\&...\fP
 107         Avltree *t = avlcreate(nodecmp);
 108
 109 .EE
 110 .SH SOURCE
 111 .B /sys/src/libavl
 112 .SH SEE ALSO
 113 .nf
 114 Donald Knuth, ``The Art of Computer Programming'', Volume 3. Section 6.2.3
 115 .SH DIAGNOSTICS
 116 .I Avlcreate
 117 returns nil on error.
 118 .SH HISTORY
 119 This implementation was written for 9front (Dec, 2016).