Re: [boost] Augmented trees

Subject: Re: [boost] Augmented trees
From: Chapman, Alec (archapm_at_[hidden])
Date: 2012-10-11 19:18:25

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

This implementation was written to allow easy augmentation, and it's worked well for me.
www.stroustrup.com/tree-appendix.pdf

It is described at onlinelibrary.wiley.com/doi/10.1002/spe.564/pdf.  I don't know about the license.

Alec