Path Copying and the Cost of Persistence in Balanced Trees

A persistent data structure preserves every previous version after an update. The usual implementation for a balanced tree is path copying: the update descends to the affected node, constructs new copies of every node on that path, and leaves every node off the path shared with the previous version. A tree of n nodes and height h therefore allocates h new nodes per update and shares the remaining n − h, so the time and space per update are both O(log n).

That is the simple part. The parts that matter are the consequences: rotations inside a copied path must not mutate shared nodes, the balance invariants interact with sharing in ways that are easy to get wrong, and the constant factors are dominated by allocation rather than by comparison.

The sharing argument

Consider an update that changes one key. In the previous version, the path from the root to that key consists of h + 1 nodes, each holding a pointer to a subtree. Every subtree hanging off that path is unchanged by the update, so it can be referenced by both versions. Only the path nodes must be duplicated, and each duplicate points at the same children as the original except for the one child on the path.

type Link<T> = Option<std::rc::Rc<Node<T>>>;

struct Node<T> {
    key: T,
    left: Link<T>,
    right: Link<T>,
}

// Insert into a persistent BST; unchanged subtrees are shared with the input.
fn insert<T: Ord + Clone>(t: &Link<T>, key: T) -> Link<T> {
    match t {
        None => Some(std::rc::Rc::new(Node { key, left: None, right: None })),
        Some(node) => {
            let mut n = Node { key: node.key.clone(), left: node.left.clone(), right: node.right.clone() };
            if key < node.key {
                n.left = insert(&node.left, key);
            } else if key > node.key {
                n.right = insert(&node.right, key);
            } else {
                return t.clone();          // key present: share the whole subtree
            }
            Some(std::rc::Rc::new(n))
        }
    }
}

This is a plain binary search tree, so it has the degenerate-height problem described in height bounds and the cost of a degenerate tree. Persistence does not fix balance; it only fixes the cost of an update given the height. To get a logarithmic update the tree must also be balanced, and the balance metadata must be copied along with the node.

Rotations cannot mutate shared nodes

The moment a balance scheme is added, the update path is no longer a simple descent. A rotation at the bottom of the path rewires three pointers, and if those pointers refer to nodes that are shared with an earlier version, the rotation would corrupt that version. The rule is absolute: every node that a rotation touches must already be a fresh copy owned by the new version.

The practical consequence is that the copy must be made before the rotation, not after. In a mutable implementation the order is descend, rotate, then walk up; in a persistent one the order is descend copying, rotate the copies, and return the new root. Implementations that copy only the nodes on the search path and then rotate a node that was not on that path — the sibling that becomes a child, for instance — break sharing silently. The bug is invisible until a query on the old version follows a pointer into the new version’s structure, and it then produces a wrong answer rather than a crash.

A rotation moves one subtree from one parent to another, so the subtree itself is shared and only the two parents need to be new. That is consistent with the path-copying rule, since both parents are on the search path when the rotation happens. The invariant to state explicitly in the code is: rotations are applied only to nodes that the current update has freshly allocated.

/* Persistent red-black insertion: copy the node, then rotate the copy. */
node *insert_p(node *t, int key, int *ok) {
    if (t == NULL) { *ok = 1; return new_red_node(key); }
    node *n = copy_node(t);              /* fresh copy; shares both children */
    if (key < t->key)      n->left  = insert_p(t->left,  key, ok);
    else if (key > t->key) n->right = insert_p(t->right, key, ok);
    else { *ok = 0; free(n); return t; }
    return n;                            /* rebalance operates on n, never on t */
}

The rebalancing step is elided above; in a real implementation it follows the copy and operates on n, which is owned by this version. The important structural point is that the function returns a new root and never writes through t.

Where the cost goes

The asymptotic story is clean: O(log n) time and O(log n) new nodes per update, with the rest shared. The constant factors are less clean, and they are dominated by three things.

The first is allocation. Each update allocates h nodes, and on a managed runtime each allocation also creates work for the collector. A tree of a million keys has height near 20, so an update allocates on the order of 20 nodes and abandons none — the previous version is still reachable if the caller holds a reference. A workload that keeps every version alive retains O(n + m log n) nodes after m updates, which is the space bound that makes persistence expensive in long-lived systems.

The second is indirection. A path-copied tree cannot store nodes in a contiguous array, because a new version must coexist with the old one and the old one’s layout is fixed. Every access is a pointer dereference, and the cache behaviour is that of a linked structure. This is the price paid for sharing, and it is the reason persistent trees are often slower per query than mutable ones even when the update cost is comparable.

The third is reference counting or tracing. On a runtime with reference counting, every pointer copy adjusts a counter, and the counters sit in the same cache line as the node, so a read-only traversal that clones pointers writes to shared cache lines. On a tracing collector the cost moves to collection time and depends on how much of the version graph is still reachable. Neither is free, and both change the constant by a factor that the asymptotic analysis hides.

Scheme	Nodes per update	Metadata per node	Old versions readable
Mutable red-black	0 (in place)	1 bit	no
Path-copied red-black	h + 1	1 bit	yes
Path-copied AVL	h + 1	2 bits	yes
Fat-node (versioned fields)	0	unbounded per field	yes, with lookup cost

The fat-node approach, where each field records a modification history and a version number selects the right entry, avoids allocating per update but makes every field access a search. The trade is between allocation and lookup, and it is the same trade that the persistence literature formalises as the difference between path copying and node versioning.

Why the balance invariants survive, and where they do not

For red-black and AVL trees, the balance invariant is a function of the node’s own metadata and its children’s, so a copied node can compute it from the shared children exactly as a mutable node would. The invariants survive path copying unchanged, which is why persistent red-black trees are a standard implementation in functional languages.

Two invariants do not survive as cleanly. The first is any invariant that refers to parent pointers, because a shared node has one parent in each version that references it, and a single parent field cannot record both. Implementations either drop parent pointers and pass the path explicitly, or copy the parent pointer into the new node and accept that the shared child’s back-pointer refers to the newest parent — which is wrong for the old version. Dropping the pointers is the usual choice, and it is why persistent implementations of splay trees, which need parent pointers for the upward walk, are rare.

The second is any invariant maintained by mutation of a sibling, which is the shape of B-tree splits. A B-tree split modifies a node and its sibling, and under persistence both must be copied, so a single insertion may copy two nodes per level rather than one. That doubles the allocation per update, and it is why persistent B-trees are usually implemented with a copy-on-write page model at the storage layer rather than as a purely functional node structure.

The version graph as a data structure

A persistent tree’s versions form a directed acyclic graph: each version points to its parent version and to the nodes it created. The graph is what makes garbage collection non-trivial, because a node is live if any reachable version references it, and the reachability is through the sharing edges rather than through a single root.

Two consequences follow. The first is that dropping a version does not immediately free the nodes it created, since later versions may share them. Reclaiming requires either reference counting on the nodes or a tracing collector that starts from all live version roots. The second is that the space bound for a sequence of m updates is not m log n in the worst case but depends on the shape of the version graph; a linear chain of versions retains every node it ever created, while a tree of versions that periodically merges shares more.

The practical lesson is that persistence is a property of the whole system, not of the tree alone. A persistent tree in a system that keeps every version is a space leak with a logarithmic rate; the same tree in a system that keeps a bounded window of versions is a fine data structure. The balance invariants described throughout this cluster are all compatible with sharing, and the cost of choosing persistence is paid in allocation and indirection rather than in correctness. The one structure that resists this treatment is the splay tree, because its repair walks upward through parent pointers, and splaying’s restructuring depends on a single mutable parent link that sharing cannot provide.