This was originally part of a larger collection of data structures for C programmers, but I lost interest in the other structures (linked lists and stacks didn't seem nearly as usefull to have as a prepackaged library as this search tree). Several years after I stopped work on the project, of which this code was a part, I had a coworker ask me about self balancing trees, so I pulled the searchtree code out and dusted it off for him to look over. You can download the tarball here .
There really isn't all that much to the search tree code, just searchtree.h and searchtree.c , as well as a little regression test program (I am working on a new regression test that can also serve as a simple benchmark, treebench.c, but it is far from complete.
I have completed the full delete code and it works perfectly: it even fixed a minor bug that was caused by the lazy delete code. The lazy delete code is still in the source, but is no longer called. I'll get rid of it eventually, but I have other things to do right now.