libtu/README.rb

   1 Generic C code for red-black trees.
   2 Copyright (C) 2000 James S. Plank
   3
   4 This library is free software; you can redistribute it and/or
   5 modify it under the terms of the GNU Lesser General Public
   6 License as published by the Free Software Foundation; either
   7 version 2.1 of the License, or (at your option) any later version.
   8
   9 This library is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12 Lesser General Public License for more details.
  13
  14 You should have received a copy of the GNU Lesser General Public
  15 License along with this library; if not, write to the Free Software
  16 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17
  18 ---------------------------------------------------------------------------
  19 Jim Plank
  20 plank@cs.utk.edu
  21 http://www.cs.utk.edu/~plank
  22
  23 Department of Computer Science
  24 University of Tennessee
  25 107 Ayres Hall
  26 Knoxville, TN 37996
  27
  28 615-974-4397
  29 $Revision: 1.2 $
  30 ---------------------------------------------------------------------------
  31
  32 Rb.c and rb.h are files for doing general red-black trees.
  33
  34 The directory ansi contains ansi-standard c code for rb-trees (there
  35 are some gross pointer casts there but don't worry about them.  They
  36 work).  The directory non-ansi contains straight c code for rb-trees.
  37 The ansi version can also be used by c++ (it has been tested).
  38
  39 Rb.h contains the typedef for red-black tree structures.  Basically,
  40 red-black trees are balanced trees whose external nodes are sorted
  41 by a key, and connected in a linked list.  The following is how
  42 you use rb.c and rb.h:
  43
  44 Include rb.h in your source.
  45
  46 Make_rb() returns the head of a red-black tree.  It serves two functions:
  47 Its p.root pointer points to the root of the red-black tree.  Its
  48 c.list.flink and c.list.blink pointers point to the first and last
  49 external nodes of the tree.  When the tree is empty, all these pointers
  50 point to itself.
  51
  52 The external nodes can be traversed in sorted order with their
  53 c.list.flink and c.list.blink pointers.  The macros rb_first, rb_last,
  54 rb_next, rb_prev, and rb_traverse can be used to traverse external node lists.
  55
  56 External nodes hold two pieces of information: the key and the value
  57 (in k.key and v.val, respectively).   The key can be a character
  58 string, an integer, or a general pointer.  Val is typed as a character
  59 pointer, but can be any pointer.  If the key is a character string,
  60 then one can insert it, and a value into a tree with rb_insert().  If
  61 it is an integer, then rb_inserti() should be used.  If it is a general
  62 pointer, then rb_insertg() must be used, with a comparison function
  63 passed as the fourth argument.  This function takes two keys as arguments,
  64 and returns a negative value, positive value, or 0, depending on whether
  65 the first key is less than, greater than or equal to the second.  Thus,
  66 one could use rb_insertg(t, s, v, strcmp) to insert the value v with
  67 a character string s into the tree t.
  68
  69 Rb_find_key(t, k) returns the external node in t whose value is equal
  70 k or whose value is the smallest value greater than k.  (Here, k is
  71 a string).  If there is no value greater than or equal to k, then
  72 t is returned.  Rb_find_ikey(t,k) works when k is an integer, and
  73 Rb_find_gkey(t,k,cmp) works for general pointers.
  74
  75 Rb_find_key_n(t, k, n) is the same as rb_find_key, except that it
  76 returns whether or not k was found in n (n is an int *).  Rb_find_ikey_n
  77 and Rb_find_gkey_n are the analogous routines for integer and general
  78 keys.
  79
  80 Rb_insert_b(e, k, v) makes a new external node with key k and val v, and
  81 inserts it before the external node e.  If e is the head of a tree,
  82 then the new node is inserted at the end of the external node list.
  83 If this insertion violates sorted order, no error is flagged.  It is
  84 assumed that the user knows what he/she is doing.  Rb_insert_a(e,k,v)
  85 inserts the new node after e (if e = t, it inserts the new node at the
  86 beginning of the list).
  87
  88 Rb_insert() is therefore really a combination of Rb_find_key() and
  89 Rb_insert_b().
  90
  91 Rb_delete_node(e) deletes the external node e from a tree (and thus from
  92 the linked list of external nodes).  The node is free'd as well, so
  93 don't retain pointers to it.
  94
  95 Red-black trees are spiffy because find_key, insert, and delete are all
  96 done in log(n) time.  Thus, they can be freely used instead of hash-tables,
  97 with the benifit of having the elements in sorted order at all times, and
  98 with the guarantee of operations being in log(n) time.
  99
 100 Other routines:
 101
 102 Rb_print_tree() will grossly print out a red-black tree with string keys.
 103 Rb_iprint_tree() will do the same with trees with integer keys.
 104 Rb_nblack(e) will report the number of black nodes on the path from external
 105   node e to the root.  The path length is less than twice this value.
 106 Rb_plength(e) reports the length of the path from e to the root.
 107
 108
 109 You can find a general description of red-black trees in any basic algorithms
 110 text.  E.g. ``Introduction to Algorithms'', by Cormen, Leiserson and Rivest
 111 (McGraw Hill).  An excellent and complete description of red-black trees
 112 can also be found in Chapter 1 of Heather Booth's PhD disseratation:
 113 ``Some Fast Algorithms on Graphs and Trees'', Princeton University, 1990.