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     *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 searches for a given key and returns
  59 the closest node less than the given key,
  60 .BR nil ,
  61 or the closest node greater than the key depending on whether
  62 .I dir
  63 is less than, equal to, or greater than zero, respectively.
  64 .I Avldelete
  65 removes the node matching the key from the tree and returns
  66 it. It returns nil if no matching key is found.
  67 .PP
  68 .I Avlmin
  69 returns the minimum
  70 .B Avl
  71 node in the tree and
  72 .I avlmax
  73 returns the maximum node.
  74 .I Avlnext
  75 returns the next
  76 .B Avl
  77 node in an in-order walk of the AVL tree
  78 and
  79 .I avlprev
  80 returns the previous node.
  81 .SH EXAMPLES
  82 Intended usage is to embed the
  83 .B Avl
  84 structure anonymously.
  85 For example, the following will create a key-value store
  86 with strings as keys and integers as values.
  87 .IP
  88 .EX
  89 typedef struct Node {
  90         Avl;
  91         char *key;
  92         int val;
  93 } Node;
  94
  95 int
  96 nodecmp(Avl *la, Avl *lb)
  97 {
  98         Node *a, *b;
  99
 100         a = (Node*)la;
 101         b = (Node*)lb;
 102         return strcmp(a->key, b->key);
 103 }
 104
 105 int
 106 get(Avltree *t, char *key)
 107 {
 108         Node *h, n;
 109
 110         n.key = key;
 111         h = (Node*)avllookup(t, &n);
 112         return h ? h->val : -1;
 113 }
 114 \fI\&...\fP
 115         Avltree *t = avlcreate(nodecmp);
 116
 117 .EE
 118 .SH SOURCE
 119 .B /sys/src/libavl
 120 .SH SEE ALSO
 121 .nf
 122 Donald Knuth, ``The Art of Computer Programming'', Volume 3. Section 6.2.3
 123 .SH DIAGNOSTICS
 124 .I Avlcreate
 125 returns nil on error.
 126 .SH HISTORY
 127 This implementation was written for 9front (Dec, 2016).