# Treap Search

# Treap Search

Treap search looks up a key in a tree that combines two invariants. The keys satisfy the binary search tree order, while each node also stores a random priority that satisfies heap order.

The priority field affects the shape of the tree during insertion and deletion. It does not affect search directly. Search follows only the key ordering, exactly as in an ordinary binary search tree.

## Problem

Given a treap root `root` and a target key `x`, find a node such that

$$
node.key = x
$$

If no such node exists, return null.

## Algorithm

Start at the root. Compare the target with the current node key. Move left when the target is smaller, move right when the target is larger, and stop when the keys are equal.

```text id="n8q3vk"
treap_search(root, x):
    node = root
    while node != null:
        if x == node.key:
            return node
        else if x < node.key:
            node = node.left
        else:
            node = node.right
    return null
```

## Example

```text id="ad6z1p"
          8:10
         /    \
      3:25    12:18
       \        \
       6:40     14:31
```

Each label has the form `key:priority`. The priority values determine the treap shape, but the search for key `6` uses only keys.

| step | node key | comparison | move   |
| ---- | -------: | ---------- | ------ |
| 1    |        8 | 6 < 8      | left   |
| 2    |        3 | 6 > 3      | right  |
| 3    |        6 | equal      | return |

## Correctness

The treap maintains the binary search tree invariant over keys. For any node, all keys in the left subtree are smaller than the node key, and all keys in the right subtree are larger.

At each step, the comparison with the current key selects the only subtree that can contain the target. If the algorithm returns a node, its key equals the target by direct comparison. If the algorithm reaches null, the target is absent from every subtree on the only possible search path, so the tree contains no matching key.

## Complexity

With random priorities, the expected tree height is logarithmic.

| case     | time        |
| -------- | ----------- |
| expected | $O(\log n)$ |
| worst    | $O(n)$      |

Space complexity:

| version   | space  |
| --------- | ------ |
| iterative | $O(1)$ |
| recursive | $O(h)$ |

where $h$ is the height of the treap.

## When to Use

Treap search is useful when you want a simple randomized balanced tree. Treaps are often easier to implement than AVL trees or red black trees because rotations are driven by random priorities rather than many deterministic balance cases.

They are appropriate for dynamic ordered sets and maps when expected logarithmic time is sufficient.

## Implementation

```python id="k1v9ps"
class Node:
    def __init__(self, key, priority):
        self.key = key
        self.priority = priority
        self.left = None
        self.right = None

def treap_search(root, x):
    node = root
    while node is not None:
        if x == node.key:
            return node
        if x < node.key:
            node = node.left
        else:
            node = node.right
    return None
```

```go id="u5nd7r"
type TreapNode struct {
	Key      int
	Priority int
	Left     *TreapNode
	Right    *TreapNode
}

func TreapSearch(root *TreapNode, x int) *TreapNode {
	node := root
	for node != nil {
		if x == node.Key {
			return node
		}
		if x < node.Key {
			node = node.Left
		} else {
			node = node.Right
		}
	}
	return nil
}
```