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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk