home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2548 < prev    next >
Encoding:
Text File  |  1992-09-01  |  2.3 KB  |  49 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!usc!sol.ctr.columbia.edu!ira.uka.de!rz.uni-karlsruhe.de!usenet
  3. From: S_TITZ@iravcl.ira.uka.de (Olaf Titz)
  4. Subject: Re: AVL trees - Re: Why Are Red-Black Trees Obscure?
  5. In-Reply-To: ok@goanna.cs.rmit.oz.au's message of 1 Sep 92 10: 39:13 GMT
  6. Message-ID: <1992Sep1.142904.430@rz.uni-karlsruhe.de>
  7. Sender: usenet@rz.uni-karlsruhe.de (USENET News System)
  8. Organization: Fachschaft Informatik, Uni Karlsruhe
  9. References: <1992Aug26.183817.7371@reed.edu> <1992Aug27.115551.7958@daimi.aau.dk> <1992Aug28.154713.3125@rz.uni-karlsruhe.de> <14298@goanna.cs.rmit.oz.au>
  10. Date: Tue, 1 Sep 1992 14:29:04 GMT
  11. X-News-Reader: VMS NEWS 1.23
  12. Lines: 35
  13.  
  14. In <14298@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au writes:
  15.  
  16. >  Thank you.  You just convinced me to switch to red-black trees or splay
  17. >  trees as soon as I understand the relative merits of each.  Quicksort is
  18. >  _not_ good for teaching because students learn "use Quicksort", which is
  19. >  not a lesson I hope any competent teacher would _want_ them to learn.
  20. >  (Merge sort is easier to explain, easier to code correctly, easier to
  21. >  analyse, and significantly faster.)
  22.  
  23. Depends on *how* it's taught. If students learn a number of algorithms
  24. to do the same thing, they can judge which one to use if a real
  25. application is under construction. IMO Heapsort is often neglected
  26. because of its being 'hard to understand' but it has efficiency
  27. advantages over Quicksort, most notably it can *cleanly* be
  28. implemented without recursion.
  29.  
  30. Another example are Bayer trees, which should be presented to the
  31. students as thorough as the AVL (or red-black, if you want it) trees
  32. just because they are the tree structure that suits best to a
  33. block-structured storage device.
  34.  
  35. >  There is a curious thing about red-black trees, which is that algorithm
  36. >  texts that describe them often leave out the deletion code.
  37.  
  38. And Bayer tree descriptions leave out deletion either, as do AVL tree
  39. descriptions, for the reason that it were 'too complicated' :-(
  40.  
  41.  
  42. MfG,
  43.         Olaf
  44. -- 
  45. Olaf Titz - comp.sc.student - Univ of Karlsruhe - s_titz@iravcl.ira.uka.de -
  46. uknf@dkauni2.bitnet - praetorius@irc - +49-721-60439 - did i forget something?
  47. The only use I can find for vi is editing the emacs sources
  48.  while porting them to a new machine. - Larry Campbell
  49.