Scapegoat Tree Search
Scapegoat Tree Search Scapegoat tree search uses the ordinary binary search tree search rule. The tree keeps logarithmic height by rebuilding unbalanced subtrees after updates, rather than storing balance information in each node. The search procedure does not rebuild anything. It benefits from the height guarantee maintained by insertions and deletions. Problem Given a scapegoat tree with root root and target key x , find a node such that $$...