comparison: README.rb
README.rb
- changeset 65
- 58e382ae97cd
equal
deleted
inserted
replaced
| 64:f20d97d852ce | 65:58e382ae97cd |
|---|---|
| 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. |
