Red-Black Tree Code Home Page

Generic red-black tree code

James S. Plank, University of Tennessee.

There is a newer and better version of the red-black tree code in the Libfdr library, which also contains the fields code and doubly-linked list code. I recommend you port that and use it instead of this code, because it is safer and easier to use.

$Revision: 1.2 $

Brief Description

Rb.c and rb.h are files for doing general red-black trees.

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:

Source code

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.