rbtree(3C)


rbtree: rbt_delete, rbt_find, rbt_free, rbt_init, rbt_insert, rbt_walk -- manage balanced binary tree

Synopsis

   #include <rbtree.h>
   

RBTree *rbt_init(size_t n, int (*cmp)(const void *, const void *), void *(*alloc)(size_t), void (*toss)(const void *));

void rbt_walk(RBTree *rbtp, int order, void (*operate)(const void *));

void rbt_free(RBTree *rbtp);

void *rbt_find(RBTree *rbtp, const void *item);

void *rbt_insert(RBTree *rbtp, const void *item);

in rbt_delete(RBTree *rbtp, const void *item);

Description

These functions manage a ``balanced'' binary tree of arbitrary content. Each tree is created by calling rbt_init. The argument n gives the size of the data to be stored in each node, and the other three arguments are pointers to functions:

cmp
the comparison function used to order the tree

alloc
used to allocate node space

toss
used to deallocate node space.
These three function pointers can be null requesting the default functions, strcmp, malloc, and free respectively. The value returned is the handle for the just-created empty tree, which is the argument rbtp passed to the other functions. A tree is destroyed by calling rbt_free.

A tree is traversed by calling rbt_walk. The six different regular traversals are specified by the order argument. It is exactly one of RBT_PREORDER, RBT_INORDER, or RBT_POSTORDER, optionally combined (bitwise OR) with RBT_REVERSE. A ``preorder'' traversal visits the parent before either child, a ``postorder'' traversal visits the parent after any child, and an ``inorder'' traversal visits the parent between the two children. Unless RBT_REVERSE is specified, the children are visited in ascending order (as specified by the cmp argument). Visiting a node causes the function pointed to by the operate argument to be called, being passed a pointer to the start of that node's data.

For the remaining functions, item points to a particular data item to which the function is to be applied.

A data item can be searched for without modifying the tree by calling rbt_find. rbt_insert acts just like rbt_find except the data will be added to the tree if a match is not found. And, rbt_delete will remove the item from the tree if it was present.

Return values

rbt_init and rbt_insert return a null pointer for an allocation failure. Or, in other words, when the function pointed to by the alloc argument returns a null pointer. When rbt_insert returns a non-null pointer, it points to the start of the matching data.

rbt_find returns a null pointer if no match for the data is found; otherwise it returns a pointer to the start of the matching data.

rbt_delete returns nonzero when no match for the item is present in the tree; otherwise it returns zero having found a match and removed it from the tree.

References

malloc(3C), string(3C)

Usage

The following shows adding a collection of invocation parameter strings into a tree, and then printing them out, one per line, in descending order.
   #include <rbtree.h>
   #include <stdio.h>
   #include <string.h>
   

static int compare(const void *p1, const void *p2) { return strcmp(*(const char **)p1, *(const char **)p2); }

static void print(const void *p) { puts(*(const char **)p); }

int main(int argc, char **argv) { const char *s; RBTree *rbtp;

if ((rbtp = rbt_init(sizeof(const char *), &compare, 0, 0)) == 0) return 2; while ((s = *++argv) != 0) { if (rbt_insert(rbtp, &s) == 0) return 2; } rbt_walk(rbtp, RBT_INORDER|RBT_REVERSE, &print); rbt_free(rbtp); return 0; }

If the above is invoked with the three arguments ``aa cc bb'', it will output these three lines:
      cc
      bb
      aa

Algorithm

The tree is balanced using a ``Red Black'' data structure in which each binary node can be thought of as being all or a portion of a node in a balanced 2-3-4 tree. A balanced 2-3-4 tree always has the same distance from the root to any leaf. This is accomplished by adjusting the number of children of individual 2-3-4 tree nodes, since a 2-3-4 node is either a leaf (and thus has no children) or it has 2, 3 or 4 children.
© 2004 The SCO Group, Inc. All rights reserved.
UnixWare 7 Release 7.1.4 - 25 April 2004