Re: [boost] RB Trees with extra information

From: Christoph Kögl (christoph_at_[hidden])
Date: 2003-09-15 16:48:21

Well,

most of the Standard Library implementations I know (HP, SGI, GCC,
Dinkumware, ...) use an rb-tree template for implementing
std::set/multiset/map/
multimap. Insert, search, and delete are of course O(log n), next and
prev (implemented
by the tree iterator's operator++/--) are amortized O(1) (could be
worst-case O(1)
but one would need node threading to do this), and min and max (easily
implemented using
begin / end) are worst-case O(1). Both std::set and std::map can of
course be used to
add "extra info" to the tree nodes (by suitably choosing the template
parameters).
Actually, implementing std::set etc. by rb-trees is not the only choice,
e.g. the Copenhagen
STL experimented with B-trees. Many height-balanced and weight-balanced
tree schemes
are candidates for implementing the standard associative containers.
This means that you cannot
be sure that a "randomly chosen" std::set is based on a rb-tree. But
from your posting
I gather that your main concern is the time complexities of various
operations. Or do you
need the special qualities of a rb-tree? If not: the C++ Standard
mandates almost exactly
the time complexities you are giving, for every conceivable
implementation of the standard
associative containers set/map etc.

Cheers

Am Die, 2003-09-16 um 09.42 schrieb ch00k:

> Hello,
> 
> Will it be useful to add such a data structure to boost library?
> 
> by addming extra info in tree node we could increase speed on some oerations
> 
> insert, search, delete are still O(log n)
> next, prev - O(1) min, max - O(1), (instead of O(log(n)),
> 
> It will be useful to design a template, that enables developer to add extra
> info to RB-Tree.- this can be useful to build such data structures as
> intervals tree, for example
> 
> For present moment I have ugly C rb-trees implementation and want to make a
> template on the base of it.
> 
> Maybe, such data structure is already included in boost or can be
> implemented by STL means?
> 
> Thanks
> 
> 
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost