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