[boost] Re: RB Trees with extra information

From: Igor Maximchuk (sp4sp_at_[hidden])
Date: 2003-09-16 01:35:01

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

I need the abiity to add extra information in tree node. This is not typical
"node data".
It must be maintained during balancing of a tree. For example, I might want
to have value
K for each tree node, that means that the left subtree of the node has
exactly K nodes
this is main tecnique of building order-statistic tree. To maintain this
information, I need to
add almost some code to balancing, insert, delete routines (this code is
need to be
added exactly in these routines due to time to saving time complexity). I
thought it would be useful
to make such a tempate, that gives ability of automatization of this
process.

something like this, maybe
tmplate<calss data_type, class extra_info_type, class maintaner_functor>
class _rb_tree
...

Best regards,
ch00k