AntInLoop

Treap (Randomized Binary Search Tree)

A Treap combines a BST key with a random heap priority so split and merge run in O(log n) expected time—unlocking implicit-key range reversals, splits, and order statistics in ~30 lines of code.

Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code

Treap (Randomized Binary Search Tree)

A Treap (Tree + Heap) assigns every node a BST key and a random heap priority (prio). Because a BST ordered by key and heap-ordered by random priorities is structurally identical to inserting keys in random order, its expected height is $O(\log n)$—and every operation (insert, erase, split, join, and implicit-key subarray reversal!) reduces to just two tiny recursive primitives: split and merge!

At a Glance

| Operation | Expected Time |

| :--- | :---: |

| split(root, key) / merge(L, R) | $O(\log n)$ |

| insert / erase / kth | $O(\log n)$ |

| Implicit-Key Subarray Cut/Paste/Reverse | $O(\log n)$ |

| Auxiliary Space | $O(n)$ |

---

Practice Problems

Hard

1. Treap split, merge, insert, erase, and $k$-th Smallest

Implement a randomized Treap supporting insert, erase, and kth(k) in $O(\log n)$ expected time.

Approach: split(t, key, l, r) partitions t into keys <= key and > key; merge(l, r) joins two treaps respecting heap priorities. Maintain sz in pull(t) for $O(\log n)$ kth!

<details>

<summary>Show C++ Solution</summary>

#include <cstdint>
#include <iostream>
#include <random>

struct TNode {
    int key, sz = 1;
    uint32_t prio;
    TNode *l = nullptr, *r = nullptr;
    TNode(int k, uint32_t p) : key(k), prio(p) {}
};

int sz(TNode* t) { return t ? t->sz : 0; }
void pull(TNode* t) { if (t) t->sz = 1 + sz(t->l) + sz(t->r); }

void split(TNode* t, int key, TNode*& l, TNode*& r) {
    if (!t) { l = r = nullptr; return; }
    if (t->key <= key) { split(t->r, key, t->r, r); l = t; }
    else { split(t->l, key, l, t->l); r = t; }
    pull(t);
}

TNode* merge(TNode* l, TNode* r) {
    if (!l || !r) return l ? l : r;
    if (l->prio > r->prio) { l->r = merge(l->r, r); pull(l); return l; }
    r->l = merge(l, r->l); pull(r); return r;
}

int kth(TNode* t, int k) {
    int ls = sz(t->l);
    if (k == ls + 1) return t->key;
    if (k <= ls) return kth(t->l, k);
    return kth(t->r, k - ls - 1);
}

void freeTreap(TNode* t) { if (!t) return; freeTreap(t->l); freeTreap(t->r); delete t; }

int main() {
    std::mt19937 rng(42);
    TNode* root = nullptr;
    for (int x : {30, 10, 50, 20, 40}) {
        TNode *l = nullptr, *r = nullptr;
        split(root, x, l, r);
        root = merge(merge(l, new TNode(x, rng())), r);
    }
    std::cout << kth(root, 1) << " " << kth(root, 3) << " " << kth(root, 5) << "\n"; // 10 30 50
    freeTreap(root);
    return 0;
}

</details>

---

Related Structures & Algorithms