Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk