Say I have a finite $n$-ary tree where each node contains state. For the sake of argument, let's say a key-value store. If we are interested in the aggregation of some key(s) at some node, then we fold over the subtree at that node with the appropriate function. However, this doesn't scale well.

An option would be to always fold whenever a node is inserted/removed, keeping a cache of each node's subtree aggregation and updating that. However, if a node were inserted deep in the structure, the resulting cascade up to the root would still be quite expensive.

Is there a known data-structure that makes this aggregation cheap? Specifically, it needs to have cheap access and insert to nodes, their state and their aggregated subtree; while being happy to sacrifice space. (Ideally the aggregation should be precise, but if an estimate is possible, then that will suffice.)

The best I've come up with is keeping the tree with a projection of its nodes onto a list, where each subtree occupies a contiguous region thereof, then folding over that to get the aggregate date. However, a fold over a flat bit of memory isn't going to be much better than the same thing over a subtree (i.e., it's still $O(n)$, modulo pointer lookups)... I'm just wondering if there's some clever trick.

  • $\begingroup$ Why not use a balanced bst? $\endgroup$ – Kaveh Oct 14 '15 at 17:35
  • $\begingroup$ It might be worth mentioning that the tree I have in mind is a filesystem, so the physical structure needs to be preserved in some meaningful way. $\endgroup$ – Xophmeister Oct 14 '15 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.