Boost logo

Boost :

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

> > What we really need is a balanced tree
> > container with upper_bound, lower_bound, find, and equal_range which
> > 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.


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


Boost list run by bdawes at, gregod at, cpdaniel at, john at