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

From: David Abrahams (abrahams_at_[hidden])
Date: 2001-01-06 22:38:33

----- Original Message -----
From: "John E. Potter" <jpotter_at_[hidden]>

> On Sat, 6 Jan 2001, David Abrahams wrote:
>
> > Funny you should mention rb-trees. My recent work on binary searches has
led
> > me to think about which rb-tree representation we'd want.
>
> Why do you want an rb-tree?  This is really two questions.  Why do you
> want a binary search tree?  What would you do with it?  Why do you
> want that tree to be an rb-tree as opposed to avl-tree, splay-tree,
> treap, unbalanced-tree, ...?

Certain efficiency guarantees of a balanced binary tree are useful. I will
admit to not knowing enough to say that I want an rb-tree as opposed to an
AVL tree.

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

> 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've begun to
> > think that the approach used in most standard library implementations is
> > probably not the right one to expose to users; the comparison function
> > shouldn't be part of the definition.

Just to be clear, I meant the non-public interface that underlies most
set<>, map<>, etc. implementations is not the right one to expose to users.

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

> > What we really need is a balanced tree
> > container with upper_bound, lower_bound, find, and equal_range which
accept
> > comparison function parameters.
>
> These are in addition to the normal ones which use the comp function
> which defines the search structure.  I understand that you have
> examples where a comp function other than the defining one can be
> used because it is compatible with the specific data.  Murphy should
> have a blast with this.  :)  No worse than operator[], maybe.  Anyway,
> it would be an addition not a replacement.

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

>  Where is known, how is a policy.  An
> rb-tree becomes an avl-tree by changing the policy functions.  If
> they do nothing, you get an unbalanced tree.  For rb-tree, there
> is also the possibility of rebalancing during or after insertion.

Good!

> > so that one can implement an interval tree
>
> Showing my ignorance here.  A quick search seems to indicate that
> an interval tree is useful only for a set of discrete values.  The
> nodes contain intervals rather than points.  Deleting a point
> within an interval will split the node and adding a point may
> combine two adjacent nodes.  Seems like a special case optimization
> not a general search structure.

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.

These are useful in graphics applications. They also happen to be useful in
computer music, which is where they first came up for me.

-Dave