Re: [boost] Augmented trees

Subject: Re: [boost] Augmented trees
From: Greg Rubino (bibil.thaysose_at_[hidden])
Date: 2012-10-11 15:42:06

On Thu, Oct 11, 2012 at 10:23 AM, Phil Endecott <
spam_from_boost_dev_at_[hidden]> wrote:

> Dear Experts,
>
> I find myself in need of an augmented tree.  My problem is something like
> [but not exactly] this:
>
> - Say I have a line of text, i.e. a sequence of characters, in a
> variable-width font; each character stores its width in pixels.
>
> - I need to efficiently insert and remove characters.
>
> - I need to efficiently find the range of characters that spans a given
> range of pixels.
>
> It seems to me that an augmented tree lets me do all of those operations
> in log(N) time - and no other data structure offers the same performance.
>
> I'm aware of two augmented trees that have been proposed here.  Francisco
> Jose Tapia has proposed "Countertree", but this only stores the count of
> elements not the sum of a property of the elements (i.e. the widths in my
> example).  Vadim Stadnik has proposed stl_ext_adv, which is a
> doubly-augmented B+ tree.  Has anyone looked at Vadim's code since it was
> proposed last year?  I have a couple of concerns about Vadim's proposal:
>
> 1. It uses B+ trees, and in the discussion it was suggested that these are
> inferior to red-black trees in some way.
>
> 2. In order to get the property to be accumulated (i.e. the widths in my
> case) it requires that arithmetic can be done on the stored type itself;
> this is fine for e.g. a sequence of ints, but if the stored type is a
> struct it is necessary to add various "unnatural" operator overloads.  I
> think I would prefer it to have some sort of user-supplied accessor to get
> the property to be accumulated.
>
> Is there any other work that I've overlooked?
>
> Is there a "friendly" red-black tree implementation somewhere that could
> be augmented relatively easily?
>
>
You could use the implementation from the GCC STL!  Actually, I think a lot
of STL implementations use RB-trees for ordered associative containers.  I
bet there's a better choice out there, but I'm not really an expert.

-Greg