Randomized Data Structures

Why Randomized Data Structures Matters

Suppose a service maintains changing integer scores. It must insert and remove scores, test membership, and enumerate the scores in ascending order. A sorted array makes searching fast but shifts elements on updates. A plain binary search tree avoids those shifts, yet inserting already sorted keys can produce a chain. A linked list also becomes slow to search as it grows.

Treaps and skip lists use random structural choices to provide efficient dynamic ordered sets. A treap gives each key a random priority and restores a heap order with tree rotations. A skip list gives each key a random tower height, creating sparse express lanes above a sorted linked list. Both preserve exact answers for every valid completed state; randomness affects the shape and running time.

You will trace both structures on the same insertions and deletions, implement them with matching interfaces in three languages, and distinguish expected performance from a worst-case guarantee. The programs support insert, erase, contains, and sorted enumeration. Predecessor, range, rank, and sequence operations are natural extensions, discussed after the core implementation.

Core Concepts and Terminology

The input is a sequence of operations on distinct integer keys. insert(x) returns true only when a new key is added; erase(x) returns true only when an existing key is removed. contains(x) returns membership without changing the structure or consuming randomness. Duplicate insertions and unsuccessful deletions leave both structures and their generator states unchanged.

A treap combines two orders. Its keys satisfy the binary search tree rule: every key in a node's left subtree is smaller, and every key in its right subtree is larger. Its priorities satisfy a min-heap rule: the parent's priority rank is smaller than each child's. Key order determines where searching goes; priority order determines which key rises above its neighbors. Smaller priority values are better in this lesson.

The programs compare priority ranks lexicographically as $(p,s)$, where $p$ is the generated value and $s$ is an increasing insertion serial number. A tie in $p$ is resolved by $s$. Distinct ranks make the treap for a fixed collection of key–rank pairs unique. This structural fact does not make a finite generator equivalent to independent continuous priorities.

A skip list has level $0$, containing every key once, and higher levels containing increasingly sparse subsequences. A node of height $h$ owns forward pointers at levels $0$ through $h-1$. Each pointer leads to the next larger key participating at that level, or to an empty link. A separate head node starts every level; its stored key is never compared, so zero and negative keys remain ordinary data.

With independent fair promotion choices, a tower begins at height $1$, rises after each promotion, and stops at the first nonpromotion:

$$\Pr(h=k)=2^{-k},\qquad \Pr(h\ge k)=2^{-(k-1)},\qquad k\ge1.$$

The diagram separates these random choices from the key-order rules that remain mandatory.

The abstract comparison model permits any consistently ordered keys. To obtain identical typed programs here, use signed $32$-bit integer keys, valid seeds from $1$ through $2147483646$, and operation counts that fit the native counters. Python can represent wider integers, but cross-language examples use the shared domain.

How Randomized Data Structures Works, Step by Step

Treap insertion. Search by key while recording the ancestor path. If the key exists, return false before drawing a priority. Otherwise draw one priority, assign a fresh serial number, and attach the new node as a binary-search-tree leaf. While its rank is smaller than its parent's rank, rotate it above that parent and reconnect the resulting subtree to the grandparent or the root. Stop when heap order is restored.

For a right child promoted by a left rotation, save its left subtree as the old parent's new right subtree. The mirrored rule applies to a left child promoted by a right rotation. These middle subtrees are real data, even when the small insertion example happens to leave them empty.

Treap deletion. Search for the key. If absent, return false. Otherwise rotate the target downward, always promoting its smaller-ranked child when it has two children. Once the target becomes a leaf, detach it. The target may temporarily violate heap order during this internal procedure; after it is removed, all remaining nodes satisfy both orders. No new priorities are drawn.

Skip-list search. Start at the head's highest active level. Move right while the next key is strictly smaller than the target, then drop one level without returning to the head. At level $0$, compare the next key with the target. Stopping before equality also gives the predecessor positions needed for updates.

Skip-list insertion. Record those predecessors and reject an existing key before drawing a height. Start with height $1$ and promote while the next generator output is even. If necessary, extend the head and set the new predecessor entries to the head. At each level in the new tower, set its successor link first, then redirect the predecessor to the new node.

Skip-list deletion. Find the same predecessor array. Redirect every incoming link to the target's successor at that level, then discard the node. Remove empty top head levels while keeping level $0$. Updating only the base list leaves stale upper links.

The following diagram isolates insertion of $25$ into the sample's local treap subtree and its two skip-list levels. The priority ordering is $p(30)\lt p(25)\lt p(20)$.

flowchart TD
    A["Insert key into an ordered set"] --> B{"Treap or skip list?"}
    B -->|Treap| C["Search by key; save ancestors"]
    B -->|Skip list| D["Search top down; save predecessors"]
    C --> E{"Key already present?"}
    D --> E
    E -->|Yes| F["Return false; draw nothing"]
    E -->|No| G{"Chosen structure?"}
    G -->|Treap| H["Draw priority; attach BST leaf"]
    H --> I{"New node outranks parent?"}
    I -->|Yes| J["Rotate up; reconnect subtree"]
    J --> I
    I -->|No| K["Increment size; return true"]
    G -->|Skip list| L["Start tower height at one"]
    L --> M{"Next draw is even?"}
    M -->|Yes| N["Increase tower height"]
    N --> M
    M -->|No| O["Extend head; splice every tower level"]
    O --> K

All traversals and updates in the programs are iterative. This avoids call-stack failure on an unusually deep treap; it does not change the time needed to traverse that treap. The explicit insertion path still uses memory proportional to its length.

Worked Example with a Full Trace

Insert $[40,20,60,10,30,50,70,25]$ into both initially empty structures. Use treap seed $7$ and skip-list seed $11$. Each structure owns its own generator, with state transition

$$s_{t+1}=16807s_t\bmod2147483647.$$

The treap consumes one raw output for each successful insertion. The skip list consumes one output per promotion test, including the final odd output that stops the tower. In the table, E means an even output and O an odd output.

For a numerical replay of every promotion test, the skip generator outputs are $[184877,959744092,669281627,96962003,1847779995,877356698,1111302984,1003974129,1014171624,604778329,469274252,1532401580,301976589,816673462,1262887857]$. These values give tower heights $[1,2,1,1,3,2,3,2]$ in insertion order, totaling $15$ node forward pointers.

The eight panels show the complete treap after each insertion. Orange marks the newly inserted key. The bottom lanes show the final skip list; omitted empty successors terminate each lane.

The final treap has root $40$, height $5$, and three insertion rotations. Its edges, written as parent: left,right with - for an empty child, are 40:10,60, 10:-,30, 30:25,-, 25:20,-, and 60:50,70; the other nodes are leaves. These are tree relationships, not an insertion-order list.

Now try inserting $25$ again. Both structures return false, consume no draws, and retain their layouts. Erase $40$, then $10$, then $25$, and finally absent key $999$:

Both final key sequences are $[20,30,50,60,70]$. The treap has edges 60:50,70, 50:30,-, and 30:20,-, with height $4$. The skip-list lanes are level $2$: $[30,70]$; level $1$: $[20,30,50,70]$; and level $0$: $[20,30,50,60,70]$. The draw counts stay at $8$ and $15$ throughout deletion.

Implementation in Python, C++, and Java

Each panel is a complete runnable program implementing both structures. The treap uses a total priority rank and an explicit ancestor path. The skip list grows its head dynamically and imposes no fixed tower cap. keys() returns sorted keys; height() measures treap height; pointers() counts live data-node forward slots, including slots whose successor is empty and excluding head slots. These diagnostic scans take linear time in the number of nodes and are not part of a normal membership query.

All three programs use the same Park–Miller recurrence, with signed $64$-bit intermediate arithmetic in C++ and Java. Since $16807(P-1)\lt2^{63}$, the state update is safe. The valid nonzero seeds remain in the generator's nonzero state domain. Separate generators ensure that changes in one implementation's random consumption do not alter the other's trace.

The expected-time analysis below assumes independent uniform priority orderings and independent fair promotion choices. This small deterministic generator is used for reproducibility; its consecutive outputs are correlated, and a fixed seed is not a proof of those assumptions. Priority tie-breaking preserves correctness, and an unfavorable sequence can still create a tall structure. The programs are sequential teaching implementations; concurrent access requires a separate synchronization design.

P = 2147483647


class RNG:
    def __init__(self, seed):
        if not 1 <= seed < P:
            raise ValueError("seed must be in 1..2147483646")
        self.state, self.draws = seed, 0

    def next(self):
        self.state = (16807 * self.state) % P
        self.draws += 1
        return self.state


class TNode:
    def __init__(self, key, priority, serial):
        self.key, self.rank = key, (priority, serial)
        self.left = self.right = None


class Treap:
    def __init__(self, seed=7):
        self.rng = RNG(seed)
        self.root, self.n, self.serial, self.rotations = None, 0, 0, 0

    def _replace(self, parent, old, new):
        if parent is None:
            self.root = new
        elif parent.left is old:
            parent.left = new
        else:
            parent.right = new

    def _lift(self, parent, child):
        if parent.left is child:
            parent.left, child.right = child.right, parent
        else:
            parent.right, child.left = child.left, parent
        self.rotations += 1

    def insert(self, key):
        path, node = [], self.root
        while node is not None:
            if key == node.key:
                return False
            path.append(node)
            node = node.left if key < node.key else node.right
        self.serial += 1
        node = TNode(key, self.rng.next(), self.serial)
        parent = path[-1] if path else None
        if parent is None:
            self.root = node
        elif key < parent.key:
            parent.left = node
        else:
            parent.right = node
        while path and node.rank < path[-1].rank:
            parent = path.pop()
            self._lift(parent, node)
            self._replace(path[-1] if path else None, parent, node)
        self.n += 1
        return True

    def erase(self, key):
        parent, node = None, self.root
        while node is not None and node.key != key:
            parent, node = node, node.left if key < node.key else node.right
        if node is None:
            return False
        while node.left is not None or node.right is not None:
            if node.right is None or (node.left is not None and node.left.rank < node.right.rank):
                child = node.left
            else:
                child = node.right
            self._lift(node, child)
            self._replace(parent, node, child)
            parent = child
        self._replace(parent, node, None)
        self.n -= 1
        return True

    def contains(self, key):
        node = self.root
        while node is not None and node.key != key:
            node = node.left if key < node.key else node.right
        return node is not None

    def keys(self):
        result, stack, node = [], [], self.root
        while stack or node is not None:
            while node is not None:
                stack.append(node)
                node = node.left
            node = stack.pop()
            result.append(node.key)
            node = node.right
        return result

    def height(self):
        height, stack = 0, [] if self.root is None else [(self.root, 1)]
        while stack:
            node, depth = stack.pop()
            height = max(height, depth)
            if node.left is not None:
                stack.append((node.left, depth + 1))
            if node.right is not None:
                stack.append((node.right, depth + 1))
        return height


class SNode:
    def __init__(self, key, height):
        self.key, self.next = key, [None] * height


class SkipList:
    def __init__(self, seed=11):
        self.rng, self.head, self.n = RNG(seed), SNode(None, 1), 0

    def _predecessors(self, key):
        update, node = [None] * len(self.head.next), self.head
        for level in range(len(update) - 1, -1, -1):
            while node.next[level] is not None and node.next[level].key < key:
                node = node.next[level]
            update[level] = node
        return update

    def insert(self, key):
        update = self._predecessors(key)
        node = update[0].next[0]
        if node is not None and node.key == key:
            return False
        height = 1
        while self.rng.next() % 2 == 0:
            height += 1
        while len(self.head.next) < height:
            self.head.next.append(None)
            update.append(self.head)
        node = SNode(key, height)
        for level in range(height):
            node.next[level] = update[level].next[level]
            update[level].next[level] = node
        self.n += 1
        return True

    def erase(self, key):
        update = self._predecessors(key)
        node = update[0].next[0]
        if node is None or node.key != key:
            return False
        for level in range(len(node.next)):
            update[level].next[level] = node.next[level]
        while len(self.head.next) > 1 and self.head.next[-1] is None:
            self.head.next.pop()
        self.n -= 1
        return True

    def contains(self, key):
        node = self.head
        for level in range(len(self.head.next) - 1, -1, -1):
            while node.next[level] is not None and node.next[level].key < key:
                node = node.next[level]
        node = node.next[0]
        return node is not None and node.key == key

    def keys(self):
        result, node = [], self.head.next[0]
        while node is not None:
            result.append(node.key)
            node = node.next[0]
        return result

    def pointers(self):
        total, node = 0, self.head.next[0]
        while node is not None:
            total += len(node.next)
            node = node.next[0]
        return total


def fmt(keys):
    return "[" + ",".join(map(str, keys)) + "]"


def main():
    t, s = Treap(), SkipList()
    ok = True
    for key in [40, 20, 60, 10, 30, 50, 70, 25]:
        a, b = t.insert(key), s.insert(key)
        ok = ok and a and b
    print("after inserts = " + fmt(t.keys()))
    print(f"treap height={t.height()}, rotations={t.rotations}")
    print(f"skip levels={len(s.head.next)}, node pointers={s.pointers()}")
    a, b = t.insert(25), s.insert(25)
    print(f"duplicate insert = {int(a)},{int(b)}")
    ok = ok and not a and not b
    for key in [40, 10, 25, 999]:
        a, b = t.erase(key), s.erase(key)
        print(f"erase {key} = {int(a)},{int(b)}")
        ok = ok and a == b == (key != 999)
    print("remaining = " + fmt(t.keys()))
    print(f"contains 25={int(t.contains(25))},{int(s.contains(25))}; 60={int(t.contains(60))},{int(s.contains(60))}")
    print(f"treap height={t.height()}, rotations={t.rotations}")
    print(f"skip levels={len(s.head.next)}, node pointers={s.pointers()}")
    print(f"raw draws treap={t.rng.draws}, skip={s.rng.draws}")
    expected = [20, 30, 50, 60, 70]
    ok = ok and t.keys() == s.keys() == expected and t.n == s.n == 5
    ok = ok and not t.contains(25) and not s.contains(25) and t.contains(60) and s.contains(60)
    print("checks = " + ("PASS" if ok else "FAIL"))


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
const std::int64_t P = 2147483647;
struct RNG {
    std::int64_t state, draws = 0;
    explicit RNG(std::int64_t seed) : state(seed) {
        if (seed < 1 || seed >= P) throw std::invalid_argument("invalid seed");
    }
    std::int64_t next() { state = 16807 * state % P; ++draws; return state; }
};
struct TNode {
    int key; std::pair<std::int64_t, std::uint64_t> rank;
    TNode *left = nullptr, *right = nullptr;
    TNode(int k, std::int64_t p, std::uint64_t serial) : key(k), rank(p, serial) {}
};
class Treap {
    void replace(TNode* parent, TNode* old, TNode* fresh) {
        if (!parent) root = fresh;
        else if (parent->left == old) parent->left = fresh;
        else parent->right = fresh;
    }
    void lift(TNode* parent, TNode* child) {
        if (parent->left == child) { parent->left = child->right; child->right = parent; }
        else { parent->right = child->left; child->left = parent; }
        ++rotations;
    }
public:
    RNG rng; TNode* root = nullptr; int n = 0;
    std::uint64_t serial = 0, rotations = 0;
    explicit Treap(std::int64_t seed = 7) : rng(seed) {}
    Treap(const Treap&) = delete;
    Treap& operator=(const Treap&) = delete;
    ~Treap() {
        std::vector<TNode*> stack;
        if (root) stack.push_back(root);
        while (!stack.empty()) {
            TNode* node = stack.back(); stack.pop_back();
            if (node->left) stack.push_back(node->left);
            if (node->right) stack.push_back(node->right);
            delete node;
        }
    }
    bool insert(int key) {
        std::vector<TNode*> path; TNode* node = root;
        while (node) {
            if (key == node->key) return false;
            path.push_back(node); node = key < node->key ? node->left : node->right;
        }
        ++serial; node = new TNode(key, rng.next(), serial);
        TNode* parent = path.empty() ? nullptr : path.back();
        if (!parent) root = node;
        else if (key < parent->key) parent->left = node;
        else parent->right = node;
        while (!path.empty() && node->rank < path.back()->rank) {
            parent = path.back(); path.pop_back(); lift(parent, node);
            replace(path.empty() ? nullptr : path.back(), parent, node);
        }
        ++n; return true;
    }
    bool erase(int key) {
        TNode *parent = nullptr, *node = root;
        while (node && node->key != key) {
            parent = node; node = key < node->key ? node->left : node->right;
        }
        if (!node) return false;
        while (node->left || node->right) {
            TNode* child = !node->right || (node->left && node->left->rank < node->right->rank) ? node->left : node->right;
            lift(node, child); replace(parent, node, child); parent = child;
        }
        replace(parent, node, nullptr); delete node; --n; return true;
    }
    bool contains(int key) const {
        TNode* node = root;
        while (node && node->key != key) node = key < node->key ? node->left : node->right;
        return node != nullptr;
    }
    std::vector<int> keys() const {
        std::vector<int> result; std::vector<TNode*> stack; TNode* node = root;
        while (node || !stack.empty()) {
            while (node) { stack.push_back(node); node = node->left; }
            node = stack.back(); stack.pop_back(); result.push_back(node->key); node = node->right;
        }
        return result;
    }
    int height() const {
        int answer = 0; std::vector<std::pair<TNode*, int>> stack;
        if (root) stack.emplace_back(root, 1);
        while (!stack.empty()) {
            auto p = stack.back(); stack.pop_back(); answer = std::max(answer, p.second);
            if (p.first->left) stack.emplace_back(p.first->left, p.second + 1);
            if (p.first->right) stack.emplace_back(p.first->right, p.second + 1);
        }
        return answer;
    }
};
struct SNode {
    int key; std::vector<SNode*> next;
    SNode(int k, std::size_t height) : key(k), next(height, nullptr) {}
};
class SkipList {
    std::vector<SNode*> predecessors(int key) const {
        std::vector<SNode*> update(head->next.size()); SNode* node = head;
        for (std::size_t level = update.size(); level-- > 0;) {
            while (node->next[level] && node->next[level]->key < key) node = node->next[level];
            update[level] = node;
        }
        return update;
    }
public:
    RNG rng; SNode* head; int n = 0;
    explicit SkipList(std::int64_t seed = 11) : rng(seed), head(new SNode(0, 1)) {}
    SkipList(const SkipList&) = delete;
    SkipList& operator=(const SkipList&) = delete;
    ~SkipList() {
        SNode* node = head;
        while (node) { SNode* next = node->next[0]; delete node; node = next; }
    }
    bool insert(int key) {
        auto update = predecessors(key); SNode* node = update[0]->next[0];
        if (node && node->key == key) return false;
        std::size_t h = 1;
        while (rng.next() % 2 == 0) ++h;
        while (head->next.size() < h) { head->next.push_back(nullptr); update.push_back(head); }
        node = new SNode(key, h);
        for (std::size_t level = 0; level < h; ++level) {
            node->next[level] = update[level]->next[level]; update[level]->next[level] = node;
        }
        ++n; return true;
    }
    bool erase(int key) {
        auto update = predecessors(key); SNode* node = update[0]->next[0];
        if (!node || node->key != key) return false;
        for (std::size_t level = 0; level < node->next.size(); ++level) update[level]->next[level] = node->next[level];
        while (head->next.size() > 1 && !head->next.back()) head->next.pop_back();
        delete node; --n; return true;
    }
    bool contains(int key) const {
        SNode* node = head;
        for (std::size_t level = head->next.size(); level-- > 0;)
            while (node->next[level] && node->next[level]->key < key) node = node->next[level];
        node = node->next[0]; return node && node->key == key;
    }
    std::vector<int> keys() const {
        std::vector<int> result;
        for (SNode* node = head->next[0]; node; node = node->next[0]) result.push_back(node->key);
        return result;
    }
    std::size_t pointers() const {
        std::size_t total = 0;
        for (SNode* node = head->next[0]; node; node = node->next[0]) total += node->next.size();
        return total;
    }
};
std::string fmt(const std::vector<int>& keys) {
    std::string result = "[";
    for (std::size_t i = 0; i < keys.size(); ++i) { if (i) result += ","; result += std::to_string(keys[i]); }
    return result + "]";
}
int main() {
    Treap t; SkipList s; bool ok = true;
    for (int key : {40, 20, 60, 10, 30, 50, 70, 25}) {
        bool a = t.insert(key), b = s.insert(key); ok = ok && a && b;
    }
    std::cout << "after inserts = " << fmt(t.keys()) << '\n';
    std::cout << "treap height=" << t.height() << ", rotations=" << t.rotations << '\n';
    std::cout << "skip levels=" << s.head->next.size() << ", node pointers=" << s.pointers() << '\n';
    bool a = t.insert(25), b = s.insert(25);
    std::cout << "duplicate insert = " << a << ',' << b << '\n'; ok = ok && !a && !b;
    for (int key : {40, 10, 25, 999}) {
        a = t.erase(key); b = s.erase(key);
        std::cout << "erase " << key << " = " << a << ',' << b << '\n'; ok = ok && a == b && a == (key != 999);
    }
    std::cout << "remaining = " << fmt(t.keys()) << '\n';
    std::cout << "contains 25=" << t.contains(25) << ',' << s.contains(25) << "; 60=" << t.contains(60) << ',' << s.contains(60) << '\n';
    std::cout << "treap height=" << t.height() << ", rotations=" << t.rotations << '\n';
    std::cout << "skip levels=" << s.head->next.size() << ", node pointers=" << s.pointers() << '\n';
    std::cout << "raw draws treap=" << t.rng.draws << ", skip=" << s.rng.draws << '\n';
    std::vector<int> expected = {20, 30, 50, 60, 70};
    ok = ok && t.keys() == expected && s.keys() == expected && t.n == 5 && s.n == 5;
    ok = ok && !t.contains(25) && !s.contains(25) && t.contains(60) && s.contains(60);
    std::cout << "checks = " << (ok ? "PASS" : "FAIL") << '\n';
    return 0;
}

import java.util.ArrayList;
import java.util.ArrayDeque;
import java.util.Arrays;

public class Main {
    static final long P = 2147483647L;
    static class RNG {
        long state, draws;
        RNG(long seed) {
            if (seed < 1 || seed >= P) throw new IllegalArgumentException("invalid seed");
            state = seed;
        }
        long next() { state = 16807L * state % P; ++draws; return state; }
    }
    static class TNode {
        final int key; final long priority, serial;
        TNode left, right;
        TNode(int key, long priority, long serial) { this.key = key; this.priority = priority; this.serial = serial; }
    }
    static boolean less(TNode a, TNode b) {
        return a.priority < b.priority || (a.priority == b.priority && a.serial < b.serial);
    }
    static class Treap {
        final RNG rng; TNode root; int n; long serial, rotations;
        Treap(long seed) { rng = new RNG(seed); }
        void replace(TNode parent, TNode old, TNode fresh) {
            if (parent == null) root = fresh;
            else if (parent.left == old) parent.left = fresh;
            else parent.right = fresh;
        }
        void lift(TNode parent, TNode child) {
            if (parent.left == child) { parent.left = child.right; child.right = parent; }
            else { parent.right = child.left; child.left = parent; }
            ++rotations;
        }
        boolean insert(int key) {
            ArrayList<TNode> path = new ArrayList<>(); TNode node = root;
            while (node != null) {
                if (key == node.key) return false;
                path.add(node); node = key < node.key ? node.left : node.right;
            }
            node = new TNode(key, rng.next(), ++serial);
            TNode parent = path.isEmpty() ? null : path.get(path.size() - 1);
            if (parent == null) root = node;
            else if (key < parent.key) parent.left = node;
            else parent.right = node;
            while (!path.isEmpty() && less(node, path.get(path.size() - 1))) {
                parent = path.remove(path.size() - 1); lift(parent, node);
                replace(path.isEmpty() ? null : path.get(path.size() - 1), parent, node);
            }
            ++n; return true;
        }
        boolean erase(int key) {
            TNode parent = null, node = root;
            while (node != null && node.key != key) {
                parent = node; node = key < node.key ? node.left : node.right;
            }
            if (node == null) return false;
            while (node.left != null || node.right != null) {
                TNode child = node.right == null || (node.left != null && less(node.left, node.right)) ? node.left : node.right;
                lift(node, child); replace(parent, node, child); parent = child;
            }
            replace(parent, node, null); --n; return true;
        }
        boolean contains(int key) {
            TNode node = root;
            while (node != null && node.key != key) node = key < node.key ? node.left : node.right;
            return node != null;
        }
        ArrayList<Integer> keys() {
            ArrayList<Integer> result = new ArrayList<>(); ArrayDeque<TNode> stack = new ArrayDeque<>(); TNode node = root;
            while (node != null || !stack.isEmpty()) {
                while (node != null) { stack.push(node); node = node.left; }
                node = stack.pop(); result.add(node.key); node = node.right;
            }
            return result;
        }
        int height() {
            ArrayDeque<TNode> nodes = new ArrayDeque<>(); ArrayDeque<Integer> depths = new ArrayDeque<>(); int answer = 0;
            if (root != null) { nodes.push(root); depths.push(1); }
            while (!nodes.isEmpty()) {
                TNode node = nodes.pop(); int depth = depths.pop(); answer = Math.max(answer, depth);
                if (node.left != null) { nodes.push(node.left); depths.push(depth + 1); }
                if (node.right != null) { nodes.push(node.right); depths.push(depth + 1); }
            }
            return answer;
        }
    }
    static class SNode {
        final int key; final ArrayList<SNode> next = new ArrayList<>();
        SNode(int key, int height) { this.key = key; for (int i = 0; i < height; ++i) next.add(null); }
    }
    static class SkipList {
        final RNG rng; final SNode head = new SNode(0, 1); int n;
        SkipList(long seed) { rng = new RNG(seed); }
        ArrayList<SNode> predecessors(int key) {
            ArrayList<SNode> update = new ArrayList<>();
            for (int i = 0; i < head.next.size(); ++i) update.add(null);
            SNode node = head;
            for (int level = update.size() - 1; level >= 0; --level) {
                while (node.next.get(level) != null && node.next.get(level).key < key) node = node.next.get(level);
                update.set(level, node);
            }
            return update;
        }
        boolean insert(int key) {
            ArrayList<SNode> update = predecessors(key); SNode node = update.get(0).next.get(0);
            if (node != null && node.key == key) return false;
            int h = 1; while (rng.next() % 2 == 0) ++h;
            while (head.next.size() < h) { head.next.add(null); update.add(head); }
            node = new SNode(key, h);
            for (int level = 0; level < h; ++level) {
                node.next.set(level, update.get(level).next.get(level)); update.get(level).next.set(level, node);
            }
            ++n; return true;
        }
        boolean erase(int key) {
            ArrayList<SNode> update = predecessors(key); SNode node = update.get(0).next.get(0);
            if (node == null || node.key != key) return false;
            for (int level = 0; level < node.next.size(); ++level) update.get(level).next.set(level, node.next.get(level));
            while (head.next.size() > 1 && head.next.get(head.next.size() - 1) == null) head.next.remove(head.next.size() - 1);
            --n; return true;
        }
        boolean contains(int key) {
            SNode node = head;
            for (int level = head.next.size() - 1; level >= 0; --level)
                while (node.next.get(level) != null && node.next.get(level).key < key) node = node.next.get(level);
            node = node.next.get(0); return node != null && node.key == key;
        }
        ArrayList<Integer> keys() {
            ArrayList<Integer> result = new ArrayList<>();
            for (SNode node = head.next.get(0); node != null; node = node.next.get(0)) result.add(node.key);
            return result;
        }
        long pointers() {
            long total = 0;
            for (SNode node = head.next.get(0); node != null; node = node.next.get(0)) total += node.next.size();
            return total;
        }
    }
    static String fmt(ArrayList<Integer> keys) {
        StringBuilder b = new StringBuilder("[");
        for (int i = 0; i < keys.size(); ++i) { if (i > 0) b.append(','); b.append(keys.get(i)); }
        return b.append(']').toString();
    }
    static int bit(boolean b) { return b ? 1 : 0; }
    public static void main(String[] args) {
        Treap t = new Treap(7); SkipList s = new SkipList(11); boolean ok = true;
        for (int key : new int[] {40, 20, 60, 10, 30, 50, 70, 25}) {
            boolean a = t.insert(key), b = s.insert(key); ok = ok && a && b;
        }
        System.out.println("after inserts = " + fmt(t.keys()));
        System.out.println("treap height=" + t.height() + ", rotations=" + t.rotations);
        System.out.println("skip levels=" + s.head.next.size() + ", node pointers=" + s.pointers());
        boolean a = t.insert(25), b = s.insert(25);
        System.out.println("duplicate insert = " + bit(a) + "," + bit(b)); ok = ok && !a && !b;
        for (int key : new int[] {40, 10, 25, 999}) {
            a = t.erase(key); b = s.erase(key);
            System.out.println("erase " + key + " = " + bit(a) + "," + bit(b)); ok = ok && a == b && a == (key != 999);
        }
        System.out.println("remaining = " + fmt(t.keys()));
        System.out.println("contains 25=" + bit(t.contains(25)) + "," + bit(s.contains(25)) + "; 60=" + bit(t.contains(60)) + "," + bit(s.contains(60)));
        System.out.println("treap height=" + t.height() + ", rotations=" + t.rotations);
        System.out.println("skip levels=" + s.head.next.size() + ", node pointers=" + s.pointers());
        System.out.println("raw draws treap=" + t.rng.draws + ", skip=" + s.rng.draws);
        ArrayList<Integer> expected = new ArrayList<>(Arrays.asList(20, 30, 50, 60, 70));
        ok = ok && t.keys().equals(expected) && s.keys().equals(expected) && t.n == 5 && s.n == 5;
        ok = ok && !t.contains(25) && !s.contains(25) && t.contains(60) && s.contains(60);
        System.out.println("checks = " + (ok ? "PASS" : "FAIL"));
    }
}

Run Python 3 directly, compile C++ with g++ -std=c++14 -O2 main.cpp -o randomized, or compile Java 17 or later with javac Main.java and run java Main. Each program prints these fourteen lines, with treap and skip-list boolean results in that order:

• after inserts = [10,20,25,30,40,50,60,70]
• treap height=5, rotations=3
• skip levels=3, node pointers=15
• duplicate insert = 0,0
• erase 40 = 1,1
• erase 10 = 1,1
• erase 25 = 1,1
• erase 999 = 0,0
• remaining = [20,30,50,60,70]
• contains 25=0,0; 60=1,1
• treap height=4, rotations=13
• skip levels=3, node pointers=11
• raw draws treap=8, skip=15
• checks = PASS

Complexity, Correctness, and Invariants

Let $n$ be the current number of keys. For the skip list, let $L$ be the greatest active level count before or after the operation, including a newly sampled tower, and let $h_i$ be each live node's tower height. Bounds below use constant-cost comparisons, pointer accesses, and random draws. Enumeration returns $n$ keys in $\Theta(n)$ time in either structure.

For a treap with distinct independent continuous priorities, the minimum-priority key in any fixed interval is uniformly distributed within that interval. If a target has zero-based sorted rank $r$, a smaller key at rank $j$ is its ancestor exactly when it has minimum priority among ranks $j$ through $r$. Its probability is $1/(r-j+1)$. Summing the left and right ancestor probabilities yields

$$\mathbb E[\operatorname{depth}(r)]=H_{r+1}+H_{n-r}-2=O(\log(n+1)),$$

where $H_k=\sum_{i=1}^k1/i$. This explains expected search cost without assuming that input keys arrive randomly. Treap insertion rotates only along its search path. Deletion combines the left and right subtrees by repeatedly promoting the smaller-ranked child; the corresponding randomized merge path also has expected logarithmic length. Thus search, insertion, and deletion have expected $O(\log(n+1))$ time for a fixed operation sequence under the ideal priority model. A chain remains possible, so their deterministic worst case is $O(n+1)$.

For independent fair skip-list promotions, the tail-sum formula gives

$$\mathbb E[h_i]=\sum_{k\ge1}2^{-(k-1)}=2,\qquad \mathbb E\!\left[\sum_{i=1}^n h_i\right]=2n.$$

The maximum tower height obeys $\Pr(L\ge k)\le\min(1,n2^{-(k-1)})$ for a fixed nonempty set of independently generated live towers. Summing that tail gives expected $O(\log(n+1))$ active levels. In the usual backward search-path analysis, only a constant expected number of horizontal steps is needed per level before reaching a node promoted to the next level. Combining those facts gives expected logarithmic search and update time. Generating and linking one new tower costs an additional expected constant amount.

For a fixed skip-list state, even a very favorable search visits every active level, so its best search cost is $\Theta(L)$ in these programs. A layout with all towers of height $1$ gives linear searching. Conversely, even one ideal tower can be arbitrarily tall: saying merely “worst-case $O(n)$” would omit the uncapped vertical work. A chosen finite height cap changes that worst-case statement and must be included in the analysis.

Treap searches and deletions use constant auxiliary space; insertion uses its explicit path. Skip-list updates use an $O(L)$ predecessor array, while membership uses constant auxiliary space. Diagnostic output allocates the returned list of keys. The link-space bound counts logically live entries; dynamic containers and garbage collectors may retain unused allocated capacity after shrinking or deletion.

To justify a rotation, consider keys in the transferred middle subtree: they lie between the old parent and the promoted child, so they remain in the correct interval after the exchange. The grandparent's link or the root must then point to the promoted child. During deletion, choosing the smaller-ranked child is exactly the root choice for merging the two remaining treaps; repeating it preserves the final heap order once the target disappears.

For skip-list search, the cursor remains the head or a node with key smaller than the target. Moving right never overshoots the target, and dropping a level preserves this fact because upper-level nodes participate at all lower levels. At level $0$, the successor is therefore the first possible matching key. Splicing at every recorded predecessor maintains each level's sorted subsequence.

Correctness is deterministic; expected balance is probabilistic. The standard guarantees apply to fixed, or otherwise suitably randomness-independent, operation sequences. An adversary that observes the shape and selectively removes tall towers or chooses keys from exposed priorities can invalidate the usual distributional argument. Likewise, matching one sample's statistics verifies a replay, not a general running-time theorem.

Variants, Pitfalls, and Optimizations

Deletion exposes two particularly useful mistakes. A skip-list node removed only from level $0$ still has incoming upper links; freeing it in C++ leaves dangling pointers. A treap deletion that promotes the larger-ranked child can leave a heap violation among the survivors. The diagram uses a separate three-key treap with priority ranks $1,2,3$ to isolate that second error.

Practical extensions build on the same invariants:

• Ordered navigation and ranges: search for the first key at least a target, then walk successors. A skip list already has a base-level successor chain. A treap can enumerate a range with an explicit traversal stack; expected setup is logarithmic and reporting $k$ keys costs an additional $O(k)$.
• Order statistics: maintain treap subtree sizes for rank and selection. Update sizes after every rotation and structural change. A skip list needs spans measuring how many base-level nodes each link crosses; tower height alone does not encode rank.
• Split and merge: split a treap by key, then merge treaps whose key ranges do not overlap. These operations lead to implicit treaps, where subtree position replaces an explicit search key, and to sequence editing with carefully maintained lazy metadata.
• Multisets and maps: attach a multiplicity or value instead of creating indistinguishable duplicate-key nodes. Specify whether replacing a value consumes randomness; the set interface here rejects duplicates without drawing.
• Promotion tuning: with independent promotion probability $p$, the expected node height is $1/(1-p)$. Smaller $p$ uses fewer links but increases horizontal search work. Changing $p$ changes the distribution and performance analysis.
• Tower caps: a cap $C$ bounds vertical work and gives search an $O(n+C)$ worst-case bound. Under independent half-promotions, a useful expected upper bound includes $O(C+n/2^{C-1})$; a fixed small cap eventually leaves too many nodes in the top lane. Choose a cap against a supported size range or analyze a resizing policy.
• Persistence and concurrency: persistent treaps copy modified paths; concurrent skip lists require atomic link updates and a safe memory-reclamation protocol. The sequential code's pointer assignments do not provide either feature automatically.

Do not confuse a treap with a heap ordered by its data keys: its priorities and search keys serve different purposes. Do not regenerate a resident node's priority during searches, return to the head after every skip-list level drop, or sample a duplicate's unused height. Each changes either correctness, cost, or the reproducible random stream.

Practice Problems and Real-World Use

Validate the two implementations against an independent reference set after every operation. Check results, sizes, sorted enumeration, duplicates, absent deletions, negative keys, and the smallest and largest signed integer keys. Separately inspect treap key intervals and parent–child priority ranks, and compare every skip-list lane with the subsequence of base nodes whose heights reach it. Membership tests alone can miss broken upper links and orphaned subtrees.

Use sorted, reverse-sorted, alternating-extreme, and random operation streams. Delete the treap root repeatedly, delete the only tallest tower, empty both structures completely, and reinsert removed keys. Inject tied and monotone treap priorities and deliberately tall towers to exercise structural cases that an ordinary seed may rarely generate. Check identical state and draw counts across languages, not just the final key list.

For further reading, see the treap chapter in Open Data Structures and William Pugh's A Skip List Cookbook. Redis's sorted-set documentation gives a practical ordered-data use case; the programs above implement integer sets, without Redis's score/member API or production concurrency behavior.