Skip to content
Tutorials Center
My learning

Topics

Lesson 200 of 225 ยท Advanced Topics

Advanced Amortized Structures

Go beyond dynamic arrays. Study splay tree amortization, the inverse Ackermann bound for union-find, ropes for text editors and persistent stacks in Python.

In amortized analysis you saw how a dynamic array pays for rare expensive resizes with many cheap appends. That idea is far more powerful than it first looks. Some of the most elegant data structures have no worst-case guarantee per operation at all, yet guarantee that any long sequence of operations is fast.

This lesson revisits four structures from that angle: the splay tree (a self-adjusting search tree), union-find (whose cost is bounded by the strangely slow-growing inverse Ackermann function), the rope (a tree of strings for text editors) and the persistent stack (old versions stay usable after "changes"). Each one shows a different way to turn local cleverness into a global guarantee.

Splay trees: a tree that reorganizes itself

A binary search tree is only fast if it is balanced. AVL and red-black trees store balance information in every node and fix it with rotations. A splay tree stores nothing extra. Instead, every time you access a key, it moves that key to the root with a sequence of rotations called splaying.

The effect is self-organizing: recently used keys sit near the top, rarely used keys sink. A single access can be slow (the tree may be a long chain), but a long chain is repaired by the access that walked it.

There are three cases when splaying a node x with parent p and grandparent g:

TEXT
zig       (p is the root)          one rotation
zig-zig   (x and p both left, or both right children)
             g              x
            /                \
           p        ->        p
          /                    \
         x                      g       rotate g's parent link first, then p
zig-zag   (x is a left child of a right child, or the reverse)
           g                 x
            \               / \
             p     ->      g   p        rotate x up twice
            /
           x

The zig-zig case (rotating the grandparent first) is what makes the amortized proof work: it roughly halves the depth of every node on the access path, not just of x.

Here is a splay tree where insert and find both splay, and a global counter records every rotation:

Python A splay tree that counts rotations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sorted inserts produce a chain of height 200, which would be a disaster in a plain BST. The first access to key 1 costs 199 rotations, but it also reshapes the chain into a tree about half as tall, and the 200 sequential accesses that follow cost 816 rotations in total, about 4 per access, instead of the roughly 20,000 a chain would need. Expensive operations pay for their own repair.

Why it is amortized O(log n): the potential method

The proof uses a potential function. Give every node a rank r(v) = log2(size of the subtree rooted at v) and let the potential ฮฆ be the sum of all ranks. A long, thin chain has a large potential; a balanced tree has a small one. The access lemma says that splaying x has amortized cost at most 3 * (r(root) - r(x)) + 1. Because r(root) = log2 n, every access has amortized cost O(log n). Over m operations on a tree of n keys, the total is O(m log n + n log n), since the potential starts at most n log n.

We can check the lemma on real runs: the actual rotations plus the change in potential must stay under 3 * log2(n) + 1.

Python Checking the access lemma numerically

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first access drains the huge potential of the chain: its actual cost is big but the potential drops by nearly the same amount, so its amortized cost is small. That is the whole trick.

Splay trees also satisfy stronger claims: the static optimality theorem (they do as well as the best fixed tree for your access frequencies) and the unproven dynamic optimality conjecture (they might match any binary search tree strategy). The price is that individual operations have no worst-case guarantee, and even reads change the tree, which makes sharing a splay tree between threads awkward.

Union-find and the inverse Ackermann function

Union-find tracks which items belong to the same set. With two tricks, union by rank (attach the shorter tree under the taller) and path compression (make every node on a find path point straight at the root), a sequence of m operations on n items costs O(m * ฮฑ(n)), where ฮฑ is the inverse Ackermann function.

The Ackermann function grows faster than any function you would normally write down, so its inverse grows slower than almost anything. Here are the first values of the standard two-argument version:

Python The Ackermann function grows absurdly fast

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A(4, 2) already has 19,729 decimal digits. Since ฮฑ(n) is roughly the smallest k for which A(k, k) reaches n, it is at most 4 for any n that could fit in the physical universe. So union-find is technically not constant time, but for every practical purpose it is.

You cannot see ฮฑ directly in a small experiment, but you can see the effect of the two tricks by counting the pointer steps find takes. Below, the same worst-case-ish sequence of unions runs on a naive union-find and on the optimized one:

Python Counting find steps: naive versus optimized

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The naive version ends with a chain of 2,000 nodes, so each of the 2,000 finds of element 0 walks the whole chain and the total reaches into the millions. With rank and compression the total stays in the low thousands. The proof that the bound is exactly ฮฑ (Tarjan, 1975) is one of the hardest analyses in introductory algorithms, and Tarjan also showed the bound cannot be improved for this kind of structure.

Ropes: editing huge strings cheaply

Python strings are immutable and stored contiguously. Inserting one character into a string of a million characters copies about a million characters. A text editor that did this on every keystroke would crawl.

A rope stores the text as a binary tree whose leaves are small strings. Each internal node remembers the length of its left subtree (its weight), so you can find the character at index i by walking down. Joining two ropes is O(1): just create a new parent. Inserting means splitting the rope at a position and concatenating three ropes, which only touches nodes along one root-to-leaf path.

TEXT
         (weight 6)
         /        \
   (weight 3)     "world!"
    /     \
 "Hel"   "lo "

The text is "Hello world!". index(7): 7 >= weight 6, so go right with index 1 -> "world!"[1] = 'o'
Python A rope with concat, index, split and insert

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the original rope is unchanged after insert: because nodes are never modified, the new rope simply shares all the untouched nodes. That sharing is the bridge to the last topic.

Plain ropes can become lopsided after many edits, so real editors rebalance them (or use a balanced tree such as a B-tree or a finger tree of chunks). Another popular design is the piece table. The rope's weakness is a larger constant factor: for small texts, a plain string or the gap buffer is faster. Ropes pay off when strings are huge and edits happen anywhere.

Persistent structures: keeping every version

An ephemeral structure loses its old state when you change it. A persistent structure keeps every version available: updates return a new version and the old one still works. Persistent data makes undo history trivial, enables safe sharing between threads, and is the foundation of functional programming.

The simplest persistent structure is the immutable linked stack. Pushing creates one new node whose next points at the old stack; popping just returns the old node's next. Nothing is copied, so both operations are O(1) in time and space, and all versions share their common tails (structural sharing).

TEXT
v0 = empty
v1 = push(v0, "a")        v1:  a -> .
v2 = push(v1, "b")        v2:  b -> a -> .
v3 = push(v1, "c")        v3:  c -> a -> .      (v2 and v3 share the tail "a")
Python A persistent stack with shared versions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For structures other than stacks, persistence uses path copying: to "change" a node deep in a tree, copy that node and each ancestor on the way to the root (about O(log n) nodes in a balanced tree) and let everything else be shared. The new root represents the new version. Persistent segment trees built this way can answer questions such as "what was the k-th smallest in the first i elements?" using one version per prefix.

Persistence interacts with amortization in a surprising way: amortized bounds can fail for persistent structures. If an expensive operation is paid for by credit built up by earlier cheap ones, using the same old version twice spends that credit twice. Persistent structures therefore need worst-case bounds, or special techniques such as lazy evaluation.

Common mistakes

  • Treating amortized as worst case per operation. A splay or a dynamic-array resize can be slow once; do not use them where one slow operation breaks a deadline (real-time code).
  • Forgetting that reads change a splay tree. A find restructures the tree, which matters for concurrency and for iterating while searching.
  • Using only one union-find trick. Path compression alone gives O(log n) amortized and rank alone gives O(log n) worst case; you need both for ฮฑ(n).
  • Copying strings in a loop. Building text with repeated s = s[:i] + t + s[i:] is quadratic over many edits; use a rope, a gap buffer or collect pieces in a list and join once.
  • Mutating "persistent" data. One accidental in-place change breaks every version sharing that node. Make the nodes immutable (frozen dataclasses, tuples).

When to use which

Use a splay tree when access patterns are skewed or sequential and you do not want to store balance data, as in caches and some network routers. Use union-find whenever you merge groups and ask connectivity questions (Kruskal's algorithm, connected components). Use a rope (or a piece table) when users edit large text and need cheap inserts and deletes. Use persistent structures for undo/redo, version history, or concurrent code that must not see half-finished updates. For most programs a plain list, dict or balanced tree is simpler and just as good.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a splay tree do when you search for a key?

    Splaying moves the accessed node to the root using zig, zig-zig and zig-zag rotations. This self-adjustment is what gives the O(log n) amortized bound without stored balance data.
  2. 2. In the potential-method analysis of splay trees, what is the potential function?

    The potential is the sum of node ranks, where rank is log2 of the subtree size. A chain has a large potential, and splaying it releases that potential, paying for the long access.
  3. 3. Which pair of techniques gives union-find its O(alpha(n)) amortized bound?

    Either technique alone only achieves O(log n) amortized. Together they give the inverse Ackermann bound, which is at most 4 for any realistic input size.
  4. 4. Why is concatenating two ropes O(1)?

    A concatenation node just records the two children and the length of the left one. Characters are only copied when a leaf has to be split.
  5. 5. After v2 = v1.push("b") on a persistent stack, what happens to v1?

    Persistent operations return a new version and never modify old nodes, so v1 stays exactly as it was and v2 shares v1 as its tail.

Summary

  • Amortized structures guarantee the cost of a sequence of operations, not each operation.
  • Splay trees move every accessed key to the root; a potential function (sum of log subtree sizes) proves O(log n) amortized per operation with no balance data.
  • Union-find with union by rank and path compression runs in O(ฮฑ(n)) amortized, where the inverse Ackermann ฮฑ(n) is at most 4 in practice.
  • A rope is a tree of string pieces: concat is O(1), index/split/insert are proportional to the tree depth, and old versions stay intact.
  • Persistent structures share unchanged nodes (structural sharing, path copying) so every version remains usable; amortized bounds can break when old versions are reused.

Next: Project: Autocomplete Engine