|
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);
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. 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
| |
/usr/local/plan9/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.
|
|
|