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

From: John E. Potter (jpotter_at_[hidden])
Date: 2001-01-06 17:52:09

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

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.  Note that the
interface is that of a set/map not a tree.  Anyone wanting a tree
wants graph not a search structure.

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

Without a comparison function, you do not have a search structure.  It
is required for insert.

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

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

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

John