Re: [Boost-users] [Intrusive] augmenting red black trees

Subject: Re: [Boost-users] [Intrusive] augmenting red black trees
From: Alan M. Carroll (amc_at_[hidden])
Date: 2009-03-30 10:51:06

At 07:16 AM 3/29/2009, Ion Gaztañaga wrote:
>George Slavov wrote:
>>I want to know if it’s possible to augment the red black tree structure offered by Boost.Intrusive. Specifically I need each node to contain some information like the max value of the subtree rooted at that node and this information should be updated during insert/delete operations. This is a fairly common thing, allowing you to do logarithmic queries that are specific to certain trees, so I’m surprised I couldn’t find anything about it in the Boost.Intrusive docs.
>
>Sorry, but that's not currently possible and unfortunately, due to time constraints and other boost projects I would like to implement (move library with independent move-aware containers, some allocator experiments...), I'm afraid it won't be on the top of my to do list.
>
>I have no much experience with data structures so any help, code or a link to documentation would be great, just to see how much effort would be needed to implement this feature.

I did exactly this sort of thing a few years back, basically writing my own version of an intrusive std::map so that I could track the minimum and maximum values of subtrees for each node.  My experience was that you needed only one virtual method which I named "structure_fixup". It is a method on the node type and is called on a node *after* it has been rotated during a tree rebalance. The container guarantees that it is called after any tree modification

* For every node with a geometry change

* After all geometry changes for that node have occurred

* In ascending order, i.e. for any two nodes A and B, if A is a descendant of B in the post fixup geometry, then the method is called on A before B.

Maintaining subtree properties is easy at this point, since for each node it can pick up "final" sub-sub-tree properties from its direct children and update itself.  Its parent will do the same as needed. The overhead is log(N), which is the theoretical minimum.

Because inserts and deletes both cause structure fixups / rotations, there's no need to distinguish the cases.  The support code shows up in three places in my implementation

* In the node rotate code, called on the rotated nodes (new child first, then new parent).

* In the insert and delete methods. For these cases most of the calls are handled by the rotate method, but after all rotations have finished, the call must be rippled up the tree to the root. This is naturally done in the standard red-black algorithm after the final required rotation has been performed and is implemented by simply walking the parent pointers to the root, calling structure_fixup on the way.

You could require either a specifically named method and use BOOST_HAS_METHOD to detect it, or pass it as a pointer to method template parameter. Note that the method doesn't have to be virtual if there's no polymorphism in the tree (and sometimes not even then, depending on the node implementation).