home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / lisp / mcl / 1201 < prev    next >
Encoding:
Internet Message Format  |  1992-08-12  |  1.3 KB
  1. Path: sparky!uunet!olivea!apple!cambridge.apple.com!straz@cambridge.apple.com
  2. From: markt@dgp.toronto.edu (Mark A. Tapia)
  3. Newsgroups: comp.lang.lisp.mcl
  4. Subject: Btree contribution to pub/MCL2/contrib
  5. Message-ID: <9208122241.AA07005@cambridge.apple.com>
  6. Date: 12 Aug 92 23:40:06 GMT
  7. Sender: info-mcl-request@cambridge.apple.com
  8. Lines: 25
  9. Approved: comp.lang.lisp.mcl@Cambridge.Apple.C0M
  10. Full-Name: Steve Strassmann
  11. Original-To: info-mcl
  12.  
  13.  
  14. Here is the working version of a package for manipulating btrees with
  15. added links (pointers) to the leftmost (min) and rightmost (max) nodes
  16. in the tree (or subtree). The package is based on algorithms by Knuth:
  17.  
  18. Description:
  19. Routines for manipulating binary (2,4) trees with user-defined full ordering.
  20.  
  21. Thanks,
  22.  
  23. mark
  24.  
  25.  
  26. ;;  The algorithms are based on the balanced tree algorithms in Knuth
  27. ;;  The Art of Computer Programming, Searching and Sorting Volume III
  28. ;;  sections 6.2.2 - 6.2.4 with modifications.
  29. ;; 
  30. ;;  The balanced trees are red-black trees augmented with points to
  31. ;;  allow fast reporting and updating. The representation is described in
  32. ;;  Cheng SW and Janardon R, "Efficient maintenance of the union intervals 
  33. ;;  on a line, with applications", Proceedings of the First Annual ACM-SIAM 
  34. ;;  Symposium on Discrete Algorithms, SIAM pp74-83.
  35.  
  36.  
  37. [Archived as cambridge.apple.com:/pub/MCL2/contrib/btree.sit.hqx]
  38.