[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Btree contribution to pub/MCL2/contrib

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:

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



;;  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]