Randomized Search Trees (Treap, RST)

Abstract

A Randomized Search Tree (RST) is a specialized Treap structure where priorities are randomly generated upon insertion. This application of randomness simulates a completely uniform random insertion sequence, successfully securing an $O(\log n)$ average-case time complexity across all operations regardless of the actual order in which keys are provided by the user.

• Category: Probabilistic Self-Balancing Tree
• Core Composition: Dual-attribute node tracking mapping a unique search key alongside a priority score.
• Balancing Invariant: Simultaneously maintains binary search tree and max-heap properties.

---

The Treap (Tree + Heap) Core Architecture

A Treap is a binary tree structure where each node explicitly encapsulates two structural attributes: a Key and a Priority. To protect the integrity of the architecture, it must satisfy two data layout properties simultaneously:

1. BST Operational Invariant: The tree is sorted horizontally by keys ($\text{Left}<\text{Node}<\text{Right}$).
2. Heap Operational Invariant: The tree is ordered vertically by node priorities ($\text{Parent Priority}\ge \text{Child Priority}$, operating under max-heap rules).

---

Fundamental Operations

Find(element)

Since a Randomized Search Tree functions as a valid, standard Binary Search Tree, lookups navigate down branches using key comparisons alone, bypassing priority scores entirely.

• Time Complexity: Bounded by tree height: $O(h)$ operations.

Insert(key, priority)

Insertion updates the tree topology through a two-phase lifecycle:

1. BST Insertion Phase: Walk down the branches based solely on key comparisons, appending the new item as a terminal leaf node.
2. Heap Fix Phase (Bubble Up): While the new node’s priority is greater than its parent’s priority, execute tree rotations to move the node up the structure without breaking the underlying left-to-right BST sequence.

Algorithm 46 RST Node Insertion

procedure Insert(key, priority, root)

$node \gets$ PerformBSTInsertion(key, priority, root)

while $node \neq root$and$node.\text{priority} > node.\text{parent}.\text{priority}$ do

if $node == node.\text{parent}.\text{leftChild}$ then

AVLRight($node.\text{parent}$)

else

AVLLeft($node.\text{parent}$)

Remove(key)

1. BST Removal Phase: Trace down the branches to isolate the target node matching the input key.
2. Heap Fix Phase (Trickle Down): If the substitute successor node brought into the position violates the priority hierarchy, run tree rotations to shift it down until max-heap ordering properties are restored.

---

The Structural Tool: Tree Rotations

Rotations are constant-time $O(1)$ pointer-swapping operations that modify the physical layout of tree branches while preserving the relative left-to-right sorted sequence of the keys.

Rotation Style	Operational Description	Trigger Condition
Right Rotation	Promotes a left child into its parent’s structural position.	Triggered when a left child node registers a higher priority score than its parent.
Left Rotation	Promotes a right child into its parent’s structural position.	Triggered when a right child node registers a higher priority score than its parent.
RST Balance Rotations

Algorithm 47 RST Right Rotation

procedure AVLRight(b)

$a \gets b.\text{leftChild}$

$y \gets a.\text{rightChild}$

$p \gets b.\text{parent}$

if $p \neq \text{NULL}$and$b == p.\text{rightChild}$ then

$p.\text{rightChild} \gets a$

else if $p \neq \text{NULL}$and$b == p.\text{leftChild}$ then

$p.\text{leftChild} \gets a$

$a.\text{parent} \gets p$

$b.\text{leftChild} \gets y$

if $y \neq \text{NULL}$ then

$y.\text{parent} \gets b$

$a.\text{rightChild} \gets b$

$b.\text{parent} \gets a$

Algorithm 48 RST Left Rotation

procedure AVLLeft(a)

$b \gets a.\text{rightChild}$

$y \gets b.\text{leftChild}$

$p \gets a.\text{parent}$

if $p \neq \text{NULL}$and$a == p.\text{rightChild}$ then

$p.\text{rightChild} \gets b$

else if $p \neq \text{NULL}$and$a == p.\text{leftChild}$ then

$p.\text{leftChild} \gets b$

$b.\text{parent} \gets p$

$a.\text{rightChild} \gets y$

if $y \neq \text{NULL}$ then

$y.\text{parent} \gets a$

$b.\text{leftChild} \gets a$

$a.\text{parent} \gets b$

---

Why Use Randomness?

In a native, non-balancing BST, introducing sorted data in sorted sequences (such as [1, 2, 3, 4, 5]) causes the nodes to stack into a single linear branch line. This degrades lookups to an expensive $O(n)$ search cost. An RST resolves this sorting risk through a distinct pipeline:

1. Accepts the incoming key value from the input stream.
2. Generates an independent, random priority score from a uniform distribution.
3. Inserts the key-priority pair into the Treap container.

Because the assigned priority weights are randomly distributed, the nodes bubble up into a balanced layout that mimics a standard tree built from a random insertion sequence. This keeps the branch height balanced on average, even if the input keys themselves are sorted or patterned.

---

Performance Complexity Summary

Execution Case	Time Complexity	Structural Behavior Profile
Average-Case	$O(\log n)$	Maintained via randomized priority distributions.
Worst-Case	$O(n)$	Occurs if random priority assignments happen to generate a sorted list layout (statistically rare).

Worst-Case Mitigation

While an RST fixes average-case degradation, its absolute worst-case boundary remains $O(n)$. In real-time production systems where worst-case delays are unacceptable, developers instead select strict, deterministic height-balanced models like the AVL Tree or Red-Black Tree.

---

Related Notes

• Binary Search Tree
• AVL Tree
• Heap
• Red-Black Tree