Senior LevelData Structures & Algorithms
What is a Treap (Tree + Heap) and how does it maintain expected O(log N) height?
ā Interview Prompt: Explain Treap structure, priority-based heap rotations maintaining BST + heap invariants, O(log N) expected operations, and split/merge operations.
A Treap is a randomised BST where each node has:
ā¢
A key (maintains BST ordering).
ā¢
A random priority (maintains Max-Heap ordering).
The dual invariant ensures expected $O(\log N)$ height with high probability (same as random BST).
Operations:
ā¢
Split(k): Split into two treaps with keys < k and ā„ k. $O(\log N)$.
ā¢
Merge(left, right): Merge two treaps maintaining both invariants. $O(\log N)$.
ā¢
Insert = Split + create node + Merge.
ā¢
Delete = Split (isolate node) + Merge children.
Implicit Treap (key = position) acts as a balanced sequence with $O(\log N)$ split/merge ā a powerful alternative to segment trees for sequence operations.
Code Implementation Example
typescript
class TreapNode {
key: number;
priority: number;
left: TreapNode | null = null;
right: TreapNode | null = null;
constructor(key: number) {
this.key = key;
this.priority = Math.random(); // random priority
}
}
function merge(l: TreapNode | null, r: TreapNode | null): TreapNode | null {
if (!l) return r;
if (!r) return l;
if (l.priority > r.priority) { l.right = merge(l.right, r); return l; }
else { r.left = merge(l, r.left); return r; }
}
function split(t: TreapNode | null, k: number): [TreapNode | null, TreapNode | null] {
if (!t) return [null, null];
if (t.key <= k) {
const [l, r] = split(t.right, k);
t.right = l; return [t, r];
} else {
const [l, r] = split(t.left, k);
t.left = r; return [l, t];
}
}š”Treap merge and split operations ā O(log N) expected via random priorities.
šÆ Interview Key Takeaway
Treaps combine BST + heap invariants with random priorities for expected O(log N) height. Split/merge in O(log N) makes Treaps powerful for competitive programming.
#DSA#Treap#Randomised BST#Advanced#Senior
Back to all Data Structures & Algorithms Questionsā