mirror of
https://github.com/SEPPDROID/Digital-Research-Source-Code.git
synced 2025-10-25 01:14:21 +00:00
125 lines
3.4 KiB
Plaintext
125 lines
3.4 KiB
Plaintext
.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.
|