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).
