# Randomized BST Search

# Randomized BST Search

Randomized BST search operates on a binary search tree whose shape is maintained by randomized insertion or rotation rules. The key invariant remains identical to a standard BST, while randomization ensures that the expected height stays logarithmic.

Search uses only key comparisons. Randomization affects structure, not traversal logic.

## Problem

Given a randomized BST with root `root` and a target key `x`, find a node such that

$$
node.key = x
$$

If no such node exists, return null.

## Algorithm

Traverse the tree using comparisons against the current node key.

```text id="z4p7qs"
rbst_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="x8n1cd"
        10
       /  \
      4    15
     / \     \
    2   7     20
```

Search for `7`:

| step | node | comparison | move   |
| ---- | ---- | ---------- | ------ |
| 1    | 10   | 7 < 10     | left   |
| 2    | 4    | 7 > 4      | right  |
| 3    | 7    | equal      | return |

## Correctness

The structure satisfies the binary search ordering invariant. Therefore, each comparison eliminates one subtree entirely and preserves the only valid search path.

Randomization affects balancing but does not change correctness. The algorithm returns a node if and only if a matching key exists.

## Complexity

Randomization ensures that the expected height remains logarithmic.

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

Space complexity:

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

## When to Use

Randomized BST search is suitable when:

* you want simpler balancing logic than AVL or red black trees
* expected performance is sufficient
* implementation simplicity matters

Compared to treaps, randomized BSTs may not store explicit priorities, but achieve similar probabilistic balancing through randomized operations.

## Implementation

```python id="t7xk3n"
def rbst_search(root, x):
    node = root
    while node:
        if x == node.key:
            return node
        elif x < node.key:
            node = node.left
        else:
            node = node.right
    return None
```

```go id="m3q8vr"
func RBSTSearch(root *Node, x int) *Node {
    node := root
    for node != nil {
        if x == node.Key {
            return node
        } else if x < node.Key {
            node = node.Left
        } else {
            node = node.Right
        }
    }
    return nil
}
```