Subversion Repositories planix.SVN

.TH AVL 2

.SH NAME

mkavltree, insertavl, lookupavl, deleteavl, avlwalk, avlnext, avlprev, endwalk - AVL 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>

.sp 0.3v

typedef struct Avl Avl;

struct Avl

{

	Avl	*p;		/* parent */

	Avl	*n[2];		/* children */

	int	bal;		/* balance bits */

};

.sp 0.3v

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*));

.EE

.SH DESCRIPTION

An AVL tree is a self-balancing binary search tree.

These routines allow creation and maintenance of in-memory AVL trees.

.PP

An empty AVL tree is created by calling

.I mkavltree

with a comparison function as argument.

This function should take two pointers to

.B Avl

objects and return -1, 0 or 1 as the first is

respectively less than,

equal to, or greater than,

the second.

.I Insertavl

adds a

.I new

tree node into

.IR tree .

If

.I oldp

is non-nil upon return,

it points to storage for an old node

with the same key that may now be freed.

.I Lookupavl

returns the

.I tree

node that matches

.I key

by

.IR tree 's

comparison function,

or

.B nil

if none.

.PP

.I Searchavl

returns the

.I tree

node that matches

.I key

by

.IR tree 's

comparison function, if it exists.

If it does not, and

.I neighbor

is positive, it returns the nearest node whose

.I key

is greater or

.B nil

if there is none and, if

.I neighbor

is negative, it returns the nearest node whose

.I key

is less or

.B nil

if there is none.

It is an error to set

.I neighbor

to values other than \-1, 0, or +1.

.PP

.I Deleteavl

removes the node matching

.I key

from

.IR tree ;

.I oldp

is handled as per

.IR insertavl .

.PP

.I Avlwalk

returns a pointer to a newly-allocated

.B Avlwalk

object.

.I Endwalk

frees such an object.

.I Avlnext

and

.I avlprev

walk the tree associated with

.IR walk ,

returning the next

(respectively, previous)

tree node in the comparison order

defined by the comparison function

associated with the tree associated with

.IR walk .

.SH EXAMPLES

Intended usage seems to be to make an anonymous

.B Avl

the first member of the application's tree-node structure,

then pass these routines tree-node pointers instead of

.BR Avl* s.

.IP

.EX

typedef struct Node {

	Avl;

	uchar	score[VtScoreSize];

	int	type;

} Node;

.sp 0.3v

Avltree *tree;

Avl *res;

Node *np;

\fI\&...\fP

	res = lookupavl(tree, np);

.EE

.SH SOURCE

.B /sys/src/libavl

.SH SEE ALSO

G. M. Adelson-Velsky,

E. M. Landis,

``An algorithm for the organization of information'',

.IR "Soviet Mathematics" ,

Vol. 3, pp. 1256—1263.

.SH DIAGNOSTICS

Functions returning pointers return

.B nil

on error.