7.14 Treaps

Most balanced tree structures maintain balance through carefully designed invariants. AVL trees track subtree heights. Red-black trees maintain color constraints. B-trees enforce node capacity rules.

Treaps take a different approach.

Instead of explicitly maintaining balance, they introduce randomness.

A treap combines two structures:

A binary search tree on keys
A heap on priorities

The name comes from this combination:

Tree + Heap = Treap

The result is a remarkably simple balanced tree with expected logarithmic performance. Treaps are popular in competitive programming, randomized algorithms, in-memory indexing systems, and situations where implementation simplicity matters more than worst-case guarantees.

Problem

Suppose we insert sorted values into an ordinary binary search tree.

The resulting tree becomes:

10
  \\n   20
     \\n      30
        \\n         40
           \\n            50
              \\n               60
                 \\n                  70

Height:

Search complexity:

O(n)

We need a way to prevent pathological insertion orders from producing pathological trees.

AVL trees and red-black trees solve this using explicit balancing rules.

Treaps solve it using random priorities.

Understanding the Structure

Each node stores:

type Node struct {
	Key      int
	Priority int

	Left  *Node
	Right *Node
}

The key obeys BST ordering:

Left < Node < Right

The priority obeys heap ordering:

Parent priority >
Child priority

Example:

Key:       50
Priority:  90

Children:

Key:       25
Priority:  70

Key:       75
Priority:  60

The priorities create an additional structure that influences the tree shape.

BST Property

Keys obey ordinary BST rules.

Example:

          50
         /  \\n       25    75
      / \    / \\n    10 40 60 90

Search operations use keys exactly as they would in a normal BST.

The priorities play no role during lookup.

This is an important distinction.

Keys determine ordering.

Priorities determine shape.

Heap Property

Now assign priorities.

          50(90)
         /      \\n     25(70)    75(60)
      /  \      /  \\n 10(20)40(50)60(30)90(10)

Observe:

Every parent priority exceeds its children's priorities.

This is a max-heap.

Some implementations use min-heaps instead.

The choice is arbitrary as long as it remains consistent.

Why Random Priorities Work

Suppose priorities are assigned randomly.

Example:

Key: 10 Priority: 17
Key: 20 Priority: 82
Key: 30 Priority: 44
Key: 40 Priority: 91
Key: 50 Priority: 33

The resulting shape depends primarily on priorities rather than insertion order.

A remarkable mathematical result shows that randomly assigned priorities produce expected height:

O(log n)

This means a treap behaves similarly to a randomly built BST regardless of insertion sequence.

The balancing emerges naturally from randomness.

Insertion

Insertion occurs in two phases.

Phase 1: BST Insertion

Insert by key.

Suppose:

       20(90)
      /
   10(50)

Insert:

30(95)

BST insertion gives:

       20(90)
      /      \\n   10(50)   30(95)

The BST property is correct.

The heap property is violated.

95 > 90

The child has higher priority than the parent.

Phase 2: Rotate Up

Apply a rotation.

Now both invariants hold.

This process repeats until the heap property is restored.

Example Walkthrough

Insert:

50(60)
20(40)
80(90)

After BST insertion:

       50(60)
      /      \\n   20(40)   80(90)

Heap violation:

90 > 60

Rotate left.

The tree is now valid.

Notice that insertion required only local rotations.

Recursive Insertion

A simplified implementation:

func Insert(
	root *Node,
	key int,
	priority int,
) *Node {

	if root == nil {
		return &Node{
			Key: key,
			Priority: priority,
		}
	}

	if key < root.Key {

		root.Left =
			Insert(
				root.Left,
				key,
				priority,
			)

		if root.Left.Priority >
			root.Priority {

			root =
				RotateRight(root)
		}

	} else {

		root.Right =
			Insert(
				root.Right,
				key,
				priority,
			)

		if root.Right.Priority >
			root.Priority {

			root =
				RotateLeft(root)
		}
	}

	return root
}

This implementation is dramatically simpler than AVL insertion.

The priorities guide balancing automatically.

Deletion

Deletion also uses rotations.

Suppose:

        50(90)
       /      \\n   20(70)    80(60)

Delete:

Instead of immediately removing the node, rotate the higher-priority child upward.

       20(70)
         \\n         50(90)
           \\n           80(60)

Continue rotating until the target becomes a leaf.

Remove the leaf.

This preserves both invariants throughout the operation.

Split

One of the most elegant treap operations is split.

Given:

Keys < X

and

Keys ≥ X

produce two treaps.

Example:

1 2 3 4 5 6 7

Split at:

Results:

1 2 3

and

4 5 6 7

Both outputs remain valid treaps.

Split operates in:

O(log n)

expected time.

Many advanced treap algorithms are built on top of split.

Merge

Merge performs the inverse operation.

Given two treaps:

All keys in A
<
All keys in B

construct a single treap.

Example:

A = [1 2 3]
B = [4 5 6]

Result:

[1 2 3 4 5 6]

Merge also runs in expected logarithmic time.

The combination of split and merge makes treaps extremely flexible.

Implicit Treaps

A particularly useful variant removes explicit keys.

Instead:

Position = key

The tree stores sequence order.

Operations include:

Insert at position
Delete at position
Reverse range
Move segment
Range queries

Example:

A B C D E F G

Reverse:

[C, F]

Result:

A B F E D C G

All performed in logarithmic time.

Implicit treaps are widely used in competitive programming because they behave like dynamic arrays with efficient updates.

Why Treaps Are Popular

Treaps offer several advantages.

Simple Implementation

The balancing logic is surprisingly small.

Most implementations fit comfortably in a few hundred lines.

Expected Logarithmic Performance

Random priorities produce balanced trees on average.

Split and Merge

These operations are easier than in AVL or red-black trees.

Flexible Augmentation

Additional information can be stored in nodes:

Size int
Sum  int
Min  int
Max  int

This enables powerful range-query structures.

Limitations

Treaps provide expected guarantees rather than strict guarantees.

AVL trees guarantee:

O(log n)

height.

Treaps guarantee:

Expected O(log n)

height.

A pathological random sequence is theoretically possible, though extremely unlikely.

For most practical applications this distinction is acceptable.

Treaps Versus AVL Trees

Feature	Treap	AVL
Balancing	Randomized	Deterministic
Height guarantee	Expected O(log n)	Worst-case O(log n)
Implementation complexity	Low	Moderate
Rotations	Simple	More complex
Split/Merge	Excellent	Difficult
Predictability	Probabilistic	Deterministic

Treaps often win when implementation simplicity matters.

AVL trees win when strict guarantees are required.

Complexity Analysis

Expected height:

O(log n)

Expected operation costs:

Operation	Complexity
Search	O(log n)
Insert	O(log n)
Delete	O(log n)
Split	O(log n)
Merge	O(log n)

Space complexity:

O(n)

Common Mistakes

A common mistake is generating priorities poorly. Low-quality random number generators can create undesirable structures.

Another mistake is forgetting that balancing depends entirely on priorities. If priorities are not random, performance guarantees may disappear.

A third mistake is confusing keys and priorities. Searches use keys. Rotations use priorities.

Finally, many implementations fail to update auxiliary metadata such as subtree sizes during rotations. Any augmentation must be recomputed after structural changes.

Takeaway

Treaps combine binary search tree ordering with heap priorities to produce a simple randomized balanced tree. By assigning random priorities and restoring heap order through rotations, they achieve expected logarithmic performance without complex balancing rules. Their elegant split and merge operations make them particularly useful for dynamic sequences, interval manipulation, and competitive programming. Treaps demonstrate an important algorithmic principle: randomness can often replace complicated deterministic logic while preserving excellent practical performance.