Skip to content
Tutorials Center
My learning

Topics

Lesson 99 of 225 ยท Trees

Red-Black Trees, Splay Trees and Treaps

Learn how red-black trees, splay trees and treaps keep a binary search tree balanced, with rotations, a red-black insert and a treap built from scratch in Python.

An ordinary binary search tree is fast only when it is bushy. Insert the keys 1, 2, 3, ... in order and it turns into a linked list, and every search costs O(n). The AVL tree fixes this with a strict rule about heights. That rule makes lookups very fast but costs many rotations when you insert and delete a lot.

This lesson covers three other ways to stay balanced. Red-black trees relax the rule a little to save work, and they are what most standard libraries use. Splay trees have no rule at all: they simply move whatever you touch to the top. Treaps use randomness and a second hidden key. You will see why each idea works, then build a red-black insert and a treap from scratch.

Rotations: the one tool all of them share

Every balanced tree rebalances with a rotation. A rotation changes the shape of a few nodes without breaking the search-tree order. If you read the keys left to right (in-order), you get the same sequence before and after.

TEXT
        y                         x
       / \     rotate right(y)   / \
      x   C   ---------------->  A   y
     / \      <----------------     / \
    A   B      rotate left(x)      B   C

order before: A x B y C
order after:  A x B y C   (unchanged)

Subtree B is the only thing that changes parents: it was between x and y in the order, and it still is. A rotation touches a constant number of pointers, so it is O(1).

Python Rotations keep the order

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 order is the same, but the height dropped. Balanced trees are really just rules about when to rotate.

Red-black trees

A red-black tree is a binary search tree where every node has a color, red or black, and these rules hold at all times:

  1. Every node is red or black.
  2. The root is black.
  3. A red node never has a red child (no two reds in a row).
  4. Every path from a node down to a missing child (a None) passes through the same number of black nodes. This count is the node's black height.

New nodes are inserted red. That is a convention of the insert algorithm, not an invariant.

Rules 3 and 4 give a height guarantee. Rule 4 says all paths have equal numbers of black nodes. Rule 3 says red nodes can only be sprinkled between black ones, so the longest path is at most twice as long as the shortest one. A tree with n keys therefore has height at most 2 * log2(n + 1), which is O(log n).

Compare this with AVL: an AVL tree is allowed a height of about 1.44 * log2(n), while a red-black tree may reach 2 * log2(n). Searches in AVL trees are a little faster. But a red-black tree needs at most 2 rotations per insert and 3 per delete, while the rest of the fixing is recoloring, which is cheap. For workloads with many writes, that is a good trade.

Insert: color red, then repair

Insertion is a normal BST insert with the new node colored red. That can only break rule 3 (a red parent with a red child), so you repair upward. Let z be the red node, p its parent and u its "uncle" (the parent's sibling):

  • Parent is black: nothing to do.
  • Parent and uncle are both red: recolor the parent and uncle black and the grandparent red, then continue the repair from the grandparent. No rotation.
  • Parent is red, uncle is black (or missing): rotate. If z is on the "inside" (a left child of a right child, or the mirror), first rotate at the parent to make it an "outside" case. Then rotate the grandparent and swap colors. Done.

Finally, color the root black.

Python Red-black insert with a validator

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 input is the nightmare case for a plain BST, yet the red-black tree stays within the 2 * log2(32) = 10 bound. The check() method is worth keeping in your toolbox: whenever you implement a balanced tree, write a validator that asserts the invariants and run it after many inserts.

Deletion in a red-black tree is the hardest routine in a first course: it has about six cases, and many textbooks omit the code. You do not need it to understand the idea. The takeaway is that deleting a black node removes one black node from some paths, so the repair tries to push that "missing black" up the tree with recoloring and at most 3 rotations.

Splay trees

A splay tree stores no balance information at all. Its only rule is: after every access, move the accessed node to the root using rotations. The moves come in three shapes:

  • Zig: the node's parent is the root. One rotation.
  • Zig-zig: node and parent are both left children (or both right). Rotate the grandparent first, then the parent. This roughly halves the length of the path.
  • Zig-zag: node is a left child of a right child (or the mirror). Rotate the node twice.

A single operation can be O(n), because the tree can be a long chain. But the amortized cost of any sequence of m operations on n keys is O(log n) per operation (see amortized analysis). A bonus: recently used keys sit near the root, so splay trees adapt to access patterns, like a built-in cache.

Python Splaying a key to the root

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.

Splaying 8 does not just move it up: it also shortens the path to the other nodes it passed. That "path shortening" is what pays for the expensive first access.

Treaps

A treap is a tree + a heap. Every node holds a search key and a random priority. The tree is a BST on the keys and, at the same time, a max-heap on the priorities (a parent always has a higher priority than its children). For a given set of keys and distinct priorities there is exactly one such tree, and because the priorities are random, it has the same shape as a BST built by inserting the keys in random order. Random BSTs have expected height O(log n), no matter what order you insert in.

Insert is simple: do a normal BST insert, then, on the way back up, rotate the new node above its parent whenever its priority is larger.

Python A treap with seeded priorities

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.

Treaps are popular in contests because the code is short, and because they support cheap split and merge operations. Those two let you cut a sequence in two pieces or glue pieces together in O(log n), which is the basis of "implicit treaps" used for editors and sequence problems.

Comparing the balanced trees

Tree Height bound Rebalancing work Strength Typical use
AVL about 1.44 log n up to O(log n) rotations on delete fastest lookups read-heavy ordered maps
Red-black up to 2 log n at most 2 (insert) or 3 (delete) rotations cheap updates C++ std::map, Java TreeMap, Linux kernel
Splay none (amortized O(log n)) many rotations on every access adapts to hot keys, no extra memory caches, networking
Treap expected O(log n) expected O(1) rotations per insert tiny code, split/merge contests, sequences
Skip list expected O(log n) none (random levels) simple, easy to make concurrent Redis sorted sets

Common mistakes

  • Forgetting the root rule. After the repair loop, always recolor the root black.
  • Skipping the first rotation in the inside case. Rotate at the parent first, otherwise the order or the colors break.
  • Using the same priority twice in a treap. Draw priorities from a large range (floats are fine) so ties are practically impossible.
  • Unseeded randomness in tests. A seeded generator makes treap tests repeatable.
  • Recursion depth. A splay tree can be a chain of n nodes, so a recursive splay on huge inputs can hit Python's recursion limit.

When to use what

In Python you rarely write these yourself: a dict or a sorted list with bisect covers most needs (see dicts and sets). Reach for a balanced tree when you need an ordered collection with fast inserts and deletes in the middle, such as a calendar, an order book or "the next larger key". Choose AVL for read-mostly data, red-black for a general-purpose ordered map, a splay tree for skewed access patterns, and a treap when you want short code or split/merge.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is true about every rotation in a binary search tree?

    A rotation only re-links a few nodes and moves one subtree to a new parent, so the left-to-right order of keys stays the same. It is O(1), and it does not always reduce the height.
  2. 2. Why do the rules 'no red node has a red child' and 'equal black height on every path' bound the height?

    All paths have the same number of black nodes, and reds can only appear between blacks. The shortest path is all black, the longest alternates red and black, so the longest is at most twice as long, giving a height of O(log n).
  3. 3. In a red-black insert, the new red node's parent and uncle are both red. What do you do?

    This is the recoloring case. It removes the red-red conflict locally but may create a new one at the grandparent, so the repair loop continues from there.
  4. 4. What guarantee does a splay tree give?

    A single splay can be O(n) on a chain, but the expensive operations shorten the tree so much that the total over any sequence is O(log n) per operation on average.
  5. 5. A treap stores a random priority in each node. What are the priorities used for?

    The tree is a BST on keys and a heap on priorities. For distinct random priorities that structure is unique and behaves like a BST built from a random insertion order, with expected height O(log n).

Summary

  • Rotations re-link a few nodes in O(1) and preserve the in-order key sequence. All balanced trees are built on them.
  • A red-black tree enforces: black root, no red-red, equal black height. Its height is at most 2 * log2(n + 1), and it needs at most 2 rotations per insert.
  • Insert red, then repair: recolor when the uncle is red, rotate (once or twice) when the uncle is black.
  • A splay tree moves each accessed node to the root. Single operations can be O(n), but the amortized cost is O(log n) and hot keys stay close to the top.
  • A treap pairs each key with a random priority and keeps a BST on keys and a heap on priorities, giving expected O(log n) height with very little code.
  • Write a validator for the invariants and run it in your tests.

Next: B-Trees and B+ Trees