James S. Plank, University of Tennessee.
$Revision: 1.2 $
Rb.h contains the typedef for red-black tree structures. Basically, red-black trees are balanced binary trees whose external nodes are sorted by a key, and connected in a linked list.
Red-black trees are spiffy because find_key, insert, and delete are all done in log(n) time. Thus, they can be freely used instead of hash-tables, with the benifit of having the elements in sorted order at all times, and with the guarantee of operations being in log(n) time.
The directory ansi contains ansi-standard c code for rb-trees. The directory non-ansi contains straight c code for rb-trees. The ansi version can also be used by c++ (it has been tested).
You can find a general description of red-black trees in any basic algorithms text. E.g. ``Introduction to Algorithms'', by Cormen, Leiserson and Rivest (McGraw Hill). An excellent and complete description of red-black trees can also be found in Chapter 1 of Heather Booth's PhD disseratation: ``Some Fast Algorithms on Graphs and Trees'', Princeton University, 1990.
However, you don't need to know anything about the mechanics of the data structure in order to use it. Just treat is as a doubly-linked list that remains sorted. If you'd like some more help with using these libraries, please see the following lecture notes from our algorithms course here:
Compressed Shar file (18859 bytes)
Uncompressed Shar file (48604 bytes)
In case you can't deal with shar files, here are the individual files. Read the README for more info.