Suppose we have a forest. The leaves have labels. Let's suppose all labels are natural numbers. We would like the forest to support two operations:
rebasing that replaces a leaf on first tree with the second tree.
void rebase(node leaf, node root)
leaf search by the (possibly internal) node of any tree and label we'd like to find in a subtree with a root in that node. It should return either a reference to the leaf that has that label or a failure. In case there are two leaves with the same label, it should return any of them.
optional<node> search(node root, int label)
Which data structure could help implementing both of these operations in sublinear (i.e.
O(log n)) time? Is there a popular name for this problem?
Currently I'm using an
O(N) search that visits via DFS every node of the subtree and compares labels to the given one.
Pretty obvious solution would be to have a double-linked list of leaves for each tree in a forest. Leaves should be listed in a left-to-right traversal order. Every node would store two pointers that mark beginning and the end of the part of that DLL that contains all leaves of the subtree with the root in that node. In such a way
rebase could insert one DLL into the middle of the other, and
search would need to traverse only leaves of the subtree. But that doesn't decrease complexity of
search from linear, because it requires
O(N) leaf visits and label comparisons.
Another solution is to have a persistent binary search tree on each node of the original tree. Rebasing would require
O(h n) operations to rebuild search trees on all the nodes from the insertion point to the root, and
search would be
O(log n). But this approach seems overcomplicated and requires garbage collector to implement properly.