Skip to content
Tutorials Center
My learning

Topics

Lesson 100 of 225 ยท Trees

Scapegoat Trees and Self-Organizing Lists

Two structures that fix themselves lazily: scapegoat trees rebuild a lopsided subtree, and self-organizing lists reorder with move-to-front, transpose and count.

Most balanced trees, like AVL and red-black trees, store extra data in every node and repair the shape with rotations after each update. This lesson shows a different, lazier idea: do nothing until things go wrong, then fix them in one go. We meet it twice. A scapegoat tree is a binary search tree that rebuilds a whole subtree when it notices the tree has become too deep. A self-organizing list is a plain linked list that rearranges itself so that the items you ask for most often drift toward the front.

Both rely on the same principle you saw in amortized analysis: an occasional expensive repair is fine if it is paid for by many cheap operations.

Scapegoat trees

A scapegoat tree is an ordinary binary search tree: no colors, no heights and no balance factors. The only thing it stores per node is the key and two child links (the node sizes are computed when needed). It is controlled by one number, alpha, between 0.5 and 1. A tree with n nodes is considered too deep if it is deeper than log(n) / log(1/alpha). With alpha = 0.7 that is about 1.94 * log2(n), nearly twice the ideal depth of a perfect tree.

How insertion works

  1. Insert the key like in any binary search tree and remember the path.
  2. If the new node ended up deeper than the limit, the tree is out of balance, and some node on the path is to blame.
  3. Walk up the path until you find an ancestor that is not alpha-weight-balanced: one of its children holds more than alpha times the ancestor's subtree size. That ancestor is the scapegoat.
  4. Rebuild the scapegoat's subtree into a perfectly balanced one: write its keys in sorted order (an in-order walk), then build a tree from the middle outward.

Why does a scapegoat always exist? If every node on the path were alpha-balanced, the path could not be that deep; the depth limit and the weight rule are tied together by the arithmetic. Rebuilding costs time proportional to the subtree size, but it happens rarely and leaves a perfect tree behind, so insertion is O(log n) amortized, and search is O(log n) worst case because depth never stays above the limit.

Python A scapegoat tree with insertion and rebuilding

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 insertion would build a 200-level chain in an ordinary BST. Here the height stays within a small multiple of log2(n) (15 levels against an ideal of 8). Sorted input is the harshest case for a scapegoat tree, so it rebuilds often (73 times for 200 inserts), but most rebuilds touch only a small subtree near the bottom, which is why the total work stays near O(n log n).

Deletion

Deletion is a normal BST delete plus a global counter. Keep max_n, the largest size since the last full rebuild. After a delete, if n < alpha * max_n, rebuild the entire tree and set max_n = n. This keeps the depth bound valid when many deletes shrink the tree. Delete, too, is O(log n) amortized.

Why bother?

The big selling point is space: no balance information per node, so each node is as small as in a plain BST. The price is that single operations can occasionally take O(n) when a rebuild happens, so scapegoat trees suit applications that care about the total time, not each individual call. The tuning knob is alpha: values near 0.5 keep the tree tight but rebuild often; values near 1 rebuild rarely but allow deep trees.

Self-organizing lists

Now the second lazy idea. A singly linked list has O(n) search, and the cost of finding an item is its position. If a few items are requested far more often than the rest (a very common pattern: popular products, frequent words, recently used files), putting those items near the front would make the average search much shorter. But you rarely know the frequencies in advance. A self-organizing list learns them on the fly, using a rule applied after every successful search:

  • Move-to-front (MTF): move the found item to the head of the list. Recently used items stay near the front. This is the idea behind "recent files" menus and some caches.
  • Transpose: swap the found item with the one just before it. Items climb by one step per access, so it reacts slowly but never throws a popular item far back.
  • Count (frequency): keep a counter per item; after each access, move the item forward past neighbors with a smaller count. The list stays sorted by frequency, at the price of an extra integer per node.
Python Comparing the three rules on skewed requests

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.

With uniform requests no rule would help, since every position is equally likely. With skewed requests, all three beat a static list that starts in a bad order by a factor of 2.4 to 3.3 in this run. Count converges to the best fixed order; move-to-front adapts quickly when the popular items change; transpose is the most stable but slowest to react.

Competitive guarantee

A known result: move-to-front never costs more than about twice what the best possible list would pay, even for the best arrangement chosen with full knowledge of the future (in the model where reorderings are charged). That is why MTF is the default choice and why it appears in compression too: the move-to-front transform replaces each symbol by its current position in a list and moves it to the front, so repeated symbols become small numbers (see the Burrows-Wheeler lesson).

Python Move-to-front transform

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.

Runs of the same letter turn into runs of zeros, which compress very well.

Common mistakes

  • Setting alpha outside (0.5, 1). At 0.5 or below no tree can satisfy the rule; at 1 nothing ever counts as unbalanced.
  • Rebuilding the whole tree on every violation instead of only the scapegoat subtree.
  • Expecting self-organizing lists to help with uniform access. They only pay off when accesses are skewed.
  • Using a list that reorders on every read in a structure shared by many threads. A "read" now writes.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is stored in a scapegoat tree node besides the key and child links?

    This is the main advantage: no balance data per node. When an insertion goes too deep, sizes are measured along the path to find the scapegoat.
  2. 2. After an insertion exceeds the depth limit, what does a scapegoat tree do?

    The first ancestor on the way up whose child holds more than alpha of its size is the scapegoat. Its subtree is flattened in order and rebuilt as a perfectly balanced tree.
  3. 3. Which self-organizing rule moves the accessed item all the way to the front?

    Move-to-front jumps to the head after every successful search. Transpose moves only one step, and count moves past items with smaller counters.
  4. 4. When will a self-organizing list give the biggest improvement?

    Reordering pays off when popular items are found repeatedly, because they end up near the front where searches are short.

Summary

  • A scapegoat tree is an unaugmented BST that rebuilds a subtree when an insertion goes deeper than log(n) / log(1/alpha).
  • The scapegoat is the first ancestor whose child holds more than alpha of its size; its subtree is flattened and rebuilt perfectly.
  • Search is O(log n) worst case; insert and delete are O(log n) amortized; deletes trigger a full rebuild when n < alpha * max_n.
  • Self-organizing lists reorder after each access: move-to-front, transpose or count.
  • They help when requests are skewed, and move-to-front is within a constant factor of the best possible static arrangement.
  • Both structures trade an occasional costly repair for simplicity and low overhead.

Next: N-ary Trees