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

$$ node.key = x $$

If no such node exists, return null.

Algorithm

Compare the target with the current node. Move left for smaller keys and right for larger keys.

scapegoat_search(root, x):
    node = root

    while node != null:
        if x == node.key:
            return node
        else if x < node.key:
            node = node.left
        else:
            node = node.right

    return null

Example

        10
       /  \
      5    18
     / \   /
    2   7 14

Search for 14:

step	node	comparison	move
1	10	14 > 10	right
2	18	14 < 18	left
3	14	equal	return

Correctness

A scapegoat tree preserves the binary search tree ordering invariant. For any node, all keys in the left subtree are smaller and all keys in the right subtree are larger.

The search algorithm always chooses the only subtree that can contain the target. If it returns a node, that node has the target key. If it reaches null, the target is absent from the unique possible search path.

Complexity

A scapegoat tree maintains logarithmic height using a balance parameter $\alpha$ where

$$ \frac{1}{2} < \alpha < 1 $$

The height is bounded by

$$ O(\log n) $$

Therefore search time is:

case	time
worst case, after maintained balance	$O(\log n)$

Space complexity:

version	space
iterative	$O(1)$
recursive	$O(\log n)$

When to Use

Scapegoat trees are useful when you want logarithmic search without storing per-node balance metadata. Each node only needs key and child pointers.

They are appropriate when:

• node memory should stay small
• search must have logarithmic worst case height after updates
• occasional subtree rebuilding is acceptable

Compared to AVL and red black trees, scapegoat trees move balancing work into less frequent rebuild operations.

Implementation

def scapegoat_search(root, x):
    node = root

    while node is not None:
        if x == node.key:
            return node
        elif x < node.key:
            node = node.left
        else:
            node = node.right

    return None

func ScapegoatSearch(root *Node, x int) *Node {
    node := root

    for node != nil {
        if x == node.Key {
            return node
        } else if x < node.Key {
            node = node.Left
        } else {
            node = node.Right
        }
    }

    return nil
}