Re: [boost] Augmented trees

Subject: Re: [boost] Augmented trees
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2012-10-12 06:40:15

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

I don't know if this will work for you, but in Boost.Geometry we have 
two implementations of the R-tree. Currently none of them is in the 
release branch but you can play with it. The R-tree is a spatial index 
based on B-tree, if you use 1 dimensional data you should get what you 
want. Implemented queries allows to retrieve values in various ways, 
e.g. values in some range or nearest to some other value.

If you want to check it out, here is the address:
http://svn.boost.org/svn/boost/sandbox-branches/geometry/index/

Regards,
Adam