[boost] More on augmented trees

Subject: [boost] More on augmented trees
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2012-11-27 12:52:49

Dear All,

A while ago I posted a question about augmented trees:

     http://thread.gmane.org/gmane.comp.lib.boost.devel/235004

There has also been other discussion recently in this thread:

     http://thread.gmane.org/gmane.comp.lib.boost.devel/236103

Unfortunately I have been manically bug-hunting for the last few weeks 
[*] and wasn't able to follow-up properly until now.  Here are my thoughts:

I'm aware of 3 applications for augmented trees:
- O(log N) indexing, insertion and deletion; "best of list and vector" 
(i.e. Countertree).
- Similar where the "value" of each node is variable, so one can 
accumulate over any range in O(log N) time (i.e. stl_ext_adv).
- Interval trees.

In the first two cases, the augmented value is the sum of the augmented 
values in the sub-nodes.  In the last case, it's the maximum of them.

Is anyone aware of any other applications that are not not very similar 
to those, e.g. where the augmentation is some other function of the sub-nodes?

Question: with only three (or two, if the first is considered a special 
case of the second) different kinds of augmentation, is it worthwhile 
to try to distil out a generic augmented tree?

Here is an interesting augmented tree implementation that attempts to 
be generic:

     http://kaba.hilvi.org/pastel/pastel/sys/redblacktree.htm

This seems to work by exposing the tree structure in the iterator (i.e. 
the iterator has parent(), left() and right() methods that return other 
iterators), and by requiring a Customization class that is called to 
updated augmented data in a node when its children change.

This looks to me to be a sensible approach, but I'm still not sure that 
it's better than just copy-and-paste when there are only two (or three) 
useful ways to apply it.

Thoughts anyone?

Regards,  Phil.

[*] My recent bug-hunting has really made me value the ease of working 
with open-source code like Boost.  What might take 5 minutes with grep 
instead takes weeks of back-and-forth with "technical support" (or 
reverse-engineering with a disassembler) - literally 3 orders of 
magnitude less efficient.