[boost] Re: Boost library inclusion: generic tree containers?

From: Dan Rosen (dan.rosen_at_[hidden])
Date: 2005-02-27 17:11:01

Hi all,

This is my first posting to the Boost mailing list, so apologies in
advance for any gaffes. I wanted to jump into the fray a bit on the
tree container discussion with a couple little thoughts I had on the
topic.

There's been some excellent points made, reviewing the thread thus
far, about separating the concerns of tree structure from tree
iteration. I agree that it's very appropriate to consider designing
the fundamental structure and operations on a tree a distinct exercise
from designing how the data might be accessed, traversed or mutated by
standard algorithms. Talking first in terms of concepts such as
TreeContainer, which behave similarly to (or refine) the existing
standard library Container, seems like the right approach.

But there has also been some mention of more refined concepts such as
AVL Tree, Red-Black Tree, Splay Tree, BTree, etc. which have some
intrinsic algorithmic properties that distinguish them from what I'd
call a "basic" tree for lack of a better term. I believe that an AVL
tree, for example, is not actually a refinement of the basic tree
concept, because you can not treat an AVL tree polymorphically as a
basic tree. Inserting into one of these types of specialized trees,
for example, may invalidate iterators or violate other ordering
assumptions that are safe to make in a basic tree. I'm picturing a
particularly hairy instance where you have iterators marking a range
in, say, a red-black tree, and you call std::transform() on that range
in-place.

In other words, I think the only tree structures that are appropriate
to consider are the basic TreeContainer and strict refinements
thereof. Taking my own argument to an extreme, I'm not even entirely
convinced that binary or k-ary trees should be considered, since they
aren't strictly substitutable for basic trees... That aside, the real
idea I wanted to offer was this: If we want to provide the type of
behavior that one of these various self-balancing search trees, etc.
would offer (which I certainly think we should), it should take much
the same form as the heap algorithms present in the standard library
do today.

The operations push_heap(), pop_heap(), make_heap(), sort_heap() and
is_heap() operate with typical, characteristic cleverness on a
sequential range of RandomAccessIterators, imposing an ordering more
specific than that offered by the RandomAccessContainer storing the
data. Similarly, operations such as is_k_ary_tree(int), is_avl_tree(),
avl_balance(), etc. would serve to impose and maintain a useful, more
specific structure on top of TreeContainer, and would avoid having to
make a messy hierarchy of structural concepts.

So, this is all just to say: if we adopt the approach of further
separating the concern of specialized tree structures, then I believe
the exercise of formulating good concepts for basic tree structures
becomes simpler. Furthermore, I'm guessing that also makes things
easier when we do get to the step of worrying about standard iterators
and interoperability with standard library algorithms.

Hope this is a useful contribution! Cheers,
dr