Merging and Unmerging Sets of Trees Efficiently

Background

Given multiple trees, I'd like to merge all of the them and be able to efficiently unmerge arbitrary trees in the set. For example, here are some JSON trees:

Tree 1:

{
a: {
b: 1
},
c: [{}],
d: 3
}


Tree 2:

{
a: {
z: 1
},
c: [
{
x: 1
},
{
x: 2
}
],
d: 4
}


merge(t1, t2) would yield:

{
a: {
b: 1
z: 1
},
c: [
{
x: 1
},
{
x: 2
}
],
d: 4
}


Note the overwrite of primitives (d).

Problem

I'd like to be able to merge some order set of trees like the above (the order is important because of the overwriting of primitives) AND be able to efficiently unmerge one of the trees.

Mathematically, I want two functions $$merge$$ and $$unmerge$$ such that the following holds true:

$$unmerge(merge(t_1,...,t_n,...,t_p), t_n) = merge(t_1,...,t_{n-1},t_{n+1},...,t_p)$$

where $$p,n \in Z^+$$ and $$n \leq p$$.

Simple solutions like "delete all of the nodes on $$t_n$$ from the merged tree" obviously doesn't work in many cases.

More robust solutions like creating immutable copies of the interim trees might would has you could take the cached tree $$merge(t_1,...,t_{n-1})$$ and then merge in the subsequent trees $$t_{n+1},...,t_p$$. However, in the worst-case ($$n=1$$) this is equivalent to just remerging the entire set; ideally, there would be some less computationally complex solution.

Would love any advice or pointers for further research. Thanks!

One solution

Make trees immutable, using path copying. Give each tree a name. Whenever you create a new tree T3 by merging two trees T1,T2, remember in T3 that it was created by merger of T1,T2 (i.e., include pointers to T1,T2 as part of the auxiliary information in the root node of T3). Also keep track in the auxiliary information for each tree all of the original trees it was transitively created from.

Now, when you want to unmerge a tree, you can look at the auxiliary information to work out what you need to do. When you call unmerge(T, U), look at the auxiliary information for T to find the two trees T1,T2 it was merged from; if U was used to create T1, then

unmerge(T, U) = merge(unmerge(T1, U), T2)

so you can proceed recursively. Similarly, if U was used to create T2, then

unmerge(T, U) = merge(T1, unmerge(T2, U))

The running time of this will be proportional to the maximum "depth" of the merge operations, times the time to merge two trees.

A more efficient solution

With more sophisticated data structures, you can speed up the unmerge operation so it performs at most $$O(\log n)$$ merges.

Call a tree "atomic" if it wasn't created by a merge/unmerge. The auxiliary information for each tree T will be an ordered list of the atomic trees T1,..,Tk it was created from, so that T = merge(T1,..,Tk). This list will be stored as a persistent self-balancing binary tree with k leaves, one per atomic tree in the list, ordered in the same way they are in the list. Each node in that self-balancing tree corresponds to an interval Ti,..,Tj of the list (namely, Ti,..,Tj are the set of leaves under that node); add metadata so that node points to the tree produced by merge(Ti,..,Tj). Also, as auxiliary information for tree T, we'll have a map that given the name of a tree U lets you look up where in the list T1,..,Tk that U appears; this can be done with a second persistent self-balancing binary tree with k leaves, ordered by lexicographic order on the names of the atomic trees.

The merge(T1, T2) operation merges the two trees, and constructs its auxiliary information by concatenating the associated lists. Those operations on the self-balancing binary trees can be done in $$O(\log n)$$ time, so this adds little overhead to the merge operation.

Finally, unmerge(T, U) can be implement as follows. First, we look up where U appears in the associated list for T; suppose U is the ith item in the list T1,..,Tk, i.e., U = Ti. Then we need to compute merge(T1,..,Ti-1,Ti+1,..,Tk). It turns out that this can be done in $$O(\log n)$$ merges. Why? Well, we look at the path from Ti to the root in the self-balancing tree for T; if we take all of the siblings of the nodes on that path, and merge their associated trees in the correct order, we get merge(T1,..,Ti-1,Ti+1,..,Tk). Since it is a self-balancing tree, its depth is at most $$O(\log n)$$, so there are at most $$O(\log n)$$ nodes along that path, so we need to do at most $$O(\log n)$$ merge operations. Thus, unmerge(T, U) is about $$O(\log n)$$ times as slow as a merge operation.

A final note: there's nothing special here about the fact that the T1,..,Tk are trees. They could have been any value, such as simple integers or anything else. So, you might find it easier to think about this with simple values first. On the other hand, this also means that my algorithm isn't taking into account the fact that the T1,..,Tk are trees; it's possible that data structures that take that into account might be able to be even more efficient.

• This was great. Thank you for taking the time to explain your solution. I am going to explore this algorithm for performance metrics in my use case and I will report back. As an aside, in my ideal world, there would be an optimization for trees that would allow unmerge to have the same time complexity as merge. In my application, I have an average of 4 trees (s.d. 2) and so the clever dependency graph solution introduces overhead (path copying, balanced, etc.) that might offset the 2-3x time complexity gains. Only testing will tell though! – Jclangst Apr 24 at 19:22