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

From: Beman Dawes (bdawes_at_[hidden])
Date: 2005-02-27 21:46:57

At 05:11 PM 2/27/2005, Dan Rosen wrote:

 >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.

A Skip List is an interesting case. It is both list-like and tree-like. I 
always thought it should be called a Skip Tree. It supports forward 
iteration but not reverse iteration. It has lower per node memory 
overhead  than competitors, yet performs quickly on searches and has very, 
very fast inserts.

But a Skip List would be like your AVL tree example; it would be stretching 
it to try to call it a refinement of a basic tree. Yet it is simple and has 
enough advantages that for many uses it would be nice to view a Skip List 
as an example of a generic tree. But more in a general family way that 
strictly polymorphically.

--Beman