|
Matthew H. Austern, Bjarne Stroustrup, Mikkel Thorup, John Wilkinson. Untangling the balancing and searching of balanced binary search trees. Softw., Pract. Exper. 33(13): 1273-1298 (2003)
I really hate Software - Practice and Experience since they don't allow authors to provide their papers online (or so it seems). Still, I think this paper may interest several LtU readers, so I'll make an exception and mention it here even though it is not publically available.
The authors show how to decouple the search and balancing stategies so they can be expressed independently of each other, communicating only by basic operations such as rotations.
The paper presents a C++ framework that makes heavy use of templates, and is quite efficient.
Aside from being an interesting exercise in libary design, and being a nice example of templates, the authors use a few interesting programming techniques related to C++ templates that are worth knowing about.
An appendix containing the source code is available online.
Posted to Software-Eng by Ehud Lamm on 5/19/04; 8:23:53 AM
|
Untangling the balancing and searching of balanced binary search trees
