Skip to main content

Treap: Let Random Priorities Keep the Tree Balanced

A Treap combines two familiar tree ideas into one structure. It stores an ordered key like a binary search tree, and it assigns every node a priority that participates in a heap ordering. The name is a blend of tree and heap.

The central idea is simple:

  • Keys determine the left-to-right order.
  • Priorities determine the top-to-bottom order.
  • Rotations repair the heap order without destroying the key order.
  • Random priorities make highly unbalanced shapes unlikely.

This gives the Treap the search behavior of a binary search tree while using randomized priorities to influence its shape. A Treap does not store an explicit height, color, rank, or balance factor. Instead, its shape is induced by the relative ordering of node priorities.

The most useful way to understand a Treap is to keep its two rules separate. First ask whether the keys are arranged like a BST. Then ask whether the priorities are arranged like a heap. Every operation must preserve both rules.

1. The Two Invariants​

Every Treap node contains at least two important values:

(key, priority)

The key controls search order. The priority controls which nodes are allowed to appear above other nodes.

1.1 The binary-search-tree invariant​

For every node, all keys in its left subtree are smaller than the node's key, and all keys in its right subtree are larger than the node's key. Assuming distinct keys, this rule is:

key(left subtree)<key(node)<key(right subtree)\text{key(left subtree)} < \text{key(node)} < \text{key(right subtree)}

This is the ordinary binary-search-tree rule. It means an in-order traversal visits keys in sorted order.

For example, the following shape is a valid BST:

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

Its in-order traversal is:

10, 20, 30, 40, 50, 60, 70

The exact shape is not important for the ordering property. Many different binary trees can represent the same sorted set of keys. What matters is that every node separates smaller keys from larger keys.

1.2 The min-heap invariant​

A Treap also follows a min-heap rule for priorities. A node's priority must be no greater than the priority of either child. For a parent and child, the relationship is:

priority(parent)≤priority(child)\text{priority(parent)} \leq \text{priority(child)}

Thus, the smallest priority appears at the root, and priorities do not decrease as we move down any root-to-leaf path.

For example:

              (40, 5)
             /       \
         (20, 12)   (60, 9)
         /    \     /    \
    (10, 18) (30, 15) (50, 14) (70, 20)

This tree satisfies the min-heap condition. The root has priority 5, which is smaller than every priority below it. Each child also has a priority no smaller than its parent.

The Treap must satisfy both rules at the same time. A tree can be a valid BST but violate the heap rule. It can also satisfy the heap rule while placing keys in the wrong order. Neither case is a valid Treap.

1.3 Why the two fields have different jobs​

The key answers questions such as:

  • Where should a new value be inserted?
  • Which values are smaller or larger?
  • What is the sorted order?
  • Which subtree may contain a requested key?

The priority answers a different question:

  • Which node should be above another node when the shape is repaired?

A helpful mental model is that the key controls horizontal position and the priority controls vertical position. The key determines whether a node belongs to the left or right side of another node. The priority determines whether that node should remain below its parent or rotate upward.

2. Random Priorities and Randomized Balance​

If priorities are chosen in an unfortunate deterministic pattern, a Treap can still become a chain. For example, if keys are inserted in increasing order and priorities also force every new node below the previous one, the resulting tree may resemble a linked list. The BST invariant alone does not prevent this.

Random priorities make such patterns unlikely. Each key receives a priority independently of its position in key order, and the heap rule uses those priorities to determine which nodes rise toward the root.

A useful interpretation is that priorities create a random ranking of the nodes. Among a fixed set of keys, the node with the smallest priority becomes the root of the corresponding Treap. Keys smaller than it belong to the left subtree, and keys larger than it belong to the right subtree. The same process repeats recursively inside both subtrees.

Suppose the keys and priorities are:

key:       10   20   30   40   50
priority:   8    3   11    6    9

The smallest priority is 3, belonging to key 20, so key 20 becomes the root. Key 10 is smaller and therefore belongs in the left subtree. Keys 30, 40, and 50 belong in the right subtree. Among those right-side keys, priority 6 is smallest, so key 40 becomes the root of that subtree.

The resulting shape is:

          (20, 3)
          /      \
      (10, 8)   (40, 6)
                 /    \
             (30, 11) (50, 9)

The shape is simultaneously a BST by key and a min-heap by priority.

Randomness does not make every individual Treap perfectly balanced. It makes a well-behaved shape likely in expectation when priorities are randomized. This distinction matters: randomized balance is probabilistic, not an absolute guarantee for every possible priority assignment.

2.1 Relative priority order determines the shape​

The actual numeric values of priorities are less important than their relative order. If all priorities are replaced by another sequence with the same ordering, the same Treap shape can be produced for the same keys.

For example, these sequences have the same relative order:

8, 3, 11, 6, 9
2, 1, 5, 3, 4

In both sequences, the second item has the smallest priority, the fourth item has the next smallest priority, and so on. With the keys fixed, the resulting Cartesian-style tree shape is therefore the same.

This explains the role of random priorities. They create a random ordering of the nodes. The smallest priority becomes the root, the next suitable priorities become roots of subtrees, and the recursion continues. The BST invariant determines the key ranges of those subtrees, while the heap invariant determines their vertical arrangement.

For distinct keys and distinct priorities, the two invariants determine a unique shape for the set of key-priority pairs. If priorities can tie, the implementation needs a consistent tie-breaking rule.

3. Rotations: Local Shape Changes​

A rotation is the basic operation used to repair a Treap. It changes a small part of the tree while preserving the in-order sequence of keys.

Consider a right rotation. Before the rotation, a node P has a left child Q, and Q has a right subtree B:

        P
       /
      Q
       \
        B

After a right rotation around P, Q moves above P:

      Q
       \
        P
       /
      B

The middle subtree B changes sides. Its keys remain between the keys of Q and P, so the BST invariant is preserved.

A left rotation is the mirror image:

      P
       \
        Q
       /
      B

becomes:

        Q
       /
      P
       \
        B

Again, the middle subtree moves, but the in-order sequence of keys does not change.

3.1 Why rotations preserve sorted order​

Suppose the key ranges satisfy:

keys(Q)<keys(B)<keys(P)\text{keys}(Q) < \text{keys}(B) < \text{keys}(P)

Before a right rotation, the in-order sequence of this portion is:

Q, B, P

After the rotation, the in-order sequence is still:

Q, B, P

Only parent-child relationships have changed. Therefore, a rotation can repair a priority relationship without losing the BST property.

This is the essential reason rotations are useful in search trees. They change height and ancestry locally while retaining sorted order. A Treap uses the direction of a rotation to move a low-priority node upward during insertion or to move a node downward during deletion.

4. Insertion​

Insertion begins exactly like insertion into an ordinary BST. Compare the new key with the current node's key:

  • Move left when the new key is smaller.
  • Move right when the new key is larger.
  • Apply the chosen duplicate-key policy when the keys are equal.

The new node is initially placed at a leaf position. This placement immediately preserves the BST invariant. However, the new priority may be smaller than its parent's priority, violating the min-heap invariant.

The new node is then rotated upward until the heap condition is restored.

4.1 Insertion example​

Start with this valid Treap:

          (40, 5)
         /       \
     (20, 9)    (60, 8)

Insert the new pair:

(30, 3)

The key 30 is smaller than 40 but larger than 20, so it is placed as the right child of (20, 9):

          (40, 5)
         /       \
     (20, 9)    (60, 8)
          \
          (30, 3)

The BST invariant is correct, but the heap invariant is not. Priority 3 is smaller than its parent's priority 9.

A left rotation around (20, 9) moves (30, 3) upward:

          (40, 5)
         /       \
     (30, 3)    (60, 8)
     /
 (20, 9)

Now priority 3 is still smaller than the root priority 5, so another rotation is needed. A right rotation around (40, 5) produces:

            (30, 3)
           /       \
       (20, 9)    (40, 5)
                         \
                         (60, 8)

The key order remains 20, 30, 40, 60, and the priorities now obey the min-heap rule. The new node has risen until its priority is no smaller than the priority of either child.

4.2 Insertion procedure​

A conceptual insertion algorithm has these stages:

  1. Create a node containing the new key and priority.
  2. Follow BST comparisons until reaching the correct leaf position.
  3. Attach the new node as a leaf.
  4. While its priority is smaller than its parent's priority, rotate the node upward.
  5. Stop when the node reaches the root or its parent has a priority no greater than its own.

The rotations are local. There is no need to rebuild the entire tree or recalculate balance information for every node.

4.3 Duplicate keys​

The basic BST rule assumes distinct keys. If duplicate keys are allowed, the implementation must choose a consistent convention. Equal keys might always go to the left, always go to the right, or be represented internally as a pair such as (key, unique identifier).

The exact policy is not the central Treap idea, but consistency is essential. Split, Merge, search, insertion, and deletion must all use the same ordering convention. Otherwise, a duplicate may appear in an unexpected subtree or a boundary operation may place equal keys on the wrong side.

5. Deletion​

Deletion removes a node while preserving both invariants. There are two closely related ways to describe it.

The first approach rotates the target node downward until it becomes a leaf, then removes it. At every step, the rotation direction is selected using the child priorities so that the heap relationship remains valid as the target moves downward.

Suppose the target has two children. The child with the smaller priority should generally be promoted above the target, because that child is the one that belongs higher according to the min-heap rule. If the smaller-priority child is on the left, perform a right rotation. If it is on the right, perform a left rotation. Repeat until the target has at most one child, then continue moving it down or detach it when it becomes a leaf.

5.1 Deletion example​

Consider:

          (30, 4)
         /       \
     (10, 7)    (50, 6)
                /    \
            (40, 9) (70, 8)

Suppose we delete (30, 4). It has two children. The right child has priority 6, and the left child has priority 7, so the right child has the smaller priority. A left rotation around (30, 4) promotes (50, 6):

             (50, 6)
            /       \
        (30, 4)    (70, 8)
        /    \
    (10, 7) (40, 9)

The target is now lower in the tree. It still has two children, so the process continues. The left child has priority 7, while the right child has priority 9; a right rotation promotes (10, 7):

             (50, 6)
            /       \
        (10, 7)    (70, 8)
             \
             (30, 4)
                  \
                  (40, 9)

The target now has one child. Another rotation can move that child above the target, after which the target becomes a leaf and can be removed. The exact intermediate shape depends on the child relationships, but the principle is constant: move the target downward while preserving key ranges and repairing priority order locally.

5.2 Deletion by merging subtrees​

A second description uses the Merge operation. To delete a node, remove it conceptually and combine its left and right subtrees into one Treap. The left subtree contains only smaller keys, and the right subtree contains only larger keys, so they are already separated by key.

Merge joins the two subtrees while maintaining the priority ordering. This approach is especially natural when Split and Merge are already available as primitive operations. In that style, deletion can be viewed as separating the target from the rest and then joining the remaining pieces.

6. Split​

Split divides one Treap into two Treaps according to a key boundary. Given a boundary value xx, one common convention returns:

  • A Treap containing keys less than xx.
  • A Treap containing keys greater than or equal to xx.

Another convention places keys equal to xx in the first result. Both choices are reasonable; the important requirement is to choose one and use it consistently.

Split follows the search path for xx. At a node, compare the node's key with the boundary:

  • If the node belongs on the left side, recursively split its right subtree. The node and its left subtree remain in the left result.
  • If the node belongs on the right side, recursively split its left subtree. The node and its right subtree remain in the right result.

The result is not created by sorting all keys. Split cuts along one search path and reconnects unaffected subtrees as complete pieces.

6.1 Split example​

Start with:

             (40, 5)
            /       \
        (20, 9)    (60, 8)
        /    \     /    \
    (10, 12) (30, 11) (50, 13) (70, 15)

Split at boundary 40, using the convention that the left result contains keys less than 40. The two results represent:

left keys:   10, 20, 30
right keys:  40, 50, 60, 70

The internal shapes may be assembled through recursive reconnection, but each output must still satisfy both Treap invariants. Split therefore preserves more than the key partition: it produces two independently valid Treaps.

Split is useful because it turns a search boundary into a structural operation. Instead of repeatedly searching for individual keys, an algorithm can separate an entire key range at once.

7. Merge​

Merge combines two Treaps into one, subject to a key-separation precondition. Every key in the first Treap must be smaller than every key in the second Treap according to the chosen ordering. Without this condition, no ordinary BST join can safely connect the two structures.

The result must satisfy both:

  1. The BST invariant across the combined key range.
  2. The min-heap invariant across the new root and its descendants.

The root with the smaller priority becomes the root of the merged result. If the first Treap's root has the smaller priority, keep it at the top and recursively merge its right subtree with the second Treap. If the second Treap's root has the smaller priority, keep it at the top and recursively merge the first Treap with its left subtree.

7.1 Merge example​

Suppose the two Treaps are:

left:                 right:
    (20, 4)              (50, 3)
    /    \
 (10, 8) (30, 7)

All keys in the left Treap are smaller than all keys in the right Treap. The right root has priority 3, which is smaller than the left root's priority 4, so (50, 3) becomes the merged root. The remaining merge connects the left Treap with the left subtree of the right Treap.

At each recursive step, the root with smaller priority wins. The other root is connected inside the winning root's appropriate subtree. The key-separation precondition ensures that this recursive connection is valid for the BST invariant.

7.2 Split and Merge as building blocks​

Split and Merge provide a compact way to express many updates:

  • To isolate a key range, split at the lower boundary and then split the remaining part at the upper boundary.
  • To remove a range, split around it, discard the middle result, and merge the two outer results.
  • To insert an already ordered Treap, merge it with neighboring pieces when their key ranges are compatible.
  • To express a structural update, separate the relevant pieces, modify or discard one piece, and reconnect the rest.

These operations are not separate from the BST and heap ideas. They are recursive applications of the same two invariants. Split respects key boundaries, while Merge chooses roots by priority.

8. Why the Operations Preserve the Invariants​

It is useful to verify every operation against both rules separately.

Insertion​

BST placement puts the new key in the correct horizontal position. Rotations preserve the in-order sequence, so the BST invariant remains true. Rotating upward continues until the new priority is no smaller than its parent's priority, restoring the heap condition along the affected path.

Rotation​

A rotation does not change the in-order sequence of keys. Therefore, it preserves the BST invariant. The direction of the rotation is selected to repair a priority violation during insertion or to move a target downward during deletion.

Deletion​

When a target is rotated downward, the subtrees move in a way that preserves their key ranges. Choosing the appropriate child for the next rotation keeps the priority relationship valid around the rotated portion. Once the target is a leaf, removing it cannot create a new connection between unrelated key ranges.

Split​

Split follows one boundary path. Subtrees that are entirely on one side of the boundary can be retained as units. Recursive reconnections preserve key separation and keep each output as a valid Treap.

Merge​

The key-range precondition guarantees that all keys from one input belong before all keys from the other. Choosing the smaller-priority root preserves the heap rule at the new top, and recursion handles the remaining connection.

9. Height and Complexity​

Let the Treap height be hh. A search follows one root-to-leaf path, so its running time is proportional to hh:

Tsearch=O(h)T_{\text{search}} = O(h)

Insertion first follows a search path and then performs rotations along that path. Deletion similarly follows and modifies a path. Split and Merge also recurse through paths whose lengths are controlled by the tree height. Therefore, for a Treap of height hh:

Tsearch=Tinsert=Tdelete=Tsplit=Tmerge=O(h)T_{\text{search}} = T_{\text{insert}} = T_{\text{delete}} = T_{\text{split}} = T_{\text{merge}} = O(h)

If priorities are randomized, the expected shape is balanced in the usual randomized sense, leading to expected logarithmic height for a set of nn nodes. Under that expectation, the corresponding operations have expected complexity:

O(log⁡n)O(\log n)

The word expected matters. Random priorities reduce the likelihood of a long chain, but they do not create a strict per-instance height guarantee. A particular priority assignment can still produce an unusually tall tree.

The storage requirement is linear in the number of nodes:

O(n)O(n)

Each node stores its key, its priority, and links to its children. Additional fields may be used by a specific implementation, but they are not required for the core Treap invariants described here.

10. A Small End-to-End Example​

Consider inserting these key-priority pairs in order:

(40, 5)
(20, 9)
(60, 8)
(30, 3)

After the first three insertions, the tree is:

          (40, 5)
         /       \
     (20, 9)    (60, 8)

The key ordering is correct, and the root priority 5 is smaller than both child priorities.

Now insert (30, 3). BST placement first gives:

          (40, 5)
         /       \
     (20, 9)    (60, 8)
          \
          (30, 3)

The new node violates the heap rule with its parent. A left rotation around (20, 9) gives:

          (40, 5)
         /       \
     (30, 3)    (60, 8)
     /
 (20, 9)

The new node still has priority 3, which is smaller than the root's priority 5. A right rotation around (40, 5) produces:

            (30, 3)
           /       \
       (20, 9)    (40, 5)
                         \
                         (60, 8)

Now inspect both invariants:

  • The in-order keys are 20, 30, 40, 60.
  • Every parent priority is no greater than the priority of its child.

The rotations changed the shape but did not change the sorted sequence. This is the central update pattern of a Treap: place by key, then repair by priority.

11. Practical Implementation Checklist​

When implementing a Treap, keep the following questions explicit.

Define the priority convention​

This article uses a min-heap convention: smaller priorities move upward. A max-heap convention is also possible, but every comparison and rotation decision must use the same convention.

Decide how duplicate keys work​

Choose whether equal keys go consistently left, consistently right, or are represented internally with a tie-breaking component. Do not leave equality behavior implicit. Split and Merge must follow the same decision.

Keep rotations local​

A rotation should update only the relationships involved in the rotated region. The middle subtree must be reattached correctly. Losing that subtree is a common structural error because the visible parent-child change can make the operation look correct even when keys have disappeared from the structure.

Check both invariants after updates​

An in-order traversal checks the key ordering. Parent-child priority checks verify the heap ordering. Testing both catches errors that testing only successful searches may miss.

Treat randomization as a balance mechanism, not a proof of perfection​

Random priorities make balanced shapes likely in expectation. They do not eliminate the possibility of a poor shape for one particular priority assignment. If a reproducible implementation is needed, priorities can be generated from a controlled source while retaining the same structural rules.

State Split's boundary convention​

Clarify whether the left output contains keys less than xx or keys less than or equal to xx. Both conventions are useful, but mixing them causes boundary mistakes when several splits are chained together.

Enforce Merge's key precondition​

Before merging two Treaps, verify that every key in the first lies before every key in the second according to the chosen ordering. Priority comparisons alone cannot repair an invalid key arrangement.

12. A Reliable Way to Reason About Treap Code​

When reviewing or debugging an implementation, inspect operations in a fixed order. First verify the key ranges. For every node, determine which keys are allowed in its left and right subtrees. Then inspect priority relationships only between parents and children.

For a rotation, record the local in-order sequence before the operation and after the operation. If the sequence changes, a pointer was reattached incorrectly. Next compare the priorities at the rotated boundary. The rotation should either remove the insertion violation or move the deletion target downward in the intended direction.

For Split, trace the boundary path and mark which subtrees are entirely less than the boundary and which are entirely greater than or equal to it. Any subtree that does not intersect the boundary path should remain intact. This is both an efficiency principle and a useful correctness check.

For Merge, start by checking the key-separation precondition. If that precondition fails, priority comparisons cannot make the result a valid BST. Once the key ranges are known to be compatible, follow the smaller priority at each pair of roots and verify that recursion continues through the correct side.

These checks reflect the underlying design: keys decide where recursion may go, and priorities decide which root survives at each structural join.

13. The Main Conceptual Takeaway​

A Treap is easiest to understand when its two personalities are kept separate:

  • It behaves like a BST when deciding where keys belong.
  • It behaves like a min-heap when deciding which node should be above another.

Insertion first obeys the BST. Rotations then restore the heap. Deletion moves a node downward until it can be removed, or it replaces the node by merging its two subtrees. Split divides a valid Treap along a key boundary, and Merge joins two key-separated Treaps by priority.

The structure does not need a separate balancing field because priorities provide the vertical ordering. With randomized priorities, the resulting shape is expected to stay shallow, so searches and updates are expected to take logarithmic time while the implementation remains based on ordinary BST navigation and local rotations.

The most reusable way to reason about any Treap operation is to ask two questions:

  1. Does the operation preserve the sorted order of keys?
  2. Does it preserve the heap order of priorities?

If both answers are yes, the result is still a Treap.