[boost] Re: RB Trees with extra information

From: David Abrahams (dave_at_[hidden])
Date: 2003-09-15 16:13:11

"ch00k" <sp4sp_at_[hidden]> writes:

> Hello,
>
> Will it be useful to add such a data structure to boost library?

Yes, I once needed it.  I made one myself by modifying the STLPort
rb_tree.  It's proprietary, though :(.

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

I would strongly suggest modifying an existing generic C++ rb_tree
implementation, like the one in STLPort.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com