tree_init, tree_mung, tree_srch, tree_add, tree_delete, tree_trav -- balanced
binary tree routines
void
tree_init(void **tree);
void *
tree_srch(void **tree, int (*compare)(), void *data);
void
tree_add(void **tree, int (*compare)(), void *data, void (*del_uar)());
int
tree_delete(void **tree, int (*compare)(), void *data,
void (*del_uar)());
int
tree_trav(void **tree, int (*trav_uar)());
void
tree_mung(void **tree, void (*del_uar)());
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 (or, on a RISC
or otherwise alignment constrained system with implied padding, 4+4+4+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.
Balanced binary trees are very fast on searches and replacements, but
have a moderately high cost for additions and deletions. If your application
does a lot more searches and replacements than it does additions
and deletions, the balanced (AVL) binary tree is a good choice for a data
structure.
Tree_init() creates an empty tree and binds it to ``tree'' (which for
this and all other routines in this package should be declared as a
pointer to void or int, and passed by reference), which can then be used
by other routines in this package. Note that more than one ``tree''
variable can exist at once; thus multiple trees can be manipulated simultaneously.
Tree_srch() searches a tree for a specific node and returns either NULL
if no node was found, or the value of the user data pointer if the node
was found. compare() is the address of a function to compare two user
data blocks. This routine should work much the way strcmp(3) does; in
fact, strcmp could be used if the user data was a NUL terminated string.
``Data'' is the address of a user data block to be used by compare() as
the search criteria. The tree is searched for a node where compare()
returns 0.
Tree_add() inserts or replaces a node in the specified tree. The tree
specified by ``tree'' is searched as in tree_srch(), and if a node is
found to match ``data'', then the del_uar() function, if non-NULL, is
called with the address of the user data block for the node (this routine
should deallocate any dynamic memory which is referenced exclusively by
the node); the user data pointer for the node is then replaced by the
value of ``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 ``data''. A rebalance may or may not occur,
depending on where the node is added and what the rest of the tree looks
like. Tree_add() will return the ``data'' pointer unless catastrophe
occurs in which case it will return NULL.
Tree_delete() deletes a node from ``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. Tree_delete() returns TRUE if a node was deleted,
FALSE otherwise.
Tree_trav() traverses all of ``tree'', calling trav_uar() with the
address of each user data block. If trav_uar() returns FALSE at any
time, tree_trav() will immediately return FALSE to its caller. Otherwise
all nodes will be reached and tree_trav() will return TRUE.
Tree_mung() deletes every node in ``tree'', calling del_uar() (if it is
not NULL) with the user data address from each node (see tree_add() and
tree_delete() above). The tree is left in the same state that
tree_init() leaves it in - i.e., empty.
Should have a way for the caller to specify application-specific malloc
and free functions to be used internally when allocating meta data.
Paul Vixie, converted and augumented from Modula-2 examples in
``Algorithms & Data Structures'', Niklaus Wirth, Prentice-Hall, ISBN
0-13-022005-1.
4th Berkeley Distribution April 5, 1994 4th Berkeley Distribution
[ Back ] |
