
Boost : 
From: David Abrahams (abrahams_at_[hidden])
Date: 20010106 22:38:33
 Original Message 
From: "John E. Potter" <jpotter_at_[hidden]>
> On Sat, 6 Jan 2001, David Abrahams wrote:
>
> > Funny you should mention rbtrees. My recent work on binary searches has
led
> > me to think about which rbtree representation we'd want.
>
> Why do you want an rbtree? 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 rbtree as opposed to avltree, splaytree,
> treap, unbalancedtree, ...?
Certain efficiency guarantees of a balanced binary tree are useful. I will
admit to not knowing enough to say that I want an rbtree 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 avltree.
I have used an rbtree 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 nonpublic 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 rbtree 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
> rbtree becomes an avltree by changing the policy functions. If
> they do nothing, you get an unbalanced tree. For rbtree, 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 rbtree; 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk