Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk