moss@BRL-VLD.ARPA (09/18/84)
From: "Gary S. Moss (AMXBR-VLD-V)" <moss@BRL-VLD.ARPA>
While waiting and waiting for our System V license to arrive, I wrote an
implementation of tsearch(3). It has three functions described here briefly.
char *tsearch( (char *) key, (char **) rootp, compar )
int (*compar)();
Binary tree search, returns pointer into a tree indicating where
a datum may be found. If the datum does not occur it is inserted.
It only returns NULL if 'rootp' is NULL on entry or there is no
space to create a node. You can't tell if the node was there already
or not, Yucko!
I soon decided that I didn't like the behavior of the tsearch() function as
documented (if it doesn't find a datum, it inserts it) and changed it to only
report whether or not the datum exists and added a function called tinsert()
which would behave as the original tsearch() did. They later fixed this in
System VR2 by adding a function tfind(). This change was more upward compat-
able than mine, and I probably should change the names in the library, but
since we now have our license, my library will probably go away.
char *tdelete( (char *) key, (char **) rootp, compar )
int (*compar)();
Returns a pointer to the parent of the deleted node, or NULL if the
node is not found or 'rootp' is NULL on entry.
void twalk( (char *) root, action )
void (*action)();
Traverses a binary tree and envokes 'action' at each visit to a node,
with 3 arguments; the node address, an enum data type describing
which visit {preorder, postorder, endorder, leaf} and the level in
the tree of the node. There choice of terms here was strange, so I
changed 'endorder' to 'inorder', but then Knuth originally got that
wrong too, and that's where these algorithms were taken (Bell's not
mine).
If you don't have System V and want a public domain copy, send me a note
and I'll mail you my sources and manual page.
-- Moss.jwp@sdchema.UUCP (John Pierce) (10/01/84)
If the original requestor will contact me (sorry, I've lost the original
article), I have code that may help (it is for B+ trees). It was passed
to me by a friend a couple of years ago. Unfortunately, I have never found
the time to write the application that was to use it, so I can't guarantee
that it works, but the alogrithm looks to be correct.
John Pierce, Chemistry, UC San Diego
{decvax,sdcsvax}!sdchema!jwp