term% cat index.txt AVL(2) System Calls Manual AVL(2)
NAME
mkavltree, insertavl, lookupavl, deleteavl, avlwalk, avlnext, avlprev,
endwalk - AVL tree routines
SYNOPSIS
#include <u.h>
#include <libc.h>
#include <avl.h>
typedef struct Avl Avl;
struct Avl
{
Avl *p; /* parent */
Avl *n[2]; /* children */
int bal; /* balance bits */
};
Avl *avlnext(Avlwalk *walk);
Avl *avlprev(Avlwalk *walk);
Avlwalk *avlwalk(Avltree *tree);
void deleteavl(Avltree *tree, Avl *key, Avl **oldp);
void endwalk(Avlwalk *walk);
void insertavl(Avltree *tree, Avl *new, Avl **oldp);
Avl *lookupavl(Avltree *tree, Avl *key);
Avl *searchavl(Avltree *tree, Avl *key, int neighbor);
Avltree *mkavltree(int(*cmp)(Avl*, Avl*));
DESCRIPTION
An AVL tree is a self-balancing binary search tree. These routines al‐
low creation and maintenance of in-memory AVL trees.
An empty AVL tree is created by calling mkavltree with a comparison
function as argument. This function should take two pointers to Avl
objects and return -1, 0 or 1 as the first is respectively less than,
equal to, or greater than, the second. Insertavl adds a new tree node
into tree. If oldp is non-nil upon return, it points to storage for an
old node with the same key that may now be freed. Lookupavl returns
the tree node that matches key by tree's comparison function, or nil if
none.
Searchavl returns the tree node that matches key by tree's comparison
function, if it exists. If it does not, and neighbor is positive, it
returns the nearest node whose key is greater or nil if there is none
and, if neighbor is negative, it returns the nearest node whose key is
less or nil if there is none. It is an error to set neighbor to values
other than -1, 0, or +1.
Deleteavl removes the node matching key from tree; oldp is handled as
per insertavl.
Avlwalk returns a pointer to a newly-allocated Avlwalk object. Endwalk
frees such an object. Avlnext and avlprev walk the tree associated
with walk, returning the next (respectively, previous) tree node in the
comparison order defined by the comparison function associated with the
tree associated with walk.
EXAMPLES
Intended usage seems to be to make an anonymous Avl the first member of
the application's tree-node structure, then pass these routines tree-
node pointers instead of Avl*s.
typedef struct Node {
Avl;
uchar score[VtScoreSize];
int type;
} Node;
Avltree *tree;
Avl *res;
Node *np;
...
res = lookupavl(tree, np);
SOURCE
/sys/src/libavl
SEE ALSO
G. M. Adelson-Velsky, E. M. Landis, ‘‘An algorithm for the organization
of information'', Soviet Mathematics, Vol. 3, pp. 1256â1263.
DIAGNOSTICS
Functions returning pointers return nil on error.
AVL(2)