8 avlprev \- Balanced binary search tree routines
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
17 typedef struct Avl Avl;
18 typedef struct Avltree Avltree;
21 Avl *c[2]; /* children */
23 schar balance; /* balance factor */
26 int (*cmp)(Avl*, Avl*);
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);
41 These routines allow creation and maintenance of in-memory balanced
44 An empty tree is created by calling
46 with a comparison function as an argument.
47 The comparison function must take two pointers to
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.
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.
60 searches for a given key and returns
61 the closest node less than the given key,
63 or the closest node greater than the key depending on whether
65 is less than, equal to, or greater than zero, respectively. If
67 is zero and there is no matching key, it returns
70 removes the node matching the key from the tree and returns
71 it. It returns nil if no matching key is found.
78 returns the maximum node.
82 node in an in-order walk of the AVL tree
85 returns the previous node.
87 Intended usage is to embed the
89 structure anonymously.
90 For example, the following will create a key-value store
91 with strings as keys and integers as values.
101 nodecmp(Avl *la, Avl *lb)
107 return strcmp(a->key, b->key);
111 get(Avltree *t, char *key)
116 h = (Node*)avllookup(t, &n);
117 return h ? h->val : -1;
120 Avltree *t = avlcreate(nodecmp);
127 Donald Knuth, ``The Art of Computer Programming'', Volume 3. Section 6.2.3
130 returns nil on error.
132 This implementation was written for 9front (Dec, 2016).