Re: [boost] Segment Tree Implementation for GSoC 2014

Subject: Re: [boost] Segment Tree Implementation for GSoC 2014
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2014-03-07 06:28:14

Kevin Zuniga Garate wrote:
> On 5 March 2014 12:51, Phil Endecott <spam_from_boost_dev_at_[hidden]> wrote:
>> This is an augmented tree where the nodes store the min of the sub-nodes,
>> right?
>
> Yeah, kinda, all the real elements of the tree are in the leafs, and
> the internal nodes store the min of their sub-trees, but these
> internal nodes aren't real data of the tree. From what I have read
> about augmented trees the internal nodes have real elements apart from
> the additional data, through this may be just a minor thing.

Well, an "augmented tree" is just any kind of tree where there is any
kind of "augmentation"; I think that's orthogonal to whether the
internal nodes store data.  But that's just a matter of taxonomy.

> Also, a general question that I'm wondering about, would it be better
> to construct a segment tree that compiles on its own, or should it use
> other Boost libraries? (I am asking from what I've read in that second
> thread about ICL).

I don't think ICL is relevant, except that ICL could be re-implemented
using augmented trees (interval trees).  Of more interest is
Boost.Intrusive, which would could be extended to support augmented
trees as Jeff Snyder has proposed in one of the threads that I linked
to before.  Are you familiar with Boost.Intrusive?

(Do you have a motivating application?)

Regards,  Phil.