[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Btree contribution to pub/MCL2/contrib
- To: info-mcl
- Subject: Btree contribution to pub/MCL2/contrib
- From: "Mark A. Tapia" <email@example.com> (by way of Steve Strassmann <firstname.lastname@example.org>)
- Date: Wed, 12 Aug 1992 18:40:06 -0500
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]