home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2519 < prev    next >
Encoding:
Text File  |  1992-08-29  |  1.8 KB  |  45 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!cs.utexas.edu!sdd.hp.com!ux1.cso.uiuc.edu!m.cs.uiuc.edu!gillies
  3. From: gillies@m.cs.uiuc.edu (Don Gillies)
  4. Subject: Re: Balanced Trees (Re: Why Are Red-Black Trees Obscure?)
  5. Message-ID: <1992Aug28.075102.4026@m.cs.uiuc.edu>
  6. Organization: University of Illinois, Dept. of Comp. Sci., Urbana, IL
  7. References: <1992Aug26.183817.7371@reed.edu> <1992Aug27.115551.7958@daimi.aau.dk> <PSU.92Aug27104235@ptero.cs.duke.edu> <1992Aug27.215924.24525@reed.edu>
  8. Date: Fri, 28 Aug 1992 07:51:02 GMT
  9. Lines: 34
  10.  
  11. orpheus@reed.edu (P. Hawthorne) writes:
  12.  
  13. >  Is it a flaw in my implementation, or are top-down splay trees supposed
  14. >to revert to a linked list when keys are inserted in order? Does a
  15. >bottom-up splay operation solve that problem? I've always wondered.
  16.  
  17. No, there are many ways to get a linked list when inserting keys into
  18. a splay tree.  The key is, if you continue to use splay(), the linked
  19. list quickly becomes a near-balanced-binary-tree.  There are obscure
  20. access patterns to get the structure back to a linked list, but then
  21. from that organization, most access patterns will tend to rebalance
  22. the tree rather quickly.
  23.  
  24. >  I'm partial to Patricia trees, from what I've read. Their balance and
  25. >completeness look relatively good. I haven't seen any mention of a deletion
  26. >operation on them
  27.  
  28. What are patricia trees?  Please respond via email.
  29.  
  30. >  Given an ordered list of keys, what is the fastest way to tell whether or
  31. >not they have a uniform probability distribution and just for good measure,
  32. >where in the list it breaks down if at all?
  33.  
  34. compute the entropy (see an information-theory textbook).  For
  35. sequentially degeneracy (a repetitive sequence of keys), if they are
  36. 8-bit or 16-bit keys, you might try running them through "compress".
  37. If they compress well, the key ordering is probably degenerate.
  38.  
  39.  
  40.  
  41. -- 
  42.  
  43.  
  44.  
  45.