Is there an implementation of a binary search tree annotated with sub-tree size

Question

I have been researching the tree data structure described at this link (near the bottom):

http://sigpipe.macromates.com/2009/08/13/maintaining-a-layout/

It is mentioned that this data structure could be a finger tree. However, after more research around finger trees, I've found that this lacks the "fingers" that makes finger trees finger trees. Instead, it seems this is just an annotated binary tree (annotated with subtree size).

Do you know of an existing implementation (in any language) of this data-structure that I could use as a reference for my own implementation (though, preferably not an implementation in a functional programming language)?

Or, what would be the most optimal way of retrofitting the subtree size annotations into an existing tree data-structure?

Thanks!

Answer 1

Simon Tatham's Counted B-Trees are similar. if the node count is replaced with a width of buffer like in tweak, these provide operations like ropes.

in fact from reading that the page you reference i see that it was being used like a piece table or line table for an editor

in the paper, Positional Delta Trees to reconcile updates with read-optimized data storage, the authors present a tree which behavior in regard to the invariants it holds between the nodes in the tree bares a striking resemblance to xanadu's enfilades to which the Counted B-tree is also similar.

Answer 2

I've got a project on github called Boost.Intrusive Annotated Trees that aims to provide generic support for annotations like subtree count in Boost.Intrusive. Subtree count was my original use case for it.

Currently it requires C++11 variadic templates and only supports the rbtree, but it works, and I hope to remove both of those restrictions in time Update: Now builds with C++03. Still only supports rbtree.

When used with a subtree count annotation it's similar to what jordan describes in the answer above - it calculates (left+right+1) at each node. The implementation is quite different - it works with any node and/or value traits; the annotation updates are integrated into the rbtree algorithms instead, which keeps the number of recalculations done minimal.

Answer 3

I've implemented something similar based on a question I asked the other day. I added annotations to the boost::intrusive::rbtree/avltree nodes to calculate the size of each subtree (foreach node count = node->left->count + node->right->count + 1). I perform this update on insertion/deletetion/rebalance of the tree by using the boost value_traits hook for set_parent, set_left, and set_right. Pretty much, as stated in the site you referenced, after each node update, update the current node's size and then traverse up the tree until you hit the root, updating each node's size as you go.

The problem comes when you want to insert into the tree at a specific position. Pretty much the moment you do this, you'll invalidate the key-ordering invariant for the tree structure. This means you won't be able to perform efficient O(log n) lookups by key. But, if you wanted that, you probably wouldn't be needed the size annotations anyway.