ref: bc8c31dbd506731813a62b220ae544f2eb239c5f
dir: /sys/man/2/avl/
.TH AVL 2 .SH NAME avlcreate, avlinsert, avldelete, avllookup, avlnext, avlprev \- Balanced binary search tree routines .SH SYNOPSIS .ta 0.75i 1.5i 2.25i 3i 3.75i 4.5i .\" .ta 0.7i +0.7i +0.7i +0.7i +0.7i +0.7i +0.7i .EX #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); .EE .SH DESCRIPTION These routines allow creation and maintenance of in-memory balanced binary search trees. .PP An empty tree is created by calling .I avlcreate with a comparison function as an argument. The comparison function must take two pointers to .B 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 second. .PP .I 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. .I 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 .I dir is less than, equal to, or greater than zero, respectively. If .I dir is zero and there is no matching key, it returns .BR nil . .I Avldelete removes the node matching the key from the tree and returns it. It returns nil if no matching key is found. .PP .I Avlmin returns the minimum .B Avl node in the tree and .I avlmax returns the maximum node. .I Avlnext returns the next .B Avl node in an in-order walk of the AVL tree and .I avlprev returns the previous node. .SH EXAMPLES Intended usage is to embed the .B Avl structure anonymously. For example, the following will create a key-value store with strings as keys and integers as values. .IP .EX 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; } \fI\&...\fP Avltree *t = avlcreate(nodecmp); .EE .SH SOURCE .B /sys/src/libavl .SH SEE ALSO .nf Donald Knuth, ``The Art of Computer Programming'', Volume 3. Section 6.2.3 .SH DIAGNOSTICS .I Avlcreate returns nil on error. .SH HISTORY This implementation was written for 9front (Dec, 2016).