TREE(3) BSD Library Functions Manual TREE(3)
NAME
TREE_ENTRY, TREE_HEAD, TREE_INITIALIZER, TREE_INIT, TREE_DEFINE,
TREE_INSERT, TREE_FIND, TREE_REMOVE, TREE_FORWARD_APPLY,
TREE_REVERSE_APPLY - implementation of AVL balanced binary trees
SYNOPSIS
#include <tree.h>
TREE_ENTRY(NODE);
TREE_HEAD(TREE, NODE);
TREE_INITIALIZER(int (*relation)(NODE *, NODE *));
TREE_INIT(TREE *head, int (*relation)(NODE *, NODE *));
TREE_DEFINE(NODE, NAME);
TREE_INSERT(TREE *head, NODE, NODE *elm);
TREE_REMOVE(TREE *head, NODE, NODE *elm);
TREE_FIND(TREE *head, NODE, NODE *elm);
TREE_FORWARD_APPLY(TREE *head, void (*functio_n)(TYPE *elm, void *data),
void *data);
TREE_REVERSE_APPLY(TREE *head, void (*functio_n)(TYPE *elm, void *data),
void *data);
DESCRIPTION
These macros define and operate on AVL balanced binary trees. The trees
support the following functionality:
1. Insertion of a new entry in the tree.
2. Removal of any entry in the tree.
3. Search for any entry in the tree.
4. Forward traversal through the tree.
5. Backward traversal through the tree.
In the macro definitions, NODE is the name (tag) of a user-defined struc-
ture, that must contain a field of type TREE_ENTRY named NAME, and TREE
is the name (tag) of a user-defined structure representing the head of
the tree that must be declared using the macro TREE_HEAD.
A tree is headed by a structure defined by the TREE_HEAD macro. This
structure contains a pointer to the root node of the tree and a pointer
to a function that defines the ordering relation between nodes. A
TREE_HEAD structure is declared as follows:
TREE_HEAD(TREE, NODE) head;
where TREE is the name (tag) of the structure to be defined, and NODE is
the name (struture tag) of the elements to be inserted into the tree. A
pointer to the head of the tree can later be declared as:
struct TREE *treep;
(The name treep is user selectable.)
The prototypes for the four macros that accept function arguments might
be confusing. If namespace pollution were not an issue the following
declarations using explicit typedefs would be exactly equivalent:
typedef int (*ORDER_FN)(NODE *lhs, NODE *rhs);
TREE_INIT(TREE *head, ORDER_FN relation);
TREE_INITIALIZER(ORDER_FN relation);
typedef int (*VISITOR)(NODE *elm, void *client_data);
TREE_FORWARD_APPLY(TREE *head, VISITOR func, void *client_data);
TREE_REVERSE_APPLY(TREE *head, VISITOR func, void *client_data);
The macro TREE_ENTRY declares a structure that connects the elements in
the tree.
The macro TREE_INIT initializes the tree referenced by head ordered
according to the given relation, which must be a function taking two
arguments of type NODE and returning -1, zero or 1 if the first argument
is considered less than, equal to or greater than the second argument
respectively. TREE_INITIALIZER provides a corresponding static initial-
izer.
The macro TREE_INSERT inserts the new element elm into the tree and
rebalances it.
The macro TREE_REMOVE removes the element elm from the tree and rebal-
ances it.
The macro TREE_FIND finds an element in the tree that is equal (according
to the tree's ordering relation) to elm, and returns a pointer to it or
NULL if no such element was found.
The macro TREE_FORWARD_APPLY walks the tree in-order from left to right
and calls function for each node visited passing the node as the first
argument and data as the second argument. The macro TREE_REVERSE_APPLY
is similar but walks the tree from right to left.
The macro TREE_DEFINE defines several recursive helper functions needed
to implement trees containing elements of type NODE linked through a
field with the given NAME. This macro should be invoked exactly once for
each type of tree node (a unique combination of NODE tag and entry NAME)
in a given program.
EXAMPLES
The following program reads lines from standard input into a tree struc-
ture, inserting each unique line into the tree. On EOF it prints the
lines in forward and reverse alphabetical order.
#include "tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _Node
{
char *word;
TREE_ENTRY(_Node) linkage;
} Node;
typedef TREE_HEAD(_Tree, _Node) Tree;
TREE_DEFINE(_Node, linkage);
int fence = 0;
Node *Node_new(char *word)
{
Node *self = (Node *)calloc(1, sizeof(Node));
self->word = strdup(word);
return self;
}
int Node_compare(Node *lhs, Node *rhs)
{
return strcmp(lhs->word, rhs->word);
}
void Node_printer(Node *self, void *stream)
{
if (fence)
{
fprintf((FILE *)stream, "%s", self->word);
--fence;
}
}
int main(int argc, char **argv)
{
int count = 0;
Tree tree = TREE_INITIALIZER(Node_compare);
char line[80];
while (fgets(line, sizeof(line), stdin))
{
Node test = { line };
Node *ptr = TREE_FIND(&tree, _Node, linkage, &test);
if (ptr)
printf("ignoring duplicate line: %s", line);
else
{
TREE_INSERT(&tree, _Node, linkage, Node_new(line));
++count;
}
}
fence = 20;
printf("first %d elements, forwards:\n", fence);
TREE_FORWARD_APPLY(&tree, _Node, linkage, Node_printer, stdout);
printf("\n");
fence = 20;
printf("last %d elements, backwards:\n", fence);
TREE_REVERSE_APPLY(&tree, _Node, linkage, Node_printer, stdout);
printf("\n");
printf("inserted %d elements into a tree of depth %d\n",
count, TREE_DEPTH(&tree, linkage));
return 0;
}
The above program typically sorts the contents of /usr/dict/words in less
than twice the time of the system sort(1) utility.
RETURN VALUES
The macro TREE_FIND returns a pointer to an element in the tree equal to
elm or NULL if no such element exists.
COMPATIBILITY
The interface conforms as closely as possible to the that of the standard
BSD queue(3) macros.
SEE ALSO
queue(3)
Georgii M. Adelson-Velskii and Evgenii M. Landis, "An algorithm for the
organization of information", Doklady Akademii Nauk SSSR, 146:263-266,
1962, Russian.
Myron J. Ricci (trans.), Soviet Math., 3:1259-1263, 1962, English.
Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and
Searching, 459, 1998, 2nd ed.
AUTHORS
The software and manual pages were written by Ian Piumarta.
Copyright (c) 2005 Ian Piumarta
All rights reserved.
Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the 'Soft-
ware'), to deal in the Software without restriction, including without
limitation the rights to use, copy, modify, merge, publish, distribute,
and/or sell copies of the Software, and to permit persons to whom the
Software is furnished to do so, provided that the above copyright
notice(s) and this permission notice appear in all copies of the Software
and that both the above copyright notice(s) and this permission notice
appear in supporting documentation.
THE SOFTWARE IS PROVIDED 'AS IS'. USE ENTIRELY AT YOUR OWN RISK.
BUGS
o The implementation should be generalised to support linear lists in
which elements can be searched, inserted and deleted according either
to an ordering relation or to an explicit numeric index, all in O(log
N) time.
Please send bug reports to the author at: firstName (at) lastName (dot)
com. (See AUTHORS above for suitable values of firstName and lastName.)
BSD November 11, 2005 BSD