rob@cs.vu.nl (Rob van Leeuwen) (01/09/90)
Hello there,
now that everybody has got 1.5.0 running (:-) and its library turns out
to be 100K+ anyway, it's time to add in some sophisticated stuff. Below
are included source, manual page and an example program for tsearch(3) -
a standard part of the library on some (SUN OS, SysV) UNIX systems.
The routines tsearch, tfind, tdelete and twalk manage height-balanced
binary (AVL) trees and are a reimplementation of the plain non-balanced
binary tree tsearch(3) modules found on other systems.
This package outperforms standard implementations in terms of speed due
to a better algorithm. The library entry will cost you 3K, but you'll
have something better than available on any big UNIXes (how's that for
a trade-off :-).
Have fun with it,
Peter Valkenburg (valke@psy.vu.nl).
(using someone else's account since
the local machine has run out of
disk space).
BTW: I posted a version to comp.sources.unix a while ago, but there is
no noticeable activity in that group. Is mr. Salz still out there?
Cut below the next line, and feed to sh.
------------------------------------------------------------------------
echo x - README
sed '/^X/s///' > README << '/'
X tsearch - tsearch(3) compatible AVL routines
X
XThe directories here contain sources and tests for an implementation of
Xheight balanced AVL trees. Its interface is compatible with that of
Xtsearch(3) found on some UNIX systems, but its average case behaviour
Xis slightly better, and its worst case behavior much better than the
Xstandard non-balanced binary tree implementations. Adding, searching
Xor deleting an element all cost time in the order of 2log(n), where n
Xis the number of elements already in the tree.
X
XThis version runs on any system with a proper C compiler, though the
Xcomments below apply to MINIX.
X
XThe contents of this directory:
X README - this file
X tsearch.c - tsearch library source
X search.h - include file
X tsearch.3 - manual page
X example.c - example program
X
XTo get a library assembly module tsearch.s, type:
X cc -S -LIB -I. tsearch.c
XIf you wish, you can then add it your library. It uses malloc & free,
Xso don't put it beyond those modules. The include file should go to
X/usr/include.
X
XTo test the library, type:
X cc example.c tsearch.c
XThe resulting a.out reads lines from standard input, adding each line
Xto a binary tree maintained by tsearch, upto an empty line. It then
Xreads more lines and deletes each of them (if present). After EOF it
Xprints out the remaining sorted set of lines.
X
XThe manual page is ready for insertion in the 1.5.0 /usr/man/man3 file.
XIt is not in [nt]roff source format.
/
echo x - example.c
sed '/^X/s///' > example.c << '/'
X#include <stdio.h>
X#include <search.h>
X
Xextern char **tsearch(), **tdelete(), **tfind();
Xextern void twalk();
Xextern char *strcpy(), *gets(), *malloc();
Xextern int strcmp();
X
Xvoid print(keyp, visit, level)
Xchar **keyp;
XVISIT visit;
Xint level;
X{
X /* print in order visits and leafs only */
X if (visit == postorder || visit == leaf)
X (void) puts(*keyp);
X}
X
Xvoid disp(keyp, visit, level)
Xchar **keyp;
XVISIT visit;
Xint level;
X{
X /* dispose on last visit only */
X if (visit == endorder || visit == leaf) {
X free(*keyp); /* free string */
X free((char *) keyp); /* free its node */
X }
X}
X
Xmain()
X{
X char *tree = NULL; /* empty tree */
X char buf[BUFSIZ], *sav, **keyp;
X unsigned savsiz;
X
X /* get strings and store then */
X while (gets(buf) != NULL) {
X if (*buf == 0)
X break; /* go delete */
X if (tfind(buf, &tree, strcmp) == NULL) {
X savsiz = strlen(buf) + 1;
X if ((sav = malloc(savsiz)) == NULL) {
X (void) fputs("Malloc fails", stderr);
X exit(1);
X }
X (void) strcpy(sav, buf);
X if (tsearch(sav, &tree, strcmp) == NULL) {
X (void) fputs("Tsearch fails", stderr);
X exit(1);
X }
X }
X }
X
X /* now get more strings and remove them */
X while (gets(buf) != NULL)
X if ((keyp = tfind(buf, &tree, strcmp)) != NULL) {
X sav = *keyp; /* keyp will be invalid */
X (void) tdelete(buf, &tree, strcmp);
X free(sav); /* free string */
X }
X
X twalk(tree, print); /* print tree */
X
X twalk(tree, disp); /* efficiently dispose of tree */
X}
/
echo x - search.h
sed '/^X/s///' > search.h << '/'
X/*
X * "search.h", Peter Valkenburg, november '89.
X */
X
X#ifndef _SEARCH_H
X#define _SEARCH_H
X
X/*
X * Type for twalk node visiting. Normally part of "/usr/include/search.h".
X */
Xtypedef enum {
X preorder, postorder, endorder, leaf
X} VISIT;
X
X#endif /* _SEARCH_H */
/
echo x - tsearch.3
sed '/^X/s///' > tsearch.3 << '/'
X#tsearch,tfind,tdelete,twalk
XNAME
X tsearch, tfind, tdelete, twalk - manage binary search trees
XSYNTAX
X #include <search.h>
X
X char **tsearch(key, rootp, compar)
X char **tfind(key, rootp, compar)
X char **tdelete(key, rootp, compar)
X char *key;
X char **rootp;
X int (*compar)();
X
X void twalk(root, action)
X char *root;
X void (*action)();
XDESCRIPTION
X Tsearch(), tfind(), tdelete() and twalk() implement height
X balanced binary (AVL) trees. They have exactly the same
X interface as the standard unbalanced binary tree tsearch(3)
X implemementations, but are faster on average case add/
X delete sequences; worst case performance is much better
X since tdelete() and tsearch() use in the order of 2log(n)
X operations per call (n is size of the tree).
X
X All comparisons are done with the user-supplied routine
X compar(). This routine gets two element pointers. It
X should return an integer less than, equal to, or greater
X than 0, according to whether the first argument is to be
X considered less than, equal to, or greater than the second.
X Rootp points to a variable that contains the pointer to the
X root of the tree. A NULL value for the variable pointed to
X by rootp denotes an empty tree. This variable's value may
X be changed by tsearch() or tdelete().
X
X Tsearch() is used to build and access the tree. Key is an
X element pointer to be accessed or stored. If there is an
X element pointer in the tree for which compar() compares
X equal to key, a pointer to it is returned. Otherwise, key
X is inserted, and a pointer to it (which is also a pointer
X to the node that contains it) is returned. Only key is
X copied, so the calling routine must store the data for the
X new element.
X
X Like tsearch(), tfind() will search for an element in the
X tree, returning its pointer if found. However, if it is
X not found, NULL is returned. The arguments are the same as
X for tsearch().
X
X Tdelete() deletes a node from a binary search tree. The
X arguments are the same as for tsearch(). The variable
X pointed to by rootp will be changed if the deleted node was
X the root of the tree. Tdelete() returns a pointer to the
X parent (which is also a pointer to the parent's key) of the
X deleted node, or a NULL pointer if the node is not found.
X
X Twalk() traverses a binary search tree. Root is the root
X of the tree to be traversed, which can also be a value
X returned by any of the other routines. Action is the name
X of a routine to be called at each node. This routine gets
X three arguments. The first argument is a pointer to the
X node being visited, which is also a pointer to its key.
X The second argument is a value of the following enumeration
X data type defined in <search.h>:
X typedef enum {preorder, postorder, endorder, leaf} VISIT;
X This depends on whether a node is visited the first, second
X or third time during a depth-first, left-to-right traversal
X of the tree, or whether it is a leaf.
X The third argument is the level of the node in the tree,
X where the root is level zero.
XDIAGNOSTICS
X A NULL pointer is returned by tsearch() if there is not
X enough space available to create a new node.
X A NULL pointer is returned by tsearch(), tfind() and
X tdelete() if rootp was NULL.
X If the element is found, both tsearch() and tfind() return
X a pointer to it. Else tfind() returns NULL and tsearch()
X returns a pointer to the new key.
XBUGS
X The interface is horrible.
X The return values of tsearch(), tdelete() and tfind() are
X both pointers to nodes in the trees, and pointers to keys
X (i.e. pointers to element pointers). Though behaviour is
X identical, the declaration above is slightly different
X from that in some other tsearch(3) manuals.
XSEE ALSO
X bsearch(3), hsearch(3), lsearch(3)
/
echo x - tsearch.c
sed '/^X/s///' > tsearch.c << '/'
X/*
X * "tsearch.c", Peter Valkenburg & Michiel Huisjes, november '89.
X *
X * Standard tsearch(3) compatible implementation of AVL height
X * balanced trees. Performance is slightly better than SUN OS
X * tsearch(3) for average case delete/add operations, but worst
X * case behaviour (i.e. when ordinary trees get unbalanced) is
X * much better. Tsearch/tdelete/tfind run in O(2log(n)), twalk
X * in O(n), where n is the size of binary tree.
X * Entry points:
X * NODE *tsearch((char *)key, (NODE **)rootp, int (*compar)());
X * NODE *tdelete((char *)key, (NODE **)rootp, int (*compar)());
X * NODE *tfind((char *)key, (NODE **)rootp, int (*compar)());
X * void twalk((NODE *root), void (*action)());
X * Here key is a pointer to any datum (to be) held in the tree rooted
X * by *rootp or root. Keys are compared by calling compar, which gets
X * two key arguments and should return a value < 0, 0, or > 0, if the
X * first parameter is to be considered less than , equal to, or greater
X * than the second, respectively. Users can declare type (NODE *) as
X * (char *) and (NODE **) as (char **). The return values of tsearch/
X * tdelete/tfind can be used as pointers to the key pointers of their
X * NODE, by casting them to (char **).
X * See manual page tsearch(3) for more extensive user documentation.
X */
X
X#include <lib.h> /* this doesn't do anything */
X#include <search.h>
X
X/*
X * Type for doubly linked AVL tree.
X */
Xtypedef struct node_s {
X char *key; /* ptr to datum */
X struct node_s *parent; /* ptr to parent ancestor */
X struct node_s *sibls[2]; /* ptrs to L/R siblings */
X int balance; /* balance value (-1, 0 or +1) */
X} NODE;
X
X#define NIL_NODE ((NODE *) 0) /* ptr for empty (sub)trees */
X
Xtypedef int DIR; /* type for indexing siblings */
X#define L ((DIR) 0)
X#define R ((DIR) 1)
X
X#define LEFT sibls[L] /* left sibling pointer NODE field */
X#define RIGHT sibls[R] /* right sibling pointer NODE field */
X
X/*
X * Direction gives direction in which child NODE c is under parent NODE p.
X */
X#define direction(p, c) ((DIR) ((p)->RIGHT == (c)))
X
X/*
X * Cmp_dir gives direction corresponding with compare value v (R iff v > 0).
X */
X#define cmp_dir(v) ((DIR) ((v) > 0))
X
X/*
X * Siblingp yields ptr to left (d == L) or right (d == R) child of NODE n.
X */
X#define siblingp(n, d) ((n)->sibls + (d))
X
X/*
X * Parentp yields ptr to parent's ptr to NODE n, or root ptr r if n is 0.
X */
X#define parentp(r, n) ((n)->parent == NIL_NODE ? (r) : \
X siblingp((n)->parent, direction((n)->parent, (n))))
X
X/*
X * Dir_bal yields balance value corresponding to DIR d.
X */
X#define dir_bal(d) ((d) == L ? -1 : 1)
X
Xstatic NODE *balance();
Xstatic NODE *single_rotation();
Xstatic NODE *double_rotation();
Xstatic void do_walk();
Xextern char *malloc();
Xextern free();
X
X/*
X * Tsearch adds node key to tree rooted by *rootp, using compar for
X * comparing elements. It returns the pointer to the NODE in which
X * the (possibly already existing) key pointer resides.
X */
XNODE *tsearch(key, rootp, compar)
Xchar *key;
Xregister NODE **rootp;
Xint (*compar)();
X{
X register NODE *parent, *child;
X NODE *nnode;
X register DIR d;
X register int cmp;
X
X if (rootp == 0)
X return NIL_NODE;
X
X /* find place where key should go */
X parent = NIL_NODE;
X child = *rootp;
X while (child != NIL_NODE) {
X if ((cmp = compar(key, child->key)) == 0)
X return child;
X parent = child;
X child = *siblingp(child, cmp_dir(cmp));
X }
X
X /* create new node and set its parent's sibling pointer */
X if ((nnode = (NODE *) malloc(sizeof(NODE))) == NIL_NODE)
X return NIL_NODE;
X nnode->key = key;
X nnode->balance = 0;
X nnode->parent = parent;
X nnode->LEFT = nnode->RIGHT = NIL_NODE;
X if (parent == NIL_NODE) {
X *rootp = nnode;
X return nnode; /* just created tree */
X }
X *siblingp(parent, cmp_dir(cmp)) = nnode;
X child = nnode;
X
X /*
X * Back up until tree is balanced. This is achieved when either
X * the tree is balanced by rotation or a node's balance becomes 0.
X */
X do {
X d = direction(parent, child);
X if (parent->balance == dir_bal(d)) {
X (void) balance(rootp, parent, d);
X return nnode;
X }
X else if ((parent->balance += dir_bal(d)) == 0)
X return nnode;
X child = parent;
X parent = parent->parent;
X } while (parent != NIL_NODE);
X
X return nnode;
X}
X
X/*
X * Tdelete removes key from the tree rooted by *rootp, using compar
X * for comparing elements. It returns the pointer to the NODE that
X * was the parent of the NODE that contained the key pointer, 0 if
X * it did not exist.
X */
XNODE *tdelete (key, rootp, compar)
Xchar *key;
Xregister NODE **rootp;
Xint (*compar)();
X{
X register NODE *parent, *child;
X NODE *dnode, *dparent;
X register DIR d;
X register int cont_bal;
X register int cmp;
X
X if (rootp == 0)
X return NIL_NODE;
X
X /* find node to delete */
X child = *rootp;
X while (child != NIL_NODE) {
X if ((cmp = compar(key, child->key)) == 0)
X break;
X child = *siblingp(child, cmp_dir(cmp));
X }
X if (child == NIL_NODE)
X return NIL_NODE; /* key not in tree */
X
X /* the node was found; get its successor (if any) to replace it */
X dnode = child;
X dparent = dnode->parent;
X child = child->RIGHT;
X if (child == NIL_NODE) { /* no successor for key */
X if ((child = dnode->LEFT) != NIL_NODE)
X child->parent = dparent; /* set new parent */
X if (dparent == NIL_NODE) {
X free((char *) dnode);
X *rootp = child;
X return NIL_NODE; /* just deleted the root */
X }
X d = direction (dparent, dnode); /* for back up */
X *siblingp(dparent, d) = child; /* replace by left child */
X free ((char *) dnode);
X parent = dparent;
X }
X else { /* key's successor exists */
X while (child->LEFT != NIL_NODE)
X child = child->LEFT;
X parent = child->parent;
X d = direction(parent, child); /* for back up */
X *siblingp(parent, d) = child->RIGHT;
X if (child->RIGHT != NIL_NODE)
X child->RIGHT->parent = parent; /* set new parent */
X dnode->key = child->key; /* successor replaces key */
X free((char *) child);
X }
X
X /*
X * Back up until tree is balanced. This is achieved when either
X * the tree is balanced by rotation but not made shorter, or a
X * node's balance was 0 before deletion.
X */
X do {
X if (parent->balance == dir_bal(!d)) {
X cont_bal = ((*siblingp(parent, !d))->balance != 0);
X parent = balance(rootp, parent, !d);
X }
X else {
X cont_bal = (parent->balance != 0);
X parent->balance += dir_bal(!d);
X }
X child = parent;
X if ((parent = parent->parent) == NIL_NODE)
X return dparent; /* we reached the root */
X d = direction(parent, child);
X } while (cont_bal);
X
X return dparent;
X}
X
X/*
X * Balance the subtree rooted at sb that has become to heavy on side d.
X * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
X * the top of the entire tree.
X */
Xstatic NODE *balance(rootp, sb, d)
XNODE **rootp;
XNODE *sb;
XDIR d;
X{
X NODE *sb_next = *siblingp(sb, d);
X
X if (sb_next->balance == -dir_bal(d))
X return double_rotation(rootp, sb, sb_next, d);
X else
X return single_rotation(rootp, sb, sb_next, d);
X}
X
X/*
X * Balance the subtree rooted at sb that has become to heavy on side d
X * by single rotation of sb and sb_next.
X * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
X * the top of the entire tree.
X *
X * sb sb_next Single rotation: Adding x or
X * / \ / \ deleting under 3 caused
X * sb_next 3 1 sb rotation. Same holds for mirror
X * / \ | / \ image. Single_rotation returns
X * 1 2 ==> x 2 3 top of new balanced tree.
X * | | |
X * x y y
X */
Xstatic NODE *single_rotation(rootp, sb, sb_next, d)
XNODE **rootp;
Xregister NODE *sb, *sb_next;
Xregister DIR d;
X{
X *siblingp(sb, d) = *siblingp(sb_next, !d);
X *siblingp(sb_next, !d) = sb;
X
X sb->balance -= sb_next->balance;
X sb_next->balance = -sb->balance;
X
X *parentp(rootp, sb) = sb_next;
X sb_next->parent = sb->parent;
X sb->parent = sb_next;
X if (*siblingp(sb, d) != NIL_NODE)
X (*siblingp(sb, d))->parent = sb;
X
X return sb_next;
X}
X
X/*
X * Balance the subtree rooted at sb that has become to heavy on side d
X * by double rotation of sb and sb_next.
X * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
X * the top of the entire tree.
X *
X * sb sb_next2 Double rotation: Adding x or
X * / \ / \ x', or deleting under 4
X * sb_next \ sb_next sb caused rotation. Same holds
X * / \ \ / \ / \ for the mirror image.
X * 1 sb_next2 4 ==> 1 2 3 4 Double_rotation returns top
X * / \ | | of new balanced tree.
X * 2 3 x x'
X * | |
X * x x'
X */
Xstatic NODE *double_rotation(rootp, sb, sb_next, d)
XNODE **rootp;
Xregister NODE *sb, *sb_next;
Xregister DIR d;
X{
X register NODE *sb_next2 = *siblingp(sb_next, !d);
X
X *siblingp(sb_next, !d) = *siblingp(sb_next2, d);
X *siblingp(sb, d) = *siblingp(sb_next2, !d);
X *siblingp(sb_next2, d) = sb_next;
X *siblingp(sb_next2, !d) = sb;
X
X if (sb_next2->balance == sb_next->balance)
X sb_next->balance = -sb_next->balance;
X else
X sb_next->balance = 0;
X if (sb_next2->balance == sb->balance)
X sb->balance = -sb->balance;
X else
X sb->balance = 0;
X sb_next2->balance = 0;
X
X *parentp(rootp, sb) = sb_next2;
X sb_next2->parent = sb->parent;
X sb->parent = sb_next->parent = sb_next2;
X if (*siblingp(sb_next, !d) != NIL_NODE)
X (*siblingp(sb_next, !d))->parent = sb_next;
X if (*siblingp(sb, d) != NIL_NODE)
X (*siblingp(sb, d))->parent = sb;
X
X return sb_next2;
X}
X
X/*
X * Tfind searches node key in the tree rooted by *rootp, using compar for
X * comparing elements. It returns the pointer to the NODE in which
X * the key pointer resides, or 0 if key is not present.
X */
XNODE *tfind(key, rootp, compar)
Xchar *key;
XNODE **rootp;
Xint (*compar)();
X{
X register NODE *node;
X register int cmp;
X
X if (rootp == 0)
X return NIL_NODE;
X
X node = *rootp;
X while (node != NIL_NODE) {
X if ((cmp = compar(key, node->key)) == 0)
X return node;
X node = *siblingp(node, cmp_dir(cmp));
X }
X
X return NIL_NODE;
X}
X
X/*
X * Twalk walks the tree rooted by node, from top to bottom and left
X * to right, calling action with the NODE pointer, visit order, and
X * level in the tree (0 is root). Leafs are visited only once and
X * action is then called with `leaf' as the second parameter. For
X * nodes with children action is called three times with visit order
X * parameter `preorder' before, `postorder' in between, and `endorder'
X * after visiting the nodes children.
X */
Xvoid twalk(node, action)
Xregister NODE *node;
Xregister void (*action)();
X{
X register VISIT visit;
X register int level;
X
X if (node == 0 || action == 0)
X return;
X
X /* run down tree from top to bottom, left to right */
X visit = preorder;
X level = 0;
X while (node != NIL_NODE) {
X if (visit == preorder &&
X node->LEFT == NIL_NODE && node->RIGHT == NIL_NODE)
X visit = leaf; /* node turns out to be leaf */
X
X action(node, visit, level);
X
X switch (visit) {
X case preorder: /* before visiting left child */
X if (node->LEFT != NIL_NODE) {
X node = node->LEFT;
X level++;
X }
X else
X visit = postorder;
X break;
X case postorder: /* between visiting children */
X if (node->RIGHT != NIL_NODE) {
X node = node->RIGHT;
X visit = preorder;
X level++;
X }
X else
X visit = endorder;
X break;
X case endorder: /* after visiting children */
X case leaf: /* node has no children */
X if (node->parent != NIL_NODE)
X if (direction(node->parent, node) == L)
X visit = postorder;
X else
X visit = endorder;
X node = node->parent;
X level--;
X break;
X }
X }
X}
/
exit 0valke@wundt.psy.vu.nl (Peter Valkenburg) (01/09/90)
Hello there,
now that everybody has got 1.5.0 running :-) and its library turns out
to be 100K+ anyway, it's time to add in some sophisticated stuff. Below
are included source, manual page and an example program for tsearch(3) -
a standard part of the library on some (SUN OS, SysV) UNIX systems.
The routines tsearch, tfind, tdelete and twalk manage height-balanced
binary (AVL) trees and are a reimplementation of the plain non-balanced
binary tree tsearch(3) modules found on other systems.
This package outperforms standard implementations in terms of speed due
to a better algorithm. The library entry will cost you 3K, but you'll
have something better than available on any big UNIXes (how's that for
a trade-off :-).
Have fun with it,
Peter Valkenburg (valke@psy.vu.nl).
BTW: I posted a version to comp.sources.unix a while ago, but there is
no noticeable activity in that group. Is mr. Salz still out there?
Cut below the next line, and feed to sh.
------------------------------------------------------------------------
echo x - README
sed '/^X/s///' > README << '/'
X tsearch - tsearch(3) compatible AVL routines
X
XThe directories here contain sources and tests for an implementation of
Xheight balanced AVL trees. Its interface is compatible with that of
Xtsearch(3) found on some UNIX systems, but its average case behaviour
Xis slightly better, and its worst case behavior much better than the
Xstandard non-balanced binary tree implementations. Adding, searching
Xor deleting an element all cost time in the order of 2log(n), where n
Xis the number of elements already in the tree.
X
XThis version runs on any system with a proper C compiler, though the
Xcomments below apply to MINIX.
X
XThe contents of this directory:
X README - this file
X tsearch.c - tsearch library source
X search.h - include file
X tsearch.3 - manual page
X example.c - example program
X
XTo get a library assembly module tsearch.s, type:
X cc -S -LIB -I. tsearch.c
XIf you wish, you can then add it your library. It uses malloc & free,
Xso don't put it beyond those modules. The include file should go to
X/usr/include.
X
XTo test the library, type:
X cc example.c tsearch.c
XThe resulting a.out reads lines from standard input, adding each line
Xto a binary tree maintained by tsearch, upto an empty line. It then
Xreads more lines and deletes each of them (if present). After EOF it
Xprints out the remaining sorted set of lines.
X
XThe manual page is ready for insertion in the 1.5.0 /usr/man/man3 file.
XIt is not in [nt]roff source format.
/
echo x - example.c
sed '/^X/s///' > example.c << '/'
X#include <stdio.h>
X#include <search.h>
X
Xextern char **tsearch(), **tdelete(), **tfind();
Xextern void twalk();
Xextern char *strcpy(), *gets(), *malloc();
Xextern int strcmp();
X
Xvoid print(keyp, visit, level)
Xchar **keyp;
XVISIT visit;
Xint level;
X{
X /* print in order visits and leafs only */
X if (visit == postorder || visit == leaf)
X (void) puts(*keyp);
X}
X
Xvoid disp(keyp, visit, level)
Xchar **keyp;
XVISIT visit;
Xint level;
X{
X /* dispose on last visit only */
X if (visit == endorder || visit == leaf) {
X free(*keyp); /* free string */
X free((char *) keyp); /* free its node */
X }
X}
X
Xmain()
X{
X char *tree = NULL; /* empty tree */
X char buf[BUFSIZ], *sav, **keyp;
X unsigned savsiz;
X
X /* get strings and store then */
X while (gets(buf) != NULL) {
X if (*buf == 0)
X break; /* go delete */
X if (tfind(buf, &tree, strcmp) == NULL) {
X savsiz = strlen(buf) + 1;
X if ((sav = malloc(savsiz)) == NULL) {
X (void) fputs("Malloc fails", stderr);
X exit(1);
X }
X (void) strcpy(sav, buf);
X if (tsearch(sav, &tree, strcmp) == NULL) {
X (void) fputs("Tsearch fails", stderr);
X exit(1);
X }
X }
X }
X
X /* now get more strings and remove them */
X while (gets(buf) != NULL)
X if ((keyp = tfind(buf, &tree, strcmp)) != NULL) {
X sav = *keyp; /* keyp will be invalid */
X (void) tdelete(buf, &tree, strcmp);
X free(sav); /* free string */
X }
X
X twalk(tree, print); /* print tree */
X
X twalk(tree, disp); /* efficiently dispose of tree */
X}
/
echo x - search.h
sed '/^X/s///' > search.h << '/'
X/*
X * "search.h", Peter Valkenburg, november '89.
X */
X
X#ifndef _SEARCH_H
X#define _SEARCH_H
X
X/*
X * Type for twalk node visiting. Normally part of "/usr/include/search.h".
X */
Xtypedef enum {
X preorder, postorder, endorder, leaf
X} VISIT;
X
X#endif /* _SEARCH_H */
/
echo x - tsearch.3
sed '/^X/s///' > tsearch.3 << '/'
X#tsearch,tfind,tdelete,twalk
XNAME
X tsearch, tfind, tdelete, twalk - manage binary search trees
XSYNTAX
X #include <search.h>
X
X char **tsearch(key, rootp, compar)
X char **tfind(key, rootp, compar)
X char **tdelete(key, rootp, compar)
X char *key;
X char **rootp;
X int (*compar)();
X
X void twalk(root, action)
X char *root;
X void (*action)();
XDESCRIPTION
X Tsearch(), tfind(), tdelete() and twalk() implement height
X balanced binary (AVL) trees. They have exactly the same
X interface as the standard unbalanced binary tree tsearch(3)
X implemementations, but are faster on average case add/
X delete sequences; worst case performance is much better
X since tdelete() and tsearch() use in the order of 2log(n)
X operations per call (n is size of the tree).
X
X All comparisons are done with the user-supplied routine
X compar(). This routine gets two element pointers. It
X should return an integer less than, equal to, or greater
X than 0, according to whether the first argument is to be
X considered less than, equal to, or greater than the second.
X Rootp points to a variable that contains the pointer to the
X root of the tree. A NULL value for the variable pointed to
X by rootp denotes an empty tree. This variable's value may
X be changed by tsearch() or tdelete().
X
X Tsearch() is used to build and access the tree. Key is an
X element pointer to be accessed or stored. If there is an
X element pointer in the tree for which compar() compares
X equal to key, a pointer to it is returned. Otherwise, key
X is inserted, and a pointer to it (which is also a pointer
X to the node that contains it) is returned. Only key is
X copied, so the calling routine must store the data for the
X new element.
X
X Like tsearch(), tfind() will search for an element in the
X tree, returning its pointer if found. However, if it is
X not found, NULL is returned. The arguments are the same as
X for tsearch().
X
X Tdelete() deletes a node from a binary search tree. The
X arguments are the same as for tsearch(). The variable
X pointed to by rootp will be changed if the deleted node was
X the root of the tree. Tdelete() returns a pointer to the
X parent (which is also a pointer to the parent's key) of the
X deleted node, or a NULL pointer if the node is not found.
X
X Twalk() traverses a binary search tree. Root is the root
X of the tree to be traversed, which can also be a value
X returned by any of the other routines. Action is the name
X of a routine to be called at each node. This routine gets
X three arguments. The first argument is a pointer to the
X node being visited, which is also a pointer to its key.
X The second argument is a value of the following enumeration
X data type defined in <search.h>:
X typedef enum {preorder, postorder, endorder, leaf} VISIT;
X This depends on whether a node is visited the first, second
X or third time during a depth-first, left-to-right traversal
X of the tree, or whether it is a leaf.
X The third argument is the level of the node in the tree,
X where the root is level zero.
XDIAGNOSTICS
X A NULL pointer is returned by tsearch() if there is not
X enough space available to create a new node.
X A NULL pointer is returned by tsearch(), tfind() and
X tdelete() if rootp was NULL.
X If the element is found, both tsearch() and tfind() return
X a pointer to it. Else tfind() returns NULL and tsearch()
X returns a pointer to the new key.
XBUGS
X The interface is horrible.
X The return values of tsearch(), tdelete() and tfind() are
X both pointers to nodes in the trees, and pointers to keys
X (i.e. pointers to element pointers). Though behaviour is
X identical, the declaration above is slightly different
X from that in some other tsearch(3) manuals.
XSEE ALSO
X bsearch(3), hsearch(3), lsearch(3)
/
echo x - tsearch.c
sed '/^X/s///' > tsearch.c << '/'
X/*
X * "tsearch.c", Peter Valkenburg & Michiel Huisjes, november '89.
X *
X * Standard tsearch(3) compatible implementation of AVL height
X * balanced trees. Performance is slightly better than SUN OS
X * tsearch(3) for average case delete/add operations, but worst
X * case behaviour (i.e. when ordinary trees get unbalanced) is
X * much better. Tsearch/tdelete/tfind run in O(2log(n)), twalk
X * in O(n), where n is the size of binary tree.
X * Entry points:
X * NODE *tsearch((char *)key, (NODE **)rootp, int (*compar)());
X * NODE *tdelete((char *)key, (NODE **)rootp, int (*compar)());
X * NODE *tfind((char *)key, (NODE **)rootp, int (*compar)());
X * void twalk((NODE *root), void (*action)());
X * Here key is a pointer to any datum (to be) held in the tree rooted
X * by *rootp or root. Keys are compared by calling compar, which gets
X * two key arguments and should return a value < 0, 0, or > 0, if the
X * first parameter is to be considered less than , equal to, or greater
X * than the second, respectively. Users can declare type (NODE *) as
X * (char *) and (NODE **) as (char **). The return values of tsearch/
X * tdelete/tfind can be used as pointers to the key pointers of their
X * NODE, by casting them to (char **).
X * See manual page tsearch(3) for more extensive user documentation.
X */
X
X#include <lib.h> /* this doesn't do anything */
X#include <search.h>
X
X/*
X * Type for doubly linked AVL tree.
X */
Xtypedef struct node_s {
X char *key; /* ptr to datum */
X struct node_s *parent; /* ptr to parent ancestor */
X struct node_s *sibls[2]; /* ptrs to L/R siblings */
X int balance; /* balance value (-1, 0 or +1) */
X} NODE;
X
X#define NIL_NODE ((NODE *) 0) /* ptr for empty (sub)trees */
X
Xtypedef int DIR; /* type for indexing siblings */
X#define L ((DIR) 0)
X#define R ((DIR) 1)
X
X#define LEFT sibls[L] /* left sibling pointer NODE field */
X#define RIGHT sibls[R] /* right sibling pointer NODE field */
X
X/*
X * Direction gives direction in which child NODE c is under parent NODE p.
X */
X#define direction(p, c) ((DIR) ((p)->RIGHT == (c)))
X
X/*
X * Cmp_dir gives direction corresponding with compare value v (R iff v > 0).
X */
X#define cmp_dir(v) ((DIR) ((v) > 0))
X
X/*
X * Siblingp yields ptr to left (d == L) or right (d == R) child of NODE n.
X */
X#define siblingp(n, d) ((n)->sibls + (d))
X
X/*
X * Parentp yields ptr to parent's ptr to NODE n, or root ptr r if n is 0.
X */
X#define parentp(r, n) ((n)->parent == NIL_NODE ? (r) : \
X siblingp((n)->parent, direction((n)->parent, (n))))
X
X/*
X * Dir_bal yields balance value corresponding to DIR d.
X */
X#define dir_bal(d) ((d) == L ? -1 : 1)
X
Xstatic NODE *balance();
Xstatic NODE *single_rotation();
Xstatic NODE *double_rotation();
Xstatic void do_walk();
Xextern char *malloc();
Xextern free();
X
X/*
X * Tsearch adds node key to tree rooted by *rootp, using compar for
X * comparing elements. It returns the pointer to the NODE in which
X * the (possibly already existing) key pointer resides.
X */
XNODE *tsearch(key, rootp, compar)
Xchar *key;
Xregister NODE **rootp;
Xint (*compar)();
X{
X register NODE *parent, *child;
X NODE *nnode;
X register DIR d;
X register int cmp;
X
X if (rootp == 0)
X return NIL_NODE;
X
X /* find place where key should go */
X parent = NIL_NODE;
X child = *rootp;
X while (child != NIL_NODE) {
X if ((cmp = compar(key, child->key)) == 0)
X return child;
X parent = child;
X child = *siblingp(child, cmp_dir(cmp));
X }
X
X /* create new node and set its parent's sibling pointer */
X if ((nnode = (NODE *) malloc(sizeof(NODE))) == NIL_NODE)
X return NIL_NODE;
X nnode->key = key;
X nnode->balance = 0;
X nnode->parent = parent;
X nnode->LEFT = nnode->RIGHT = NIL_NODE;
X if (parent == NIL_NODE) {
X *rootp = nnode;
X return nnode; /* just created tree */
X }
X *siblingp(parent, cmp_dir(cmp)) = nnode;
X child = nnode;
X
X /*
X * Back up until tree is balanced. This is achieved when either
X * the tree is balanced by rotation or a node's balance becomes 0.
X */
X do {
X d = direction(parent, child);
X if (parent->balance == dir_bal(d)) {
X (void) balance(rootp, parent, d);
X return nnode;
X }
X else if ((parent->balance += dir_bal(d)) == 0)
X return nnode;
X child = parent;
X parent = parent->parent;
X } while (parent != NIL_NODE);
X
X return nnode;
X}
X
X/*
X * Tdelete removes key from the tree rooted by *rootp, using compar
X * for comparing elements. It returns the pointer to the NODE that
X * was the parent of the NODE that contained the key pointer, 0 if
X * it did not exist.
X */
XNODE *tdelete (key, rootp, compar)
Xchar *key;
Xregister NODE **rootp;
Xint (*compar)();
X{
X register NODE *parent, *child;
X NODE *dnode, *dparent;
X register DIR d;
X register int cont_bal;
X register int cmp;
X
X if (rootp == 0)
X return NIL_NODE;
X
X /* find node to delete */
X child = *rootp;
X while (child != NIL_NODE) {
X if ((cmp = compar(key, child->key)) == 0)
X break;
X child = *siblingp(child, cmp_dir(cmp));
X }
X if (child == NIL_NODE)
X return NIL_NODE; /* key not in tree */
X
X /* the node was found; get its successor (if any) to replace it */
X dnode = child;
X dparent = dnode->parent;
X child = child->RIGHT;
X if (child == NIL_NODE) { /* no successor for key */
X if ((child = dnode->LEFT) != NIL_NODE)
X child->parent = dparent; /* set new parent */
X if (dparent == NIL_NODE) {
X free((char *) dnode);
X *rootp = child;
X return NIL_NODE; /* just deleted the root */
X }
X d = direction (dparent, dnode); /* for back up */
X *siblingp(dparent, d) = child; /* replace by left child */
X free ((char *) dnode);
X parent = dparent;
X }
X else { /* key's successor exists */
X while (child->LEFT != NIL_NODE)
X child = child->LEFT;
X parent = child->parent;
X d = direction(parent, child); /* for back up */
X *siblingp(parent, d) = child->RIGHT;
X if (child->RIGHT != NIL_NODE)
X child->RIGHT->parent = parent; /* set new parent */
X dnode->key = child->key; /* successor replaces key */
X free((char *) child);
X }
X
X /*
X * Back up until tree is balanced. This is achieved when either
X * the tree is balanced by rotation but not made shorter, or a
X * node's balance was 0 before deletion.
X */
X do {
X if (parent->balance == dir_bal(!d)) {
X cont_bal = ((*siblingp(parent, !d))->balance != 0);
X parent = balance(rootp, parent, !d);
X }
X else {
X cont_bal = (parent->balance != 0);
X parent->balance += dir_bal(!d);
X }
X child = parent;
X if ((parent = parent->parent) == NIL_NODE)
X return dparent; /* we reached the root */
X d = direction(parent, child);
X } while (cont_bal);
X
X return dparent;
X}
X
X/*
X * Balance the subtree rooted at sb that has become to heavy on side d.
X * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
X * the top of the entire tree.
X */
Xstatic NODE *balance(rootp, sb, d)
XNODE **rootp;
XNODE *sb;
XDIR d;
X{
X NODE *sb_next = *siblingp(sb, d);
X
X if (sb_next->balance == -dir_bal(d))
X return double_rotation(rootp, sb, sb_next, d);
X else
X return single_rotation(rootp, sb, sb_next, d);
X}
X
X/*
X * Balance the subtree rooted at sb that has become to heavy on side d
X * by single rotation of sb and sb_next.
X * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
X * the top of the entire tree.
X *
X * sb sb_next Single rotation: Adding x or
X * / \ / \ deleting under 3 caused
X * sb_next 3 1 sb rotation. Same holds for mirror
X * / \ | / \ image. Single_rotation returns
X * 1 2 ==> x 2 3 top of new balanced tree.
X * | | |
X * x y y
X */
Xstatic NODE *single_rotation(rootp, sb, sb_next, d)
XNODE **rootp;
Xregister NODE *sb, *sb_next;
Xregister DIR d;
X{
X *siblingp(sb, d) = *siblingp(sb_next, !d);
X *siblingp(sb_next, !d) = sb;
X
X sb->balance -= sb_next->balance;
X sb_next->balance = -sb->balance;
X
X *parentp(rootp, sb) = sb_next;
X sb_next->parent = sb->parent;
X sb->parent = sb_next;
X if (*siblingp(sb, d) != NIL_NODE)
X (*siblingp(sb, d))->parent = sb;
X
X return sb_next;
X}
X
X/*
X * Balance the subtree rooted at sb that has become to heavy on side d
X * by double rotation of sb and sb_next.
X * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
X * the top of the entire tree.
X *
X * sb sb_next2 Double rotation: Adding x or
X * / \ / \ x', or deleting under 4
X * sb_next \ sb_next sb caused rotation. Same holds
X * / \ \ / \ / \ for the mirror image.
X * 1 sb_next2 4 ==> 1 2 3 4 Double_rotation returns top
X * / \ | | of new balanced tree.
X * 2 3 x x'
X * | |
X * x x'
X */
Xstatic NODE *double_rotation(rootp, sb, sb_next, d)
XNODE **rootp;
Xregister NODE *sb, *sb_next;
Xregister DIR d;
X{
X register NODE *sb_next2 = *siblingp(sb_next, !d);
X
X *siblingp(sb_next, !d) = *siblingp(sb_next2, d);
X *siblingp(sb, d) = *siblingp(sb_next2, !d);
X *siblingp(sb_next2, d) = sb_next;
X *siblingp(sb_next2, !d) = sb;
X
X if (sb_next2->balance == sb_next->balance)
X sb_next->balance = -sb_next->balance;
X else
X sb_next->balance = 0;
X if (sb_next2->balance == sb->balance)
X sb->balance = -sb->balance;
X else
X sb->balance = 0;
X sb_next2->balance = 0;
X
X *parentp(rootp, sb) = sb_next2;
X sb_next2->parent = sb->parent;
X sb->parent = sb_next->parent = sb_next2;
X if (*siblingp(sb_next, !d) != NIL_NODE)
X (*siblingp(sb_next, !d))->parent = sb_next;
X if (*siblingp(sb, d) != NIL_NODE)
X (*siblingp(sb, d))->parent = sb;
X
X return sb_next2;
X}
X
X/*
X * Tfind searches node key in the tree rooted by *rootp, using compar for
X * comparing elements. It returns the pointer to the NODE in which
X * the key pointer resides, or 0 if key is not present.
X */
XNODE *tfind(key, rootp, compar)
Xchar *key;
XNODE **rootp;
Xint (*compar)();
X{
X register NODE *node;
X register int cmp;
X
X if (rootp == 0)
X return NIL_NODE;
X
X node = *rootp;
X while (node != NIL_NODE) {
X if ((cmp = compar(key, node->key)) == 0)
X return node;
X node = *siblingp(node, cmp_dir(cmp));
X }
X
X return NIL_NODE;
X}
X
X/*
X * Twalk walks the tree rooted by node, from top to bottom and left
X * to right, calling action with the NODE pointer, visit order, and
X * level in the tree (0 is root). Leafs are visited only once and
X * action is then called with `leaf' as the second parameter. For
X * nodes with children action is called three times with visit order
X * parameter `preorder' before, `postorder' in between, and `endorder'
X * after visiting the nodes children.
X */
Xvoid twalk(node, action)
Xregister NODE *node;
Xregister void (*action)();
X{
X register VISIT visit;
X register int level;
X
X if (node == 0 || action == 0)
X return;
X
X /* run down tree from top to bottom, left to right */
X visit = preorder;
X level = 0;
X while (node != NIL_NODE) {
X if (visit == preorder &&
X node->LEFT == NIL_NODE && node->RIGHT == NIL_NODE)
X visit = leaf; /* node turns out to be leaf */
X
X action(node, visit, level);
X
X switch (visit) {
X case preorder: /* before visiting left child */
X if (node->LEFT != NIL_NODE) {
X node = node->LEFT;
X level++;
X }
X else
X visit = postorder;
X break;
X case postorder: /* between visiting children */
X if (node->RIGHT != NIL_NODE) {
X node = node->RIGHT;
X visit = preorder;
X level++;
X }
X else
X visit = endorder;
X break;
X case endorder: /* after visiting children */
X case leaf: /* node has no children */
X if (node->parent != NIL_NODE)
X if (direction(node->parent, node) == L)
X visit = postorder;
X else
X visit = endorder;
X node = node->parent;
X level--;
X break;
X }
X }
X}
/
exit 0