132 lines
2.7 KiB
Text
132 lines
2.7 KiB
Text
.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).
|