home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / cplus / 16112 < prev    next >
Encoding:
Text File  |  1992-11-11  |  2.1 KB  |  56 lines
  1. Newsgroups: comp.lang.c++
  2. Path: sparky!uunet!ukma!darwin.sura.net!aplcen.apl.jhu.edu!ddsdx2.jhuapl.edu!dlc
  3. From: dlc@ddsdx2.jhuapl.edu (Dave Collard x7468)
  4. Subject: Re: Wanted: Red-Black Trees
  5. Message-ID: <1992Nov11.182456.5788@aplcen.apl.jhu.edu>
  6. Sender: news@aplcen.apl.jhu.edu (USENET News System)
  7. Organization: Johns Hopkins University
  8. References: <1992Nov11.103156.1@happy.colorado.edu>
  9. Distribution: usa
  10. Date: Wed, 11 Nov 92 18:24:56 GMT
  11. Lines: 43
  12.  
  13. In <1992Nov11.103156.1@happy.colorado.edu> srheintze@happy.colorado.edu writes:
  14.  
  15. >Does anyone have source to an implementation of Red-Black trees?
  16. Yes, but I cannot give you my version.  A 'C' version was posted 
  17. to comp.sources.misc back in February by James Plank at
  18. jsp@Princeton.EDU
  19.  
  20. I have that and can mail it to you if you want.  I have never run or
  21. built or tested it.  It is in shar format. 
  22.  
  23. csh> ls -l rbtree
  24. -rw-r--r--   1 dlc      general     30193 Nov 11 13:16 rbtree
  25.  
  26. >I was going to type one in from a textbook (anyone know of a text book that has 
  27. >Red-Black tree?) but if anyone has a softcopy it would save me the trouble.
  28.  
  29. Two references:  _Algorithms_ Robert Sedgewick 1983 Addison-Wesley
  30.                  _Introduction to Algorithms_ by Cormen, Leiserson, Rivest 
  31.                    1990 Massachusetts Institute of Technology
  32.  
  33. Cormen has a much better (read: easier to understand) description of red-black
  34. trees.  However, the Sedgewick algorithm is more efficient in storage because
  35. the parent of each node is not stored.  I have also tested both algorithms and
  36. the Sedgewick algorithm keeps the height of the tree slightly less than the
  37. Cormen algorithm.  I never figured out exactly why.
  38.  
  39. The basic properties of a red-black tree are:
  40.  
  41.   1) Nodes are colored red or black
  42.   2) Null leaves are considered black
  43.   3) Children of red nodes are black
  44.   4) Every simple path from a node to a descendant
  45.      leaf contains the same number of black nodes
  46.  
  47.                  
  48. >Does anyone understand the performance difference between red-black trees and
  49. >AVL trees?  Does anyone have  reference on this topic?
  50.  
  51. See above.
  52.  
  53. --Thor
  54. collard@capsrv.jhuapl.edu
  55. dlc@ddsdx2.jhuapl.edu
  56.