Re: [boost] More on augmented trees

Subject: Re: [boost] More on augmented trees
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2012-11-28 03:56:11

On Wed, Nov 28, 2012 at 3:52 AM, Phil Endecott <
spam_from_boost_dev_at_[hidden]> wrote:

> Dear All,
>
> A while ago I posted a question about augmented trees:
>
>     http://thread.gmane.org/gmane.**comp.lib.boost.devel/235004
>

>
> There has also been other discussion recently in this thread:
>
>     http://thread.gmane.org/gmane.**comp.lib.boost.devel/236103
>
>
> Unfortunately I have been manically bug-hunting for the last few weeks [*]
> and wasn't able to follow-up properly until now.  Here are my thoughts:
>
>
> I'm aware of 3 applications for augmented trees:
> - O(log N) indexing, insertion and deletion; "best of list and vector"
> (i.e. Countertree).
> - Similar where the "value" of each node is variable, so one can
> accumulate over any range in O(log N) time (i.e. stl_ext_adv).
> - Interval trees.
>
>
This list does not include R-trees suggested by Adam Wulkiewicz. In the
general case this is the best choice, since these trees work with both two
and one dimensional extension rectangles. Only if you are sure that one
dimensional extension intervals are sufficient for the problem you can use
one of the listed data structures or containers. However, if some time
later the problem becomes two dimensional the solution can not be fixed by
adding another container for y-coordinate. This approach is not optimal.
For the best performance you will need to re-implement the solution using
R-trees.

> Here is an interesting augmented tree implementation that attempts to be
> generic:
>
>     http://kaba.hilvi.org/pastel/**pastel/sys/redblacktree.htm
>
>
> This seems to work by exposing the tree structure in the iterator (i.e.
> the iterator has parent(), left() and right() methods that return other
> iterators), and by requiring a Customization class that is called to
> updated augmented data in a node when its children change.
>
>
These trees provide facilities and extensions of STL containers similar to
Countertree and augmented B+ trees. They do not offer efficient logarithmic
time join and split operations. Note also, that the author says that this
project is mostly for educational purposes.

Regards,
Vadim Stadnik