Btree contribution to pub/MCL2/contrib

["Mark A. Tapia" <markt@dgp.toronto.edu> (by way of Steve Strassmann <straz@cambridge.apple.com>)]

Here is the working version of a package for manipulating btrees with
added links (pointers) to the leftmost (min) and rightmost (max) nodes
in the tree (or subtree). The package is based on algorithms by Knuth:

Description:
Routines for manipulating binary (2,4) trees with user-defined full ordering.

Thanks,

mark


;;  The algorithms are based on the balanced tree algorithms in Knuth
;;  The Art of Computer Programming, Searching and Sorting Volume III
;;  sections 6.2.2 - 6.2.4 with modifications.
;; 
;;  The balanced trees are red-black trees augmented with points to
;;  allow fast reporting and updating. The representation is described in
;;  Cheng SW and Janardon R, "Efficient maintenance of the union intervals 
;;  on a line, with applications", Proceedings of the First Annual ACM-SIAM 
;;  Symposium on Discrete Algorithms, SIAM pp74-83.


[Archived as cambridge.apple.com:/pub/MCL2/contrib/btree.sit.hqx]