TREE(3)                  BSD Library Functions Manual                  TREE(3)

     TREE_REVERSE_APPLY - implementation of AVL balanced binary trees

     #include <tree.h>



     TREE_INITIALIZER(int (*relation)(NODE *, NODE *));

     TREE_INIT(TREE *head, int (*relation)(NODE *, NODE *));


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

     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-

     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.

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

     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);
               TREE_INSERT(&tree, _Node, linkage, Node_new(line));

       fence = 20;
       printf("first %d elements, forwards:\n", fence);
       TREE_FORWARD_APPLY(&tree, _Node, linkage, Node_printer, stdout);

       fence = 20;
       printf("last %d elements, backwards:\n", fence);
       TREE_REVERSE_APPLY(&tree, _Node, linkage, Node_printer, stdout);

       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.

     The macro TREE_FIND returns a pointer to an element in the tree equal to
     elm or NULL if no such element exists.

     The interface conforms as closely as possible to the that of the standard
     BSD queue(3) macros.


     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.

     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.


     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