home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2514 < prev    next >
Encoding:
Internet Message Format  |  1992-08-27  |  2.4 KB
  1. Path: sparky!uunet!europa.asd.contel.com!emory!ogicse!reed!orpheus
  2. From: orpheus@reed.edu (P. Hawthorne)
  3. Newsgroups: comp.programming
  4. Subject: Balanced Trees (Re: Why Are Red-Black Trees Obscure?)
  5. Message-ID: <1992Aug27.215924.24525@reed.edu>
  6. Date: 27 Aug 92 21:59:24 GMT
  7. References: <1992Aug26.183817.7371@reed.edu> <1992Aug27.115551.7958@daimi.aau.dk> <PSU.92Aug27104235@ptero.cs.duke.edu>
  8. Organization: Reed College, Portland, OR
  9. Lines: 40
  10.  
  11.  
  12.   psu@cs.duke.edu (Peter Su) laments:
  13. : All of the following are easier than AVL trees: splay trees, red-black
  14. : trees, skip-lists, randomized binary trees, etc. Why do people insist on
  15. : teaching AVL trees?
  16.  
  17.  (If I reveal some of my profound ignorance here, be gentle with me, huh?
  18. I've never had the pleasure of discussing data structures with others
  19. before, and some of my isolation may show through.)
  20.  
  21.   Maybe it's because AVL trees are always watching out for and correcting
  22. imbalance. The structures you mention are probabilistic solutions, not hard
  23. and fast guarantees. If you are particularly neurotic about computational
  24. cost and the cost of key compares outweighs the cost of path bookkeeping
  25. and tree rotations, I could see using AVL trees rather than the many "sure
  26. thing" alternatives. Plus, they're exotic Cold War souvenirs!
  27.  
  28.   I'll agree though, there isn't enough material available on those
  29. structures for the many circumstances in which they are the better
  30. alternatives. Ever tried to find an introduction to Fibonacci heaps or
  31. source for them that isn't in a mishmash of C++ and German?
  32.  
  33.   Is it a flaw in my implementation, or are top-down splay trees supposed
  34. to revert to a linked list when keys are inserted in order? Does a
  35. bottom-up splay operation solve that problem? I've always wondered.
  36.  
  37.   I'm partial to Patricia trees, from what I've read. Their balance and
  38. completeness look relatively good. I haven't seen any mention of a deletion
  39. operation on them however, and haven't ever really thought of them as
  40. dynamic structures that one could use where you might use other trees. Is
  41. that just a misconception of mine?
  42.  
  43.   Has anyone used frequency of node access data to bias the tree balancing
  44. rotation operations toward shorter paths?
  45.  
  46.   Given an ordered list of keys, what is the fastest way to tell whether or
  47. not they have a uniform probability distribution and just for good measure,
  48. where in the list it breaks down if at all?
  49.  
  50.   Theus (orpheus@reed.edu)
  51.