home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2516 < prev    next >
Encoding:
Text File  |  1992-08-27  |  1.6 KB  |  40 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!elroy.jpl.nasa.gov!ames!pasteur!cory.Berkeley.EDU!johnm
  3. From: johnm@cory.Berkeley.EDU (John D. Mitchell)
  4. Subject: Re: Balanced Trees (Re: Why Are Red-Black Trees Obscure?)
  5. Message-ID: <1992Aug28.005849.28502@pasteur.Berkeley.EDU>
  6. Sender: nntp@pasteur.Berkeley.EDU (NNTP Poster)
  7. Nntp-Posting-Host: cory
  8. Organization: University of California, at Berkeley
  9. References: <1992Aug27.115551.7958@daimi.aau.dk> <PSU.92Aug27104235@ptero.cs.duke.edu> <1992Aug27.215924.24525@reed.edu>
  10. Date: Fri, 28 Aug 1992 00:58:49 GMT
  11. Lines: 27
  12.  
  13. In article <1992Aug27.215924.24525@reed.edu> orpheus@reed.edu (P. Hawthorne) writes:
  14. >  psu@cs.duke.edu (Peter Su) laments:
  15. >: All of the following are easier than AVL trees: splay trees, red-black
  16. >: trees, skip-lists, randomized binary trees, etc. Why do people insist on
  17. >: teaching AVL trees?
  18. [...]
  19. >  Maybe it's because AVL trees are always watching out for and correcting
  20. >imbalance. The structures you mention are probabilistic solutions, not hard
  21. >and fast guarantees. If you are particularly neurotic about computational
  22. >cost and the cost of key compares outweighs the cost of path bookkeeping
  23. >and tree rotations, I could see using AVL trees rather than the many "sure
  24. >thing" alternatives. Plus, they're exotic Cold War souvenirs!
  25.  
  26. Nope.  AVL, splay and red-black trees are *not* probabilistic.  Skip-lists
  27. are probabilistic.
  28.  
  29. [...]
  30. >  Has anyone used frequency of node access data to bias the tree balancing
  31. >rotation operations toward shorter paths?
  32. [...]
  33.  
  34. That's what 'splaying' is for.
  35.  
  36. John D. Mitchell
  37. johnm@cory.Berkeley.EDU
  38.  
  39.  
  40.