7 / 8 Treaps, Splay & The Balanced BST Zoo

Persistence Eats Amortization

You want a fully persistent balanced BST: every past version stays queryable forever, and a user may branch off any of them. Whose complexity claim survives, and why do the others not?

A

All three. Their bounds are expected or amortized over their own operations and every operation touches one root-to-leaf path, so path copying preserves them. Splay and scapegoat are amortized, and a persistent user re-running the one expensive operation from an old version still pays back the credit banked there.

B

The FHQ treap. Its bound is expected over its own priorities and every operation is a fresh split/merge, so path copying preserves it. Splay and scapegoat are amortized, and a persistent user can re-run the one expensive operation from the same old version repeatedly, never paying the credit back.

C

The splay tree. Its bound is amortized over its own accesses and every operation re-splays the path it touched, so path copying preserves it. FHQ treap and scapegoat are expected and amortized, and a persistent user can re-run the one expensive operation from the same old version repeatedly, never paying the credit back.

D

The scapegoat tree. Its bound is amortized over its own rebuilds and every rebuild yields one perfectly balanced subtree that later versions share, so path copying preserves it. Splay and FHQ treap are amortized and expected, and a persistent user can re-run the one expensive operation from the same old version repeatedly, never paying it back.