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.

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

        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

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

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
}