Re: [boost] Container suggestions (was: Re: BOOST_NO_HASH)

From: John E. Potter (jpotter_at_[hidden])
Date: 2001-01-07 15:00:09

On Sat, 6 Jan 2001, David Abrahams wrote:

> ----- Original Message -----
> From: "John E. Potter" <jpotter_at_[hidden]>
> 
> > I have yet to see anyone want a balanced binary search tree.  Every
> > time that the question has come up on a news group, the poster wanted
> > either a set or map not the requested avl-tree.
> 
> I have used an rb-tree to implement an interval tree. To implement the
> operations of an interval tree, one needs not just iterator traversal, but
> operations like left_child(), right_child() and parent().

A little more looking done.  I hate trying to get concepts from code.
Do you have a reference for what an interval tree is, not how someone
implemented one.

> > Note that the
> > interface is that of a set/map not a tree.  Anyone wanting a tree
> > wants graph not a search structure.
> 
> It depends what you're building.

I still wonder.  A search structure has one dependance upon the data
in the form of a compare.  Otherwise, it modifies its structure in
ways unknown to the data and in ignorance of the data.  A graph is
all about structure with little involvement with the data.  Is an
interval tree either of these or is it some special structure of its
own not really related to either of these other than basic data
structures used to implement it?

> > Without a comparison function, you do not have a search structure.  It
> > is required for insert.
> 
> Only if you used the standard insert() interface. Think of an rb-tree like a
> vector. It has certain efficiency properties, etc., but is basically just a
> container. If you insert elements in sorted order, you have a structure on
> which you can do searches, given the right search algorithm and comparison
> function.

Sorry, an rb-tree is not like a vector.  Drop the rb.  Think of a tree
like a vector.  Given the proper interface, you can build many things.
I have yet to see anything that was as easy to use as the raw data
structure.  An rb-tree is optimized for binary search.  A linear
search will be much faster in a vector or list.  A non-search balanced
tree makes no sense to me.

> Actually, I'm talking about an additional /container/, not just additional
> functions. Probably the standard associative containers could be implemented
> in terms of this.

I think it would be a great reduction in usefullness.  Abstractions
which do one thing well are great.  Those which try to do all things
usually do none well and end up as shelf-ware.

> > > I think we also want some hooks into the rebalancing algorithms
> >
> > Generalize.  It is a binary search tree.  Rebalancing takes place
> > in insert, delete, search.
> 
> In search? Not in the balanced binary trees I've seen.

Depends upon what you call balance.  A splay-tree reorganizes after a
search that succeeds.

> Interval trees are a special case of balanced search tree which store ranges
> (i.e. a pair where first <= second). Nodes are sorted in order of the start
> of the range at that node (i.e. first). Each node in the tree is augmented
> with a label indicating the maximum value of the end of the range (second)
> for all nodes below it in the tree. Maintaining these maxima turns out to be
> cheap for rb-tree; I don't know about AVL. With this information you can
> quickly find, for example, all ranges which overlap a given range.

It is just as cheap for avl or any other binary search tree.  The only
thing that can be done to the structure of a binary search tree is a
rotation.

Aside.  Operator[] can be implemented on a balanced tree in O(logN).
Does anybody want it?

I'm having trouble seeing what you want.  It seems like you want
something as unsafe as array with some nice features.  Do you
have some use cases?  Some idea of the interface?  Invarients?
Are algorithms important?  What are the algorithms on this thing?

I'm really trying to understand.

John