.TH TREE 2 "23 June 1986"
.UC 4
.SH NAME
tree_init, tree_mung, tree_srch, tree_add, tree_delete, tree_trav \- balanced binary tree routines
.SH SYNOPSIS
.nf
.B void
.B tree_init(tree)
.B int **tree;
.PP
.B int *
.B tree_srch(tree, compare, data)
.B int **tree, (*compare)(), *data;
.PP
.B void
.B tree_add(tree, compare, data, del_uar)
.B int **tree, (*compare)(), *data, (*del_uar)();
.PP
.B int
.B tree_delete(tree, compare, data, del_uar)
.B int **tree, (*compare)(), *data, (*del_uar)();
.PP
.B int
.B tree_trav(tree, trav_uar)
.B int **tree, (*trav_uar)();
.PP
.B void
.B tree_mung(tree, del_uar)
.B int **tree, (*del_uar)();
.fi
.SH DESCRIPTION
These functions create and manipulate a balanced binary (AVL) tree.  Each node
of the tree contains the expected left & right subtree pointers, a short-int
balance indicator, and a pointer to the user-data.  On a 32-bit system, this
means an overhead of 4+4+2+4 bytes per node.  There is no key data type
enforced by this package; a caller-supplied compare routine is used to compare
user-data blocks.
.PP
.I Tree_init
creates an empty tree and binds it to
.I tree
(which for this and all other routines in this package should be declared as
a pointer to integer and passed by reference), which can then be used by other
routines in this package.  Note that more than one
.I tree
variable can exist at once; thus multiple trees can be manipulated
simultaneously.
.PP
.I Tree_srch
searches a tree for a specific node and returns either
.I NULL
if no node was found, or the address of the user-data for that node if one was
found.
.I compare
is the address of a function to compare two user-data blocks.  This routine
should work much the way 
.IR strcmp 2
does; in fact,
.I strcmp
could be used if the user-data was a null-terminated string.
.I data
is the address of a user-data block to be used via
.I compare
as the search criteria.  The tree is searched for a node where
.I compare
returns 0.
.PP
.I Tree_add
inserts or replaces a node in the specified tree.  The tree specified by
.I tree
is searched as in
.I tree_srch,
and if a node is found to match
.I data,
then the
.I del_uar
function is called with the address of the user-data block for the node
(this routine should deallocate any dynamic memory which is pointed to
exclusively by the node); the user-data pointer for the node is then
replaced by the value of
.I data.
If no node is found to match, a new node is added (which may or may not
cause a transparent rebalance operation), with a user-data pointer equal
to
.I data.
.PP
.I Tree_delete
deletes a node from
.I tree.
A rebalance may or may not occur, depending on where the node is removed from
and what the rest of the tree looks like.
.I Tree_delete
returns TRUE if a node was deleted, FALSE otherwise.
.PP
.I Tree_trav
traverses all of
.I tree,
calling
.I trav_uar
with the address of each user-data block.  If
.I trav_uar
returns FALSE at any time,
.I tree_trav
will immediately return FALSE to its caller.  Otherwise all nodes will be 
reached and
.I tree_trav
will return TRUE.
.PP
.I Tree_mung
deletes every node in
.I tree,
calling
.I del_uar
with the user-data address from each node (see
.I tree_add
and
.I tree_delete
above).  The tree is left in the same state that
.I tree_init
leaves it in \- i.e., empty.
.SH AUTHOR
Paul Vixie, converted and augumented from Modula-2 examples in
.I Algorithms & Data Structures,
Niklaus Wirth, Prentice-Hall, ISBN 0-13-022005-1.