Given a persistent red-black tree, I've been searching for an algorithm, approach, or equivalent data structure that allows me to efficiently merge two instances of the tree produced by divergent modification of a common ancestor.

For instance, tree instances v1 and v2 produced by mutating the common instance v0, are combined merge(v1, v2) to produce v3. The problem is slightly simplified by restricting the merge of trees to apply only when (1) the divergence is bound such that the length of a branch is at most 1, although many merges may occur between a branch point and it being merged. (2) v1 and v2 do not have merge conflicts. what i mean by this is that they do not both update the same keys, and changes in v2 take precedence.

I suspect that the best solution will involve augmenting the red-black tree with additional metadata such as node versioning information.

I've been navigating the literature on persistent data structures now for a while, and need some guidance to help restrict this search.


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.