Generic C code for red-black trees. Copyright (C) 2000 James S. Plank This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA --------------------------------------------------------------------------- Jim Plank plank@cs.utk.edu http://web.eecs.utk.edu/~jplank Department of Computer Science University of Tennessee 107 Ayres Hall Knoxville, TN 37996 615-974-4397 $Revision: 1.2 $ --------------------------------------------------------------------------- Rb.c and rb.h are files for doing general red-black trees. The directory ansi contains ansi-standard c code for rb-trees (there are some gross pointer casts there but don't worry about them. They work). The directory non-ansi contains straight c code for rb-trees. The ansi version can also be used by c++ (it has been tested). Rb.h contains the typedef for red-black tree structures. Basically, red-black trees are balanced trees whose external nodes are sorted by a key, and connected in a linked list. The following is how you use rb.c and rb.h: Include rb.h in your source. Make_rb() returns the head of a red-black tree. It serves two functions: Its p.root pointer points to the root of the red-black tree. Its c.list.flink and c.list.blink pointers point to the first and last external nodes of the tree. When the tree is empty, all these pointers point to itself. The external nodes can be traversed in sorted order with their c.list.flink and c.list.blink pointers. The macros rb_first, rb_last, rb_next, rb_prev, and rb_traverse can be used to traverse external node lists. External nodes hold two pieces of information: the key and the value (in k.key and v.val, respectively). The key can be a character string, an integer, or a general pointer. Val is typed as a character pointer, but can be any pointer. If the key is a character string, then one can insert it, and a value into a tree with rb_insert(). If it is an integer, then rb_inserti() should be used. If it is a general pointer, then rb_insertg() must be used, with a comparison function passed as the fourth argument. This function takes two keys as arguments, and returns a negative value, positive value, or 0, depending on whether the first key is less than, greater than or equal to the second. Thus, one could use rb_insertg(t, s, v, strcmp) to insert the value v with a character string s into the tree t. Rb_find_key(t, k) returns the external node in t whose value is equal k or whose value is the smallest value greater than k. (Here, k is a string). If there is no value greater than or equal to k, then t is returned. Rb_find_ikey(t,k) works when k is an integer, and Rb_find_gkey(t,k,cmp) works for general pointers. Rb_find_key_n(t, k, n) is the same as rb_find_key, except that it returns whether or not k was found in n (n is an int *). Rb_find_ikey_n and Rb_find_gkey_n are the analogous routines for integer and general keys. Rb_insert_b(e, k, v) makes a new external node with key k and val v, and inserts it before the external node e. If e is the head of a tree, then the new node is inserted at the end of the external node list. If this insertion violates sorted order, no error is flagged. It is assumed that the user knows what he/she is doing. Rb_insert_a(e,k,v) inserts the new node after e (if e = t, it inserts the new node at the beginning of the list). Rb_insert() is therefore really a combination of Rb_find_key() and Rb_insert_b(). Rb_delete_node(e) deletes the external node e from a tree (and thus from the linked list of external nodes). The node is free'd as well, so don't retain pointers to it. 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. Other routines: Rb_print_tree() will grossly print out a red-black tree with string keys. Rb_iprint_tree() will do the same with trees with integer keys. Rb_nblack(e) will report the number of black nodes on the path from external node e to the root. The path length is less than twice this value. Rb_plength(e) reports the length of the path from e to the root. 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.