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