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, int dir);
  34 Avl     *avlmin(Avltree *tree);
  35 Avl     *avlmax(Avltree *tree);
  36 Avl     *avlnext(Avl *n);
  37 Avl     *avlprev(Avl *n);
  38
  39 .EE
  40 .SH DESCRIPTION
  41 These routines allow creation and maintenance of in-memory balanced
  42 binary search trees.
  43 .PP
  44 An empty tree is created by calling
  45 .I avlcreate
  46 with a comparison function as an argument.
  47 The comparison function must take two pointers to
  48 .B Avl
  49 structures and return an integer less than, equal to, or
  50 greater than 0 as the first is
  51 respectively less than,
  52 equal to, or greater than the second.
  53 .PP
  54 .I Avlinsert
  55 adds a new
  56 node into the tree and returns an existing
  57 node with the same key that has been removed
  58 from the tree and may be freed.
  59 .I Avllookup
  60 searches for a given key and returns
  61 the closest node less than the given key,
  62 equal to,
  63 or the closest node greater than the key depending on whether
  64 .I dir
  65 is less than, equal to, or greater than zero, respectively. If
  66 .I dir
  67 is zero and there is no matching key, it returns
  68 .BR nil .
  69 .I Avldelete
  70 removes the node matching the key from the tree and returns
  71 it. It returns nil if no matching key is found.
  72 .PP
  73 .I Avlmin
  74 returns the minimum
  75 .B Avl
  76 node in the tree and
  77 .I avlmax
  78 returns the maximum node.
  79 .I Avlnext
  80 returns the next
  81 .B Avl
  82 node in an in-order walk of the AVL tree
  83 and
  84 .I avlprev
  85 returns the previous node.
  86 .SH EXAMPLES
  87 Intended usage is to embed the
  88 .B Avl
  89 structure anonymously.
  90 For example, the following will create a key-value store
  91 with strings as keys and integers as values.
  92 .IP
  93 .EX
  94 typedef struct Node {
  95         Avl;
  96         char *key;
  97         int val;
  98 } Node;
  99
 100 int
 101 nodecmp(Avl *la, Avl *lb)
 102 {
 103         Node *a, *b;
 104
 105         a = (Node*)la;
 106         b = (Node*)lb;
 107         return strcmp(a->key, b->key);
 108 }
 109
 110 int
 111 get(Avltree *t, char *key)
 112 {
 113         Node *h, n;
 114
 115         n.key = key;
 116         h = (Node*)avllookup(t, &n);
 117         return h ? h->val : -1;
 118 }
 119 \fI\&...\fP
 120         Avltree *t = avlcreate(nodecmp);
 121
 122 .EE
 123 .SH SOURCE
 124 .B /sys/src/libavl
 125 .SH SEE ALSO
 126 .nf
 127 Donald Knuth, ``The Art of Computer Programming'', Volume 3. Section 6.2.3
 128 .SH DIAGNOSTICS
 129 .I Avlcreate
 130 returns nil on error.
 131 .SH HISTORY
 132 This implementation was written for 9front (Dec, 2016).