Boost logo

Boost :

From: Jeff Mirwaisi (jeff_mirwaisi_at_[hidden])
Date: 2005-02-23 08:42:12

Since the interest level in a generic tree library
seems to be high, below is a link to an incomplete
tree library/type constructor framework I have been
tinkering with.

It, perhaps foolishly, tries to present the building
blocks for the construction of a large set of
different tree types with different balancing and
book-keeping requirements.

Keep in mind it is not complete, some of the balancing
schemes need to be checked, it has no workarounds for
broken compilers and for the most part only
basic/range insert have been implemented (erase is
just a placeholder)

There are a number of meta programming techniques used
in the library, including execute_if which i brought
up in a separate thread, the techniques link via the
above link describes a few of them (template parameter
mapping, execute_if etc).

The above is a start at defining some of the terms and
concepts used in type constructors/builders/computers,
once meaningful terms are agreed upon the tree
documentation will change to use the new terms.

Stroustrup on a generic binary tree library:
Matt Austern, Bjarne Stroustrup, Mikkel Thorup, and
John Wilkinson: Untangling the Balancing and Searching
of Balanced Binary Search Trees. Software - Practice &
Experience. Vol 33, Issue13. October 2003
(google only has a link to the example code in this

Stroustrup on binary tree iterators:

Feedback is appreciated,
-Jeff Mirwaisi

Boost list run by bdawes at, gregod at, cpdaniel at, john at