Re: [boost] Augmented trees

Subject: Re: [boost] Augmented trees
From: Beman Dawes (bdawes_at_[hidden])
Date: 2012-10-11 21:05:49

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.

I've done some experimentation with in-memory B+ trees, and they have
different performance characteristics than red-black trees. They can
be 10 times or more faster for search operations than red-black trees,
particularly on architectures with very high speed hardware caches
that are large in relation to the size of the tree. They can also use
less space than an equivalent red-black tree. I'm not sure what would
happen to the performance in an app dominated by inserts and deletes
rather than searches, but a red-black tree is likely better for that
scenario.

The B-tree, read-black tree, UB-tree, and many of their variants were
all invented by Rudolf Bayer. Each is superior for some usage
scenarios and applications, and inferior for others.

--Beman