Treap: A Randomized Balanced Binary Tree

A Treap combines two familiar tree ideas into one data structure. It behaves like a binary search tree according to its keys, and it follows a heap property according to a second value called a priority. The name Treap comes from combining tree and heap.

This dual structure is the central idea:

• The key determines whether a node belongs in the left or right subtree.
• The priority determines whether a node is allowed to remain above or below another node.

A valid Treap must satisfy both rules at the same time. The search-tree rule makes ordered operations possible, while the heap rule influences the tree's shape. When priorities are randomized, the resulting shape is balanced in expectation, even though the structure does not explicitly maintain a height, color, or balance factor in the same way as some deterministic balanced trees.

This article explains the Treap's structure and invariants, search, insertion by rotations, deletion, randomized balance, Split and Merge operations, and the related structure known as an Implicit Treap.

1. The shape of a Treap​

Each Treap node stores at least two important values:

key       -- the value used for binary-search ordering
priority  -- the value used for heap ordering

It also contains links to a left child and a right child. A node can be viewed as:

        (key, priority)
          /          \
       left        right

The key and priority have different responsibilities. The key is used when searching for a value. The priority is used when deciding which node should be closer to the root.

For the examples in this article, assume that priorities form a max-heap. That means a parent's priority is greater than the priorities of its children. A min-heap convention works just as well, but every operation must use the same convention.

For example:

             key=8, priority=90
             /                 \
   key=3, priority=40       key=12, priority=70

This is a valid Treap fragment under the max-heap convention:

• The key 3 is smaller than 8, so it is in the left subtree.
• The key 12 is larger than 8, so it is in the right subtree.
• Priority 90 is greater than both 40 and 70, so the heap rule also holds.

The root is therefore determined by two simultaneous facts: its key places it between the two subtrees in sorted order, and its priority makes it dominant over them in the heap order.

2. The binary-search-tree invariant​

The first Treap invariant is the ordinary binary search tree property. For a node with key K:

• Every key in the left subtree is smaller than K.
• Every key in the right subtree is larger than K.

The exact treatment of duplicate keys must be chosen by the implementation. A Treap may reject duplicates, store a count for equal keys in one node, or consistently place equal keys on one side. The important requirement is consistency. Insertion, searching, Split, and Merge must all follow the same equality policy.

The binary-search-tree property gives Treaps their ordered behavior. A search for a target compares it with the current node and then chooses one subtree:

1. If the current node is empty, the target is absent.
2. If the target equals the current key, the search succeeds.
3. If the target is smaller, continue in the left subtree.
4. If the target is larger, continue in the right subtree.

Notice that the priority is not needed for this comparison path. Priority affects the shape of the path, but key comparisons determine the direction of the search.

An in-order traversal visits nodes in this order:

left subtree, node, right subtree

For a valid explicit-key Treap, this traversal produces keys in sorted order. That makes in-order traversal a useful way to inspect or verify the binary-search-tree invariant.

3. The heap-priority invariant​

The second invariant is the heap property. Under the max-heap convention used here, every parent must have a priority greater than the priorities of its children. Under a min-heap convention, every parent must have a smaller priority.

The choice between max-heap and min-heap is not important by itself. What matters is that the choice is applied consistently in:

• Insertion comparisons.
• Rotation decisions.
• Deletion.
• Split and Merge.
• Any invariant-checking code.

The priority is not a replacement for the key. Two nodes can have keys that are very close but priorities that are far apart, or keys that are far apart but priorities that happen to be similar. The two fields represent different orderings.

A useful mental model is that keys define the horizontal order of the nodes, while priorities define their vertical order. In-order traversal must remain sorted by key, and parent-child relationships must remain ordered by priority.

This is also why a Treap can be viewed as a Cartesian tree: the nodes are arranged according to one ordering by key and another ordering by priority. A valid shape must satisfy both orderings simultaneously.

4. Why random priorities help​

A conventional binary search tree can become a chain when keys arrive in an unfortunate order. Inserting already sorted keys is the simplest example. Each new key may be placed below the previous one, creating a shape similar to a linked list.

If the tree has n nodes and is shaped like a chain, search, insertion, and deletion can require work proportional to n. A balanced tree avoids this by keeping root-to-leaf paths short.

A Treap separates the value used for ordering from the value that influences structure. The key still determines where the node belongs in sorted order, but the random priority determines how high that node should appear. A node with a relatively strong priority can rise above nodes inserted earlier, while a node with a weaker priority can remain lower in the tree.

As a result, sorted key insertion does not automatically force a chain. Random priorities create a varied hierarchy of ancestors instead of making the insertion order dictate the entire shape.

The balancing guarantee must be stated carefully:

• A particular priority assignment can still produce a tall tree.
• Random priorities make unfavorable shapes unlikely.
• The expected height and expected path lengths are logarithmic in the number of nodes.

Therefore, the usual complexity description for Treap operations is expected logarithmic time, not unconditional logarithmic time. Randomization improves the expected structure, but it does not make a bad shape impossible.

5. Searching a Treap​

Searching is the same as searching an ordinary binary search tree. Begin at the root and compare the target key with the current node's key.

For example, consider this shape:

          8
           \
            12

To search for 12, compare 12 with 8. Since 12 is larger, move to the right child and find the target.

To search for 3 in a tree rooted at 8, move left because 3 is smaller. At every step, the binary-search-tree invariant guarantees that the other subtree cannot contain the target under the chosen ordering policy.

The running time is proportional to the height of the Treap. With randomized priorities, the expected height is logarithmic, so searches have expected logarithmic running time. An unusually tall random shape still causes a correspondingly long search.

6. Insertion begins with key order​

Insertion has two phases. First, place the new node according to the binary-search-tree rule. Second, repair the heap property if the new priority is better than the priority of its parent.

The first phase is exactly like ordinary binary search tree insertion. Follow key comparisons until an empty child position is reached, then attach the new node there. At this point, the binary-search-tree invariant is valid, but the heap invariant may not be.

Suppose a new node is inserted as the left child of its parent. Under a max-heap convention, if the new node has a greater priority than its parent, the new node must move upward. A right rotation performs that movement:

        P                    N
       / \                  / \
      N   C       ->       A   P
     / \                      / \
    A   B                    B   C

Here N is the child that moves upward, P is its former parent, and A, B, and C are subtrees. The rotation changes parent-child relationships but preserves the in-order sequence.

If the new node is the right child and has a greater priority than its parent, use a left rotation:

      P                         N
     / \                       / \
    A   N          ->          P   C
       / \                   / \
      B   C                 A   B

The direction follows the side on which the child appears:

• A left child that moves above its parent requires a right rotation.
• A right child that moves above its parent requires a left rotation.

7. Rotating upward after insertion​

After the new node is attached as a leaf, compare its priority with its parent. If the heap rule already holds, insertion is complete. If not, rotate the new node above its parent.

The new node may still violate the heap rule with its new parent, so continue checking upward. The process stops when:

• The node becomes the root, or
• Its priority no longer dominates its parent under the chosen heap convention.

This gives a compact description of insertion:

1. Place the key as a binary-search-tree leaf.
2. Rotate the node upward while its priority violates the heap rule.

Consider inserting (6, 80) into this max-heap Treap:

          (8, 90)
          /
       (3, 40)

The key 6 must lie to the right of 3 and to the left of 8:

          (8, 90)
          /
       (3, 40)
          \
          (6, 80)

The new node has priority 80, which is greater than its parent's priority 40. Rotate left around (3, 40):

          (8, 90)
          /
       (6, 80)
       /
    (3, 40)

Now (6, 80) is below (8, 90), whose priority is still greater. The heap property holds, and the in-order key sequence remains 3, 6, 8.

8. Why rotations preserve key order​

Rotations are safe for a search tree because they preserve the in-order sequence of the affected nodes.

Before a right rotation, the local shape is:

        P
       /
      N
     / \
    A   B

Its in-order sequence is:

A, N, B, P

After the rotation, the shape is:

        N
       / \
      A   P
         /
        B

The in-order sequence is still:

A, N, B, P

The middle subtree B is especially important. Before the rotation, it belongs between N and P; after the rotation, it remains between them. The rotation changes the shape without changing the sorted order.

A left rotation follows the same principle in the opposite direction. This lets rotations repair a local priority violation while preserving the binary-search-tree invariant globally.

When implementing a rotation, the most common structural error is mishandling the middle subtree. If it is discarded, nodes are lost. If it is attached on the wrong side, key ordering breaks.

9. Deletion by rotating downward​

Deletion can be implemented by first locating the target node and then rotating it downward until it becomes a leaf. Once it has no children, it can be detached safely.

If the target has two children, choose which child should move above it according to the heap convention. Under a max-heap convention, the child with the larger priority is the natural candidate because it should remain higher in the local heap structure.

The rotation direction depends on the selected child:

• If the selected child is on the left, rotate right.
• If the selected child is on the right, rotate left.

Each rotation moves the target one level lower while preserving the key order. Continue until the target has no children, then remove it.

The process can be summarized as:

1. Search for the target key.
2. If the target has children, rotate a suitable child above it.
3. Repeat until the target is a leaf.
4. Remove the leaf.

The target's key remains in the same relative location throughout the rotations, and the remaining nodes retain their binary-search-tree ordering.

Deletion can also be expressed using Merge. Remove the target node and merge its left and right subtrees. Every key in the left subtree is smaller than the removed key, and every key in the right subtree is larger, so these two subtrees have compatible key ranges for an ordered Merge.

10. Merge: joining compatible Treaps​

Merge combines two Treaps into one, provided their key ranges are ordered. In the simplest form, every key in the first Treap must be smaller than every key in the second Treap.

Under a max-heap priority convention, compare the two roots:

• If the first root has the greater priority, it remains the result root. Recursively merge its right subtree with the second Treap.
• If the second root has the greater priority, it becomes the result root. Recursively merge the first Treap with its left subtree.

Conceptually:

merge(leftTree, rightTree):
    if leftTree is empty:
        return rightTree
    if rightTree is empty:
        return leftTree

    if priority(leftTree.root) > priority(rightTree.root):
        leftTree.root.right = merge(leftTree.root.right, rightTree)
        return leftTree.root
    else:
        rightTree.root.left = merge(leftTree, rightTree.root.left)
        return rightTree.root

The key-range condition makes the recursive links legal. If the first root wins, all keys from the second Treap belong in its right-side range. If the second root wins, all keys from the first Treap belong in its left-side range.

Merge is not simply concatenating pointers. It recursively chooses roots by priority so that the heap invariant is restored throughout the result.

11. Split: dividing a Treap at a boundary​

Split divides one Treap into two Treaps according to a key boundary. One result contains keys on one side of the boundary, and the other contains keys on the other side. The treatment of equality must be specified by the implementation.

For example, one convention for splitting around X is:

• The left result contains keys less than X.
• The right result contains keys greater than or equal to X.

At a node, compare its key with X.

If the node belongs in the left result, its right subtree may contain keys on both sides of the boundary. Recursively split that right subtree, keep the left portion attached to the current node, and return the other portion as the right result.

If the node belongs in the right result, its left subtree may cross the boundary. Recursively split that left subtree, keep the right portion attached to the current node, and return the other portion as the left result.

The operation rearranges child links so that both outputs remain valid Treaps. It is not merely a traversal that collects values into two arrays. The resulting roots and subtrees still obey both the search-tree and heap invariants.

Split is powerful because it isolates an ordered portion without scanning every node. Once a range is separated, it can be modified, removed, or replaced and then joined again with Merge.

12. Using Split and Merge together​

Split and Merge form a convenient language for Treap updates. A common pattern is:

1. Split the tree into useful pieces.
2. Modify or replace one piece.
3. Merge the pieces back together.

To isolate a key interval, split at the lower boundary and then split the upper portion at the upper boundary. The middle result represents the interval. After applying an operation to that middle Treap, merge the pieces in their original key order.

This separates responsibilities clearly:

• Split handles boundaries.
• The local operation handles the selected portion.
• Merge restores one ordered Treap.

The correctness of the final structure depends on the conditions supplied to these operations. Split must use a consistent equality rule, and Merge must receive Treaps whose key ranges can be joined without violating binary-search ordering.

Deletion is a simple example of this design. A target node can be removed, then its two compatible child Treaps can be merged. More complex range operations use the same idea at a larger scale.

13. Explicit-key Treaps and traversal​

In an explicit-key Treap, every node stores the key used for searching. In-order traversal produces those keys in sorted order:

function inorder(node):
    if node is empty:
        return
    inorder(node.left)
    visit(node)
    inorder(node.right)

The traversal provides a simple verification of the search-tree invariant. If the output is not sorted according to the chosen duplicate policy, some operation attached a subtree incorrectly.

A separate heap check should inspect every parent-child pair:

for each node:
    if left child exists:
        verify the heap relation with the left child
    if right child exists:
        verify the heap relation with the right child

Checking both invariants is important. A rotation can preserve priority order while breaking key order, or preserve key order while using an incorrect priority comparison. Testing the invariants independently makes these errors easier to identify.

14. Implicit Treap: replacing keys with positions​

An Implicit Treap uses the same randomized tree idea, but the sequence position acts as the ordering key. The node does not need to store an explicit array index. Instead, positions are derived from subtree sizes.

For every node, maintain:

size(node) = 1 + size(node.left) + size(node.right)

The in-order traversal represents the sequence. For example, a tree whose in-order traversal is:

[A, B, C, D, E]

represents that sequence regardless of which node happens to be the physical root.

The invariants of an Implicit Treap are therefore:

• In-order traversal gives the sequence order.
• Priorities obey the heap property.
• Every stored subtree size is accurate.

The physical shape is still determined by priorities. The difference is that explicit keys are no longer used to navigate to a position. The number of nodes in left subtrees tells the algorithm where a node appears in the logical sequence.

For a node with leftSize = size(node.left), the node comes after leftSize elements within its local subtree. This lets a position-based operation decide whether to recurse left or right.

15. Position-based Split in an Implicit Treap​

Splitting an Implicit Treap usually means splitting after the first k elements. The result is:

left  = first k elements
right = all remaining elements

At each node, calculate:

leftSize = size(node.left)

If the split point lies within the left subtree, recurse into the left child. If the split point lies after the current node, recurse into the right child after accounting for the left subtree and the current node. Reconnect the returned pieces and update sizes on the way back.

Suppose the sequence is:

[A, B, C, D, E]

Splitting after three elements must produce:

left  = [A, B, C]
right = [D, E]

The root need not be C, because the Treap shape is controlled by priorities. Subtree sizes allow the algorithm to find the logical boundary even when the physical root is somewhere else in the sequence.

Every structural change must be followed by a size update. If a child link changes but the affected node retains its old size, later position calculations will use incorrect information.

16. Merge in an Implicit Treap​

Implicit Merge combines two sequence Treaps while preserving their sequence order. If the first tree represents [A, B] and the second represents [C, D], the merged tree represents:

[A, B, C, D]

The priority comparison still chooses which root becomes the result root. The difference is that the ordering condition is positional: every element of the first sequence must remain before every element of the second sequence.

After recursively attaching a subtree, recompute the size of the affected root. A forgotten size update may leave the visible tree looking reasonable while causing later position-based Split operations to navigate incorrectly.

A useful summary is:

priority decides parenthood
subtree size determines position
in-order traversal determines sequence order

This is the same Treap principle with a different interpretation of ordering. Explicit keys identify positions by stored values; Implicit Treaps derive positions from the structure itself.

17. Sequence operations with Implicit Treaps​

Split and Merge make sequence transformations natural. To isolate a contiguous interval, split by its starting position and then split the remaining suffix by the interval length.

For a sequence containing [A, B, C, D, E], isolating [B, C, D] can be described as:

split(root, 1) -> prefix, suffix
split(suffix, 3) -> middle, suffixAfter

The pieces are:

prefix     = [A]
middle     = [B, C, D]
suffixAfter = [E]

An interval can then be removed by merging prefix directly with suffixAfter. A new sequence can be inserted by merging the prefix, the new sequence, and the suffix in order. The same pattern supports many positional updates because the interval is first represented as its own Treap.

The particular operation applied to the middle piece may require additional fields or update rules. The essential contribution of the Implicit Treap is the ability to isolate and reconnect sequence ranges using expected logarithmic path operations.

18. Complexity​

Search, insertion, deletion, Split, and Merge follow paths through the Treap. Their cost is therefore related to the tree height and to the number of recursive levels visited.

With randomized priorities, the expected height is logarithmic in the number of nodes. Consequently, the main operations have expected logarithmic running time. Insertion may rotate a new node several levels upward, and deletion may rotate a target downward, but these movements follow the relevant tree path.

Split and Merge also recurse through boundary paths and priority comparisons rather than scanning every node. Under the randomized balance assumption, a single boundary operation has expected logarithmic cost.

The worst case remains linear if the priorities happen to produce a chain. This is why the accurate statement is expected logarithmic time, with a possible linear-height worst case.

For recursive implementations, auxiliary call-stack usage follows the recursion depth, which is also tied to tree height. In an Implicit Treap, maintaining the size field adds constant work for each affected node. It does not change the expected logarithmic path behavior, but it creates an additional invariant that every update must preserve.

19. Common implementation mistakes​

Mixing heap conventions​

A Treap may use a min-heap or a max-heap, but all operations must use the same rule. If insertion treats larger priorities as better while Merge treats smaller priorities as better, the heap invariant will fail.

Rotating in the wrong direction​

A left child that moves above its parent requires a right rotation. A right child that moves above its parent requires a left rotation. Drawing the local three-subtree pattern is often safer than relying on memory.

Losing the middle subtree​

During a rotation, the middle subtree changes sides. It must be reassigned exactly once. Losing it drops nodes from the structure; attaching it incorrectly breaks the key ordering.

Forgetting size updates​

This mistake is especially serious in an Implicit Treap. After changing children, recompute the node's size. Updates are needed after rotations and after recursive Split or Merge calls.

Ignoring equality rules​

The side that receives a key equal to a Split boundary depends on the chosen convention. Use the same rule for duplicates, searching, insertion, and splitting.

Treating randomization as a guarantee​

Random priorities reduce the likelihood of a bad shape but do not eliminate it. Correct pointer updates and invariant checks remain essential.

20. A practical debugging strategy​

Test the two main properties separately and together. After each small update during development, an invariant checker can verify:

1. The in-order keys obey the binary-search ordering policy.
2. Every parent-child pair obeys the selected heap-priority rule.
3. In an Implicit Treap, every stored size equals one plus the sizes of the children.

Begin with very small examples. Insert a few keys in sorted order, then in reverse order, and then insert a key whose priority should move it several levels upward. Print each node's key, priority, and child links after every update.

For deletion, test a leaf, a node with one child, and a node with two children. For Split and Merge, verify that the in-order outputs of the split results, placed back together, reproduce the original ordered keys or sequence.

For an Implicit Treap, compare every operation with a simple array model. The array does not need to be efficient; it only needs to provide an obvious reference result. After each insertion, deletion, Split, Merge, or interval transformation, compare the in-order traversal with the model sequence.

Small randomized tests are useful because they exercise many different shapes. The expected balance is probabilistic, but correctness is not: every generated shape must still satisfy all relevant invariants.

21. A compact mental model​

A Treap can be remembered through four statements:

1. Keys define sorted order. In-order traversal follows binary-search-tree ordering.
2. Priorities define heap order. Parent priorities dominate child priorities according to the selected convention.
3. Rotations repair local priority violations. They change the shape without changing in-order key order.
4. Random priorities provide expected balance. The tree is usually shallow, although a tall worst-case shape remains possible.

Split and Merge extend this foundation. Split divides a valid Treap at an ordered boundary, while Merge combines compatible Treaps by priority. The same ideas apply to Implicit Treaps, where subtree sizes replace explicit keys as the mechanism for locating sequence positions.

22. Practical takeaways​

When choosing or implementing a Treap, keep the structural responsibilities separate:

• Use keys, or implicit positions, to define what belongs before and after a node.
• Use priorities only for heap ordering and for influencing the tree shape.
• Use rotations to repair local heap violations during insertion or deletion.
• Use Split and Merge when an update is easier to express as separated pieces.
• Maintain every additional field, especially subtree size, after every structural change.
• State whether priorities form a min-heap or max-heap.
• State how duplicate keys and Split equality are handled.
• Describe performance as expected logarithmic under randomized priorities, while acknowledging the possible linear-height worst case.

The power of a Treap comes from its combination of simple rules. The binary-search-tree invariant provides ordered access, the heap invariant controls parenthood, rotations reconcile the two during updates, and random priorities produce good expected balance. Once these foundations are clear, Split and Merge provide a compact way to express richer updates. An Implicit Treap takes the same design one step further by replacing explicit keys with sequence positions derived from subtree sizes.