home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2555 < prev    next >
Encoding:
Text File  |  1992-09-01  |  2.7 KB  |  59 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!mcsun!Germany.EU.net!ubrinf!ubrinf!holly
  3. From: holly@wowbagger.pc-labor.uni-bremen.de (Holger Duerer)
  4. Subject: Re: Balanced Trees (Re: Why Are Red-Black Trees Obscure?)
  5. In-Reply-To: orpheus@reed.edu's message of 27 Aug 92 21:59:24 GMT
  6. Message-ID: <HOLLY.92Sep1181058@wowbagger.pc-labor.uni-bremen.de>
  7. Sender: news@informatik.uni-bremen.de (NEWS Service)
  8. Nntp-Posting-Host: wowbagger.pclabor.uni-bremen.de
  9. Organization: PC-Labor der Universitaet Bremen
  10. References: <1992Aug26.183817.7371@reed.edu> <1992Aug27.115551.7958@daimi.aau.dk>
  11.     <PSU.92Aug27104235@ptero.cs.duke.edu> <1992Aug27.215924.24525@reed.edu>
  12. Date: Tue, 1 Sep 1992 17:10:58 GMT
  13. Lines: 44
  14.  
  15. >>>>> On 27 Aug 92 21:59:24 GMT, orpheus@reed.edu (P. Hawthorne) said:
  16.  
  17.  
  18. >>   psu@cs.duke.edu (Peter Su) laments:
  19. >> : All of the following are easier than AVL trees: splay trees, red-black
  20. >> : trees, skip-lists, randomized binary trees, etc. Why do people insist on
  21. >> : teaching AVL trees?
  22.  
  23. >>  (If I reveal some of my profound ignorance here, be gentle with me, huh?
  24. >> I've never had the pleasure of discussing data structures with others
  25. >> before, and some of my isolation may show through.)
  26.  
  27. >>   Maybe it's because AVL trees are always watching out for and correcting
  28. >> imbalance. The structures you mention are probabilistic solutions, not hard
  29. >> and fast guarantees. If you are particularly neurotic about computational
  30. >> cost and the cost of key compares outweighs the cost of path bookkeeping
  31. >> and tree rotations, I could see using AVL trees rather than the many "sure
  32. >> thing" alternatives. Plus, they're exotic Cold War souvenirs!
  33.  
  34. I myself am not very knowledgable about this stuff but red-black trees
  35. DO give guarantees.  They are just not as strict as for AVL trees.  So
  36. red-black trees are at most twice as bad as AVL.  You are right that
  37. this may be of importance in some case.  However these should be far
  38. to rare to warrant the attention given to AVLs.
  39.  
  40. >>   I'll agree though, there isn't enough material available on those
  41. >> structures for the many circumstances in which they are the better
  42. >> alternatives. Ever tried to find an introduction to Fibonacci heaps or
  43. >> source for them that isn't in a mishmash of C++ and German?
  44.  
  45. I believe there is a chapter about Fib heaps in Cormen, Rivest,
  46. Leiserson: "Algorthms".  I haven't read that chapter but liked all the
  47. ones I DID read.  It's a nice book.
  48.  
  49. >> [stuff deleted]
  50.  
  51. >>   Theus (orpheus@reed.edu)
  52.  
  53.     Holger
  54. --
  55. ----------------------------------------------------------------------
  56. Holger D"urer                           <holly@pc-labor.uni-bremen.de>
  57.  "Infinity is a notion best contemplated within four 
  58.   walls with sheets tucked snugly around one's feet" -- Oliver Wendell Jones
  59.