Re: [boost] Re: any interest in a 'tree' container?

From: Herve Bronnimann (hbr_at_[hidden])
Date: 2002-10-10 12:02:59

On Thu, Oct 10, 2002 at 04:09:32PM +0100, Craig Henderson wrote:
> Tree structures would be a welcome addition, IMO. Do you have (or plan to
> have) any "special case" tree structures, such as generic binary tree, AVL
> tree or red/black trees. Binary Trees are a very useful data structure that
> is lacking in the STL.

I have all these variants (more) in a STL-like library which I can
boostify. This was mentioned in a discussion involving Dietmar Kuehl's
priority queues structure a while ago on this list.

If anyone's interested in R/B trees, Randomized trees, Splay Trees, Treaps,
augmented or not, compact nodes (bools packed into pointers, for
instance), all in the STL style and ready to provide a set or a map
through an adapter which I provide, ask me.

What I'd expect from a generic tree library:

  - a unified interface by concepts (BinaryTree, NAryTree, SearchTree,
    RedBlackTree perhaps, etc.) Concepts are important because they lay
    the ground for the interface with generic algorithms

  - iterators for traversal, not as member functions (although a begin()
    is certainly useful, there are many ways to traverse a tree)

  - generic algorithms, with interface decoupled from the tree class
    (much like algorithms/containers in the STL interact by iterators).
    I think the right interface is algorithmic visitors, much like in
    the BGL. For example, we'd want rotations that work on any tree
    that provides left/right.

  - policies, or traits (do you maintain the tree size? is it possible
    to add fields/derive from node/add property, and have the generic
    algorithm also maintain that property?)

It's really challenging to come up with the right mixture. I've tried,
and am nowhere near. I'll take a close look at the proposal though, as
I'm sure there will be more good ideas in there.
best,
-- 
Herve'