AVL(2) 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 allow 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 nega-
tive, 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
Page 1 Plan 9 (printed 12/22/24)
AVL(2) AVL(2)
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.
Page 2 Plan 9 (printed 12/22/24)