Scapegoat trees: rebuild a deep insertion subtree

Last updated: 4 Oct 20269 min read

tutorial

A scapegoat tree is a binary search tree that occasionally rebuilds an unbalanced subtree rather than rotating after every insertion. This insertion-only model uses alpha equal to two thirds. It records the search path, increments ancestor subtree sizes, and compares insertion depth with the logarithmic threshold. If the path is too deep, it walks upward to the first ancestor whose path child exceeds two thirds of that ancestor's size. It flattens that subtree in sorted order, rebuilds a balanced tree, and reconnects the original grandparent. Search itself does not mutate the tree. Duplicate IDs are rejected without changing sizes; deletion and the global rebuild rule for shrinkage are intentionally absent.

Operational case

Case IDs 19, 29, 47, 61, 83, 103, 127, 149, and 173 arrive in ascending order. A plain BST would become a chain, but this index rebuilds a subtree when a new path exceeds the depth allowance. The final in-order sequence still matches sorted IDs and an existing lookup for 83 is true. The rebuild counter makes the expensive structural operation visible. If the new subtree is reattached on the wrong side of its grandparent, search order breaks even though every node is still present. If sizes are not recomputed within the rebuilt subtree, a later insertion can choose the wrong scapegoat.

Working Python program

import math


class CaseNode:
    def __init__(self, case_id):
        self.case_id = case_id
        self.left = self.right = None
        self.size = 1


def size(node):
    return node.size if node else 0


class ScapegoatCaseIndex:
    def __init__(self):
        self.root = None
        self.count = 0
        self.rebuilds = 0

    def contains(self, case_id):
        cursor = self.root
        while cursor:
            if case_id == cursor.case_id:
                return True
            cursor = cursor.left if case_id < cursor.case_id else cursor.right
        return False

    def insert(self, case_id):
        if self.root is None:
            self.root = CaseNode(case_id)
            self.count = 1
            return True
        path = []
        cursor = self.root
        while cursor:
            path.append(cursor)
            if case_id == cursor.case_id:
                return False
            next_node = cursor.left if case_id < cursor.case_id else cursor.right
            if next_node is None:
                child = CaseNode(case_id)
                if case_id < cursor.case_id:
                    cursor.left = child
                else:
                    cursor.right = child
                path.append(child)
                break
            cursor = next_node
        self.count += 1
        for ancestor in path[:-1]:
            ancestor.size += 1
        depth_limit = math.floor(math.log(self.count, 1.5))
        if len(path) - 1 <= depth_limit:
            return True
        for position in range(len(path) - 2, -1, -1):
            parent, child = path[position], path[position + 1]
            if 3 * child.size <= 2 * parent.size:
                continue
            nodes = []

            def flatten(node):
                if node is None:
                    return
                flatten(node.left)
                nodes.append(node)
                flatten(node.right)

            def balance(low, high):
                if low >= high:
                    return None
                middle = (low + high) // 2
                node = nodes[middle]
                node.left = balance(low, middle)
                node.right = balance(middle + 1, high)
                node.size = 1 + size(node.left) + size(node.right)
                return node

            flatten(parent)
            rebuilt = balance(0, len(nodes))
            if position == 0:
                self.root = rebuilt
            else:
                grandparent = path[position - 1]
                if grandparent.left is parent:
                    grandparent.left = rebuilt
                else:
                    grandparent.right = rebuilt
            self.rebuilds += 1
            break
        return True

    def ordered_ids(self):
        result = []

        def walk(node):
            if node:
                walk(node.left)
                result.append(node.case_id)
                walk(node.right)

        walk(self.root)
        return result


cases = ScapegoatCaseIndex()
for case_id in [19, 29, 47, 61, 83, 103, 127, 149, 173]:
    cases.insert(case_id)
print(cases.ordered_ids(), cases.rebuilds, cases.contains(83))

Output

[19, 29, 47, 61, 83, 103, 127, 149, 173] 2 True

Time, space, and tradeoff

Search follows a tree of logarithmic height after the insertion rebalance rule, so it takes O(log N) worst-case time for this insertion-only variant. An insertion can rebuild O(N) nodes at once but costs O(log N) amortized over a sequence; it does not promise low tail latency for one write. The flatten list and recursion use O(S) temporary space for rebuilt subtree size S, while stored nodes and sizes occupy O(N) space. A full mutable scapegoat tree also handles deletion and rebuilds the whole tree after enough shrinkage; those operations are outside this lesson. Python recursion depth is bounded by the maintained tree height here but would need care if this code were extended without its rebalance rule.

Common Mistakes

Do not use the amortized insertion bound as a per-write latency guarantee.
Do not update ancestor sizes after a duplicate rejection.
Do not reconnect a rebuilt subtree to the wrong grandparent child.
Do not claim deletion support from this insertion-only model.

Connected lessons

Compare its update and query contract with Two-dimensional range trees: count a static rectangle, Van Emde Boas trees: successor in a bounded integer universe, Static XOR filters: peel a fingerprint membership index, then complete the structure audit and decision quiz.

data structures

range-query-structures