# Sublinear search of variables in a term

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(1) or 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.

• 1. What are your thoughts? What research have you done? What approaches have you considered? We expect you to do a significant amount of research before asking, and to show us in the question what you've done. See cs.stackexchange.com/help/how-to-ask. 2. Can you edit your question to specify more clearly what you mean by "leaf search"? I can't understand your sentence. (Also, what does it have to do with leaves?) – D.W. Aug 30 '15 at 21:49
• @D.W. I've skipped research part because I hadn't achieved anything interesting on this task. Fixed. – polkovnikov.ph Aug 30 '15 at 22:11
• 1. I still can't understand what the sentence about "leaf search" means. What is "a subtree with a root in that node"? How does the root argument affect what search() should return? The description "It should return..." makes it sound like the desired return value depends only on label but not on root. 2. Have you looked at balanced search trees, hash tables, etc.? Each of them should support lookup, deletion, and insertion in $O(\lg n)$ time, which seems like it might be enough to implement your operations (depending on what you mean by leaf search). – D.W. Aug 31 '15 at 4:33