home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / programm / 2592 < prev    next >
Encoding:
Internet Message Format  |  1992-09-12  |  2.4 KB
  1. Path: sparky!uunet!sun-barr!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!cbnewsc!cbfsb!att-out!pacbell.com!network.ucsd.edu!sdcc12!sdcc13!sboswell
  2. From: sboswell@sdcc13.ucsd.edu (Xianity is stupid)
  3. Newsgroups: comp.programming
  4. Subject: Re: AVL trees - Re: Why Are Red-Black Trees Obscure?
  5. Message-ID: <37981@sdcc12.ucsd.edu>
  6. Date: 12 Sep 92 17:28:29 GMT
  7. References: <14298@goanna.cs.rmit.oz.au> <1992Sep1.142904.430@rz.uni-karlsruhe.de> <1992Sep2.022227.9117@reed.edu>
  8. Sender: news@sdcc12.ucsd.edu
  9. Organization: U.C. San Diego -- 1991 "Wannabe A Real College" finalist
  10. Lines: 33
  11. Nntp-Posting-Host: sdcc13.ucsd.edu
  12.  
  13. In article <1992Sep2.022227.9117@reed.edu> orpheus@reed.edu (P. Hawthorne) writes:
  14. >  I'll see your point and raise you a point. Deletion, when implementations
  15. >are given, seem to be efficient largely because of a particularly
  16. >simplistic representation, like heap allocation. One of the things I want
  17. >most from a given data structure is containment within a single memory
  18. >block (size proportional to the number of elements) which can grow, shrink
  19. >and move around when the structure isn't looking. Hence, my implementations
  20. >demand offsets rather than pointers, double links, interleaved binary and
  21. >interpolation search operations, and so on.
  22. >
  23. >  Deletion is the thorn in my side. I guess that's half the challenge! And
  24. >who knows, maybe it's not just my eccentricity, but all data structures
  25. >should have explicit "insert multiple elements" and "delete multiple
  26. >elements" operations!
  27.  
  28. I missed the beginning of this thread, so I don't know if y'all needed
  29. tree structures explicitly, or just a log(n) sorted structure, but I've
  30. had lots of success with skip lists.  The constant factors associated with
  31. each log(n) operation are significantly smaller than most other sorted
  32. log(n) structures, and things like dobule links, deletions, range insertions,
  33. range deletions, and search fingers are idiotically simple to code.
  34.  
  35. A long time ago I asked for a way to put a "next" pointer into an AVL tree
  36. so that I could address it like a linked list, and how to modify the insertion
  37. and deletion algorithms to update the "next" field automatically.  Someone
  38. suggested skip lists, and I've never looked back. :-)
  39.  
  40. If you want more info, look in mimsy.cs.umd.edu:/pub/skipLists -- there's a
  41. technical paper on it, plus a "skip list cookbook" and some data on how to
  42. write a parallel skip list.
  43.  
  44. Steve Boswell
  45. whatis@ucsd.edu
  46.