home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2554 < prev    next >
Encoding:
Internet Message Format  |  1992-09-01  |  3.1 KB
  1. Path: sparky!uunet!ogicse!reed!orpheus
  2. From: orpheus@reed.edu (P. Hawthorne)
  3. Newsgroups: comp.programming
  4. Subject: Re: AVL trees - Re: Why Are Red-Black Trees Obscure?
  5. Message-ID: <1992Sep2.022227.9117@reed.edu>
  6. Date: 2 Sep 92 02:22:27 GMT
  7. Article-I.D.: reed.1992Sep2.022227.9117
  8. References: <1992Aug28.154713.3125@rz.uni-karlsruhe.de> <14298@goanna.cs.rmit.oz.au> <1992Sep1.142904.430@rz.uni-karlsruhe.de>
  9. Organization: Reed College, Portland, OR
  10. Lines: 53
  11.  
  12.  
  13.   ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
  14. : There is a curious thing about red-black trees, which is that algorithm
  15. : texts that describe them often leave out the deletion code.
  16.  
  17.   bevan@cs.man.ac.uk (Stephen J Bevan) writes:
  18. : I don't think this is perculiar to red-black trees. It seems that no
  19. : matter what the tree, many authors leave out deletion code. 
  20.  
  21.   I'll see your point and raise you a point. Deletion, when implementations
  22. are given, seem to be efficient largely because of a particularly
  23. simplistic representation, like heap allocation. One of the things I want
  24. most from a given data structure is containment within a single memory
  25. block (size proportional to the number of elements) which can grow, shrink
  26. and move around when the structure isn't looking. Hence, my implementations
  27. demand offsets rather than pointers, double links, interleaved binary and
  28. interpolation search operations, and so on.
  29.  
  30.   Deletion is the thorn in my side. I guess that's half the challenge! And
  31. who knows, maybe it's not just my eccentricity, but all data structures
  32. should have explicit "insert multiple elements" and "delete multiple
  33. elements" operations!
  34.  
  35.   I'll admit to being dumbstruck by wise data structures sometimes. That
  36. is, I am so impressed at the design, analysis and insight that has been put
  37. into a structure, I am totally humbled when I try to develop alternative
  38. representations, make up operations, or analyze the performance of my own
  39. experimental structures. For instance, I can imagine a deletion on a
  40. Patricia tree, but I seriously doubt whether I have ample understanding of
  41. the subtleties involved to propose an operation that, AFAIK, nobody else
  42. seems to have. 
  43.  
  44.   Or, say I think I've got a representation for graphs that is as new under
  45. the sun as it is well suited for particular problems. Who am I to suggest
  46. such a thing when Knuth has never mentioned it and it's not in BSD?
  47.  
  48.   Another good example is trying to reverse engineer the Fibonacci priority
  49. queue from LEDA, which I seem to remember is coded in C++ with commentary
  50. in German. (Why is there so much sexy code out there commented in German?
  51. I've taken a bunch of natural languages, but German just doesn't happen to
  52. be one of them, and it's the only one I have an immediate use for.)
  53.  
  54.  
  55.   S_TITZ@iravcl.ira.uka.de (Olaf Titz) writes:
  56. : Another example are Bayer trees, which should be presented to the
  57. : students as thorough as the AVL (or red-black, if you want it) trees just
  58. : because they are the tree structure that suits best to a block-structured
  59. : storage device.
  60.  
  61.   Never heard of them before, but I like what I hear so far. Are these
  62. significantly different from the B-tree?
  63.  
  64.   Theus (orpheus@reed.edu)
  65.