Treap, Splay Tree & Cartesian Tree Guide

                Mastery target: Level A recognition, progressing toward Level B implementation. You should be able to explain why randomness (Treap), self-adjustment (Splay Tree), and array structure (Cartesian Tree) each substitute for an explicit balance invariant, and implement the core operations of all three.
            

1. Introduction & Motivation

AVL trees and Red-Black trees keep $O(\log n)$ height by enforcing an explicit invariant on every insert and delete: a height difference bound, or a color-and-black-height rule. Enforcing that invariant requires bookkeeping — heights, balance factors, or colors — that must be updated and checked at every node on the path back to the root.

This lesson covers three data structures that reach the same $O(\log n)$-ish behavior a different way: they use randomness or self-adjustment instead of an explicit structural invariant.

Treap — a BST where each node also carries a random priority, and the tree simultaneously maintains BST-order on keys and heap-order on priorities. Randomness alone keeps the expected height logarithmic, with no rebalancing logic at all beyond a few rotations.
Splay Tree — a BST with no balance invariant whatsoever. Instead, every access moves the touched node all the way to the root via a sequence of rotations. No single access is guaranteed fast, but a long sequence of accesses is provably efficient — this is amortized, not worst-case, efficiency.
Cartesian Tree — built directly from an array so that it is simultaneously a min-heap (or max-heap) on values and its inorder traversal recovers the array. It needs no rotations at construction time at all, and it connects binary trees to a completely different problem: range-minimum queries.

All three are still binary search trees underneath. What differs is how they stay shallow enough to be useful.

2. Prerequisites

This lesson deliberately does not re-derive two things you should already have from earlier parts of this series, and links to them instead of repeating them:

BST basics and tree rotation mechanics — read Part 10: BST & Balanced Trees, specifically the AVL Rotations section. Its left_rotate/right_rotate primitives are the exact same local pointer-surgery operations that Treaps and Splay Trees use — only the trigger for calling them changes (a broken heap-order property here, instead of a broken height-balance factor there).
The heap-order property — read Part 11: Heaps, Sorting & Hashing, specifically the Heap Fundamentals section. A Treap layers BST-order (on keys) and heap-order (on priorities) onto the same set of nodes; a Cartesian Tree layers BST-order (on array position) and heap-order (on array value) onto the same nodes. If heap-order feels shaky, that section is the place to firm it up first.

You should also be comfortable with recursive BST insert/search and basic array indexing before continuing.

3. Treap: Core Insight

                Core insight: Give every node two independent labels: its key (for search — BST-order) and a random priority (for shape — heap-order, parent priority ≥ both children's priorities). A tree that is simultaneously valid under both orderings is uniquely determined by the (key, priority) pairs — and because the priorities were assigned independently at random, that unique tree is exactly as balanced, in expectation, as a tree built by inserting the keys in a uniformly random order. Random-order BST insertion is a classical result with expected $O(\log n)$ height, so a Treap gets $O(\log n)$ expected height "for free," with no explicit rebalancing rule at all.

Put differently: instead of an algorithm deciding when to rotate by inspecting heights or colors, the random priorities decide the shape in advance, and rotations are only ever used to restore heap-order after a BST-order-only insert or delete disturbs it — reusing the same rotation primitives from Part 10.

4. Treap: Rotation-Based Insert/Delete

Insert is a normal BST insert (walk down by key) followed by bubbling the new node up with rotations wherever it violates heap-order with its parent — the new node keeps rotating upward until its priority is no longer greater than its parent's. Delete does the reverse: instead of splicing an internal node out directly (which is awkward once it has two children), rotate the node downward — always rotating up whichever child has the higher priority — until it becomes a leaf, then drop it in $O(1)$.

import random

class TreapNode:
    def __init__(self, key):
        self.key = key
        self.priority = random.random()  # independent random priority
        self.left = None
        self.right = None

def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    return x  # new local root

def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    return y  # new local root

def insert(root, key):
    if root is None:
        return TreapNode(key)
    if key < root.key:
        root.left = insert(root.left, key)
        if root.left.priority > root.priority:      # heap-order broken, fix it
            root = rotate_right(root)
    elif key > root.key:
        root.right = insert(root.right, key)
        if root.right.priority > root.priority:
            root = rotate_left(root)
    return root

def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        # Found the node: rotate it down to a leaf, then drop it.
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        if root.left.priority > root.right.priority:
            root = rotate_right(root)
            root.right = delete(root.right, key)
        else:
            root = rotate_left(root)
            root.left = delete(root.left, key)
    return root

def inorder(node):
    return inorder(node.left) + [node.key] + inorder(node.right) if node else []

root = None
for value in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, value)
print("Inorder:", inorder(root))  # [20, 30, 40, 50, 60, 70, 80] regardless of priorities

root = delete(root, 30)
print("After deleting 30:", inorder(root))  # [20, 40, 50, 60, 70, 80]

#include <cstdlib>
#include <iostream>
#include <vector>

struct TreapNode {
    int key, priority;
    TreapNode *left, *right;
    TreapNode(int k) : key(k), priority(rand()), left(nullptr), right(nullptr) {}
};

TreapNode* rotateRight(TreapNode* y) {
    TreapNode* x = y->left;
    y->left = x->right;
    x->right = y;
    return x;
}

TreapNode* rotateLeft(TreapNode* x) {
    TreapNode* y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
}

TreapNode* insert(TreapNode* root, int key) {
    if (!root) return new TreapNode(key);
    if (key < root->key) {
        root->left = insert(root->left, key);
        if (root->left->priority > root->priority) root = rotateRight(root);
    } else if (key > root->key) {
        root->right = insert(root->right, key);
        if (root->right->priority > root->priority) root = rotateLeft(root);
    }
    return root;
}

// remove(), not delete(), since delete is a reserved keyword in C++
TreapNode* remove(TreapNode* root, int key) {
    if (!root) return nullptr;
    if (key < root->key) {
        root->left = remove(root->left, key);
    } else if (key > root->key) {
        root->right = remove(root->right, key);
    } else {
        if (!root->left) return root->right;
        if (!root->right) return root->left;
        if (root->left->priority > root->right->priority) {
            root = rotateRight(root);
            root->right = remove(root->right, key);
        } else {
            root = rotateLeft(root);
            root->left = remove(root->left, key);
        }
    }
    return root;
}

void inorder(TreapNode* node, std::vector<int>& out) {
    if (!node) return;
    inorder(node->left, out);
    out.push_back(node->key);
    inorder(node->right, out);
}

int main() {
    TreapNode* root = nullptr;
    for (int value : {50, 30, 70, 20, 40, 60, 80}) root = insert(root, value);

    std::vector<int> keys;
    inorder(root, keys);
    std::cout << "Inorder:";
    for (int k : keys) std::cout << ' ' << k;
    std::cout << '\n';

    root = remove(root, 30);
    keys.clear();
    inorder(root, keys);
    std::cout << "After deleting 30:";
    for (int k : keys) std::cout << ' ' << k;
    std::cout << '\n';
}

import java.util.*;

class TreapNode {
    int key, priority;
    TreapNode left, right;
    TreapNode(int key, Random rng) {
        this.key = key;
        this.priority = rng.nextInt();
    }
}

public class Treap {
    static TreapNode rotateRight(TreapNode y) {
        TreapNode x = y.left;
        y.left = x.right;
        x.right = y;
        return x;
    }

    static TreapNode rotateLeft(TreapNode x) {
        TreapNode y = x.right;
        x.right = y.left;
        y.left = x;
        return y;
    }

    static TreapNode insert(TreapNode root, int key, Random rng) {
        if (root == null) return new TreapNode(key, rng);
        if (key < root.key) {
            root.left = insert(root.left, key, rng);
            if (root.left.priority > root.priority) root = rotateRight(root);
        } else if (key > root.key) {
            root.right = insert(root.right, key, rng);
            if (root.right.priority > root.priority) root = rotateLeft(root);
        }
        return root;
    }

    static TreapNode delete_(TreapNode root, int key) {
        if (root == null) return null;
        if (key < root.key) {
            root.left = delete_(root.left, key);
        } else if (key > root.key) {
            root.right = delete_(root.right, key);
        } else {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            if (root.left.priority > root.right.priority) {
                root = rotateRight(root);
                root.right = delete_(root.right, key);
            } else {
                root = rotateLeft(root);
                root.left = delete_(root.left, key);
            }
        }
        return root;
    }

    static void inorder(TreapNode node, List<Integer> out) {
        if (node == null) return;
        inorder(node.left, out);
        out.add(node.key);
        inorder(node.right, out);
    }

    public static void main(String[] args) {
        Random rng = new Random(42);
        TreapNode root = null;
        for (int value : new int[]{50, 30, 70, 20, 40, 60, 80}) {
            root = insert(root, value, rng);
        }
        List<Integer> keys = new ArrayList<>();
        inorder(root, keys);
        System.out.println("Inorder: " + keys);

        root = delete_(root, 30);
        keys.clear();
        inorder(root, keys);
        System.out.println("After deleting 30: " + keys);
    }
}

5. Treap: Split and Merge

Because heap-order is enforced by independent random numbers rather than a global shape rule, two Treap operations become almost trivially simple: split(treap, key) — partition one Treap into two Treaps, all keys < key and all keys ≥ key — and merge(left, right) — combine two Treaps, given that every key in left is less than every key in right, into one. Both are $O(\log n)$ expected and recurse on exactly one child at each step.

Why this makes Treap uniquely composable: AVL and Red-Black invariants (height balance, or black-height/color rules) are properties of the entire tree's shape, so splicing two balanced trees together at an arbitrary seam can violate the invariant in ways that need careful, multi-case rebalancing along that seam — it is possible (a "join" algorithm exists for balanced BSTs), but it is genuinely more machinery. A Treap's merge only ever needs to compare the two roots' priorities and recurse; because the priorities are random, the result is a valid, well-balanced Treap automatically. No case analysis, no rebalancing pass.

def split(root, key):
    """Split into (left, right): left has keys < key, right has keys >= key."""
    if root is None:
        return None, None
    if root.key < key:
        left, right = split(root.right, key)
        root.right = left
        return root, right
    else:
        left, right = split(root.left, key)
        root.left = right
        return left, root

def merge(left, right):
    """Merge two treaps; every key in `left` must be < every key in `right`."""
    if left is None:
        return right
    if right is None:
        return left
    if left.priority > right.priority:
        left.right = merge(left.right, right)
        return left
    else:
        right.left = merge(left, right.left)
        return right

# insert/delete rewritten purely in terms of split + merge:
def insert_via_split_merge(root, key):
    left, right = split(root, key)
    return merge(merge(left, TreapNode(key)), right)

def delete_via_split_merge(root, key):
    # Assumes integer keys: split the single node == key into its own tree, drop it.
    left, mid_and_right = split(root, key)
    _, right = split(mid_and_right, key + 1)
    return merge(left, right)

#include <utility>

std::pair<TreapNode*, TreapNode*> split(TreapNode* root, int key) {
    if (!root) return {nullptr, nullptr};
    if (root->key < key) {
        auto [left, right] = split(root->right, key);
        root->right = left;
        return {root, right};
    } else {
        auto [left, right] = split(root->left, key);
        root->left = right;
        return {left, root};
    }
}

TreapNode* merge(TreapNode* left, TreapNode* right) {
    if (!left) return right;
    if (!right) return left;
    if (left->priority > right->priority) {
        left->right = merge(left->right, right);
        return left;
    } else {
        right->left = merge(left, right->left);
        return right;
    }
}

class Pair {
    TreapNode left, right;
    Pair(TreapNode l, TreapNode r) { left = l; right = r; }
}

static Pair split(TreapNode root, int key) {
    if (root == null) return new Pair(null, null);
    if (root.key < key) {
        Pair p = split(root.right, key);
        root.right = p.left;
        return new Pair(root, p.right);
    } else {
        Pair p = split(root.left, key);
        root.left = p.right;
        return new Pair(p.left, root);
    }
}

static TreapNode merge(TreapNode left, TreapNode right) {
    if (left == null) return right;
    if (right == null) return left;
    if (left.priority > right.priority) {
        left.right = merge(left.right, right);
        return left;
    } else {
        right.left = merge(left, right.left);
        return right;
    }
}

6. Treap: Implicit Treap

                Core insight: Drop the explicit key entirely. Instead, store subtree size at every node, and let a node's implicit key be its rank — the number of nodes before it in an inorder traversal. The Treap now represents an array: inorder traversal gives the array in order, and split(root, k) partitions "the first $k$ elements" from "the rest" using sizes instead of key comparisons. This is the classic "array as a balanced tree" technique, and it turns insert-at-index, delete-at-index, and range reversal into $O(\log n)$ operations — none of which a plain array supports better than $O(n)$.

The only new piece of machinery is lazy propagation: to reverse a range in $O(\log n)$ rather than $O(\text{range length})$, mark a node's whole subtree as reversed with a single flag, and only actually swap its two children (pushing the flag one level down) the next time that node is visited.

import random

class ImplicitNode:
    def __init__(self, value):
        self.value = value
        self.priority = random.random()
        self.size = 1
        self.left = None
        self.right = None
        self.reversed = False

def size_of(node):
    return node.size if node else 0

def update(node):
    if node:
        node.size = 1 + size_of(node.left) + size_of(node.right)

def push_down(node):
    if node and node.reversed:
        node.left, node.right = node.right, node.left
        if node.left:
            node.left.reversed ^= True
        if node.right:
            node.right.reversed ^= True
        node.reversed = False

def split(root, k):
    """First k elements (by array position) go left, the rest go right."""
    if root is None:
        return None, None
    push_down(root)
    left_size = size_of(root.left)
    if left_size < k:
        left, right = split(root.right, k - left_size - 1)
        root.right = left
        update(root)
        return root, right
    else:
        left, right = split(root.left, k)
        root.left = right
        update(root)
        return left, root

def merge(left, right):
    if left is None:
        return right
    if right is None:
        return left
    push_down(left)
    push_down(right)
    if left.priority > right.priority:
        left.right = merge(left.right, right)
        update(left)
        return left
    else:
        right.left = merge(left, right.left)
        update(right)
        return right

def insert_at(root, index, value):
    left, right = split(root, index)
    return merge(merge(left, ImplicitNode(value)), right)

def delete_at(root, index):
    left, mid_right = split(root, index)
    _, right = split(mid_right, 1)   # peel off exactly one node at position `index`
    return merge(left, right)

def reverse_range(root, l, r):
    """Reverse the inclusive range [l, r] (0-indexed) in O(log n)."""
    left, mid_right = split(root, l)
    mid, right = split(mid_right, r - l + 1)
    if mid:
        mid.reversed ^= True
    return merge(merge(left, mid), right)

def to_list(node):
    if node is None:
        return []
    push_down(node)
    return to_list(node.left) + [node.value] + to_list(node.right)

root = None
for v in [10, 20, 30, 40, 50]:
    root = insert_at(root, size_of(root), v)   # append at the end
print("Array:", to_list(root))                  # [10, 20, 30, 40, 50]

root = reverse_range(root, 1, 3)
print("After reversing [1,3]:", to_list(root))  # [10, 40, 30, 20, 50]

#include <cstdlib>
#include <iostream>
#include <utility>
#include <vector>

struct ImplicitNode {
    int value, priority, size;
    bool reversed;
    ImplicitNode *left, *right;
    ImplicitNode(int v) : value(v), priority(rand()), size(1), reversed(false), left(nullptr), right(nullptr) {}
};

int sizeOf(ImplicitNode* n) { return n ? n->size : 0; }

void update(ImplicitNode* n) {
    if (n) n->size = 1 + sizeOf(n->left) + sizeOf(n->right);
}

void pushDown(ImplicitNode* n) {
    if (n && n->reversed) {
        std::swap(n->left, n->right);
        if (n->left) n->left->reversed = !n->left->reversed;
        if (n->right) n->right->reversed = !n->right->reversed;
        n->reversed = false;
    }
}

std::pair<ImplicitNode*, ImplicitNode*> split(ImplicitNode* root, int k) {
    if (!root) return {nullptr, nullptr};
    pushDown(root);
    int leftSize = sizeOf(root->left);
    if (leftSize < k) {
        auto [left, right] = split(root->right, k - leftSize - 1);
        root->right = left;
        update(root);
        return {root, right};
    } else {
        auto [left, right] = split(root->left, k);
        root->left = right;
        update(root);
        return {left, root};
    }
}

ImplicitNode* merge(ImplicitNode* left, ImplicitNode* right) {
    if (!left) return right;
    if (!right) return left;
    pushDown(left);
    pushDown(right);
    if (left->priority > right->priority) {
        left->right = merge(left->right, right);
        update(left);
        return left;
    } else {
        right->left = merge(left, right->left);
        update(right);
        return right;
    }
}

ImplicitNode* reverseRange(ImplicitNode* root, int l, int r) {
    auto [left, midRight] = split(root, l);
    auto [mid, right] = split(midRight, r - l + 1);
    if (mid) mid->reversed = !mid->reversed;
    return merge(merge(left, mid), right);
}

void toVector(ImplicitNode* node, std::vector<int>& out) {
    if (!node) return;
    pushDown(node);
    toVector(node->left, out);
    out.push_back(node->value);
    toVector(node->right, out);
}

int main() {
    ImplicitNode* root = nullptr;
    for (int v : {10, 20, 30, 40, 50}) {
        auto [left, right] = split(root, sizeOf(root));
        root = merge(merge(left, new ImplicitNode(v)), right);
    }
    root = reverseRange(root, 1, 3);

    std::vector<int> values;
    toVector(root, values);
    std::cout << "After reversing [1,3]:";
    for (int v : values) std::cout << ' ' << v;
    std::cout << '\n';   // 10 40 30 20 50
}

import java.util.*;

class ImplicitNode {
    int value, priority, size;
    boolean reversed;
    ImplicitNode left, right;
    ImplicitNode(int value, Random rng) {
        this.value = value;
        this.priority = rng.nextInt();
        this.size = 1;
    }
}

class Pair {
    ImplicitNode left, right;
    Pair(ImplicitNode l, ImplicitNode r) { left = l; right = r; }
}

public class ImplicitTreap {
    static int sizeOf(ImplicitNode n) { return n != null ? n.size : 0; }

    static void update(ImplicitNode n) {
        if (n != null) n.size = 1 + sizeOf(n.left) + sizeOf(n.right);
    }

    static void pushDown(ImplicitNode n) {
        if (n != null && n.reversed) {
            ImplicitNode t = n.left; n.left = n.right; n.right = t;
            if (n.left != null) n.left.reversed = !n.left.reversed;
            if (n.right != null) n.right.reversed = !n.right.reversed;
            n.reversed = false;
        }
    }

    static Pair split(ImplicitNode root, int k) {
        if (root == null) return new Pair(null, null);
        pushDown(root);
        int leftSize = sizeOf(root.left);
        if (leftSize < k) {
            Pair p = split(root.right, k - leftSize - 1);
            root.right = p.left;
            update(root);
            return new Pair(root, p.right);
        } else {
            Pair p = split(root.left, k);
            root.left = p.right;
            update(root);
            return new Pair(p.left, root);
        }
    }

    static ImplicitNode merge(ImplicitNode left, ImplicitNode right) {
        if (left == null) return right;
        if (right == null) return left;
        pushDown(left);
        pushDown(right);
        if (left.priority > right.priority) {
            left.right = merge(left.right, right);
            update(left);
            return left;
        } else {
            right.left = merge(left, right.left);
            update(right);
            return right;
        }
    }

    static ImplicitNode reverseRange(ImplicitNode root, int l, int r) {
        Pair a = split(root, l);
        Pair b = split(a.right, r - l + 1);
        if (b.left != null) b.left.reversed = !b.left.reversed;
        return merge(merge(a.left, b.left), b.right);
    }

    static void toList(ImplicitNode node, List<Integer> out) {
        if (node == null) return;
        pushDown(node);
        toList(node.left, out);
        out.add(node.value);
        toList(node.right, out);
    }

    public static void main(String[] args) {
        Random rng = new Random(7);
        ImplicitNode root = null;
        for (int v : new int[]{10, 20, 30, 40, 50}) {
            Pair p = split(root, sizeOf(root));
            root = merge(merge(p.left, new ImplicitNode(v, rng)), p.right);
        }
        root = reverseRange(root, 1, 3);

        List<Integer> values = new ArrayList<>();
        toList(root, values);
        System.out.println("After reversing [1,3]: " + values); // [10, 40, 30, 20, 50]
    }
}

Range rotation (cyclic shift) builds on the same primitive: rotating a range left by $k$ is exactly the classic "reverse the whole range, then reverse each of the two pieces" trick, so it costs three calls to reverse_range — still $O(\log n)$.

7. Splay Tree: Core Insight

Core insight: Maintain no balance invariant at all. Instead, after every search or insert, take the node that was just touched and rotate it all the way up to become the root — a process called splaying. Splaying reuses the exact same left_rotate/right_rotate primitives from AVL Rotations; what's new is only the pattern in which they're chained together (see the next section) and the fact that they run on every access, not just after a height violation.

The payoff: whatever node you just looked up is now at the root, so looking it up again is $O(1)$. A single splay can still cost $O(n)$ in the worst case (a long chain), but no single access can be catastrophically expensive often — and that trade-off is exactly what the amortized analysis in section 9 makes precise.

8. Splay Tree: Splaying Cases

Splaying node x repeats one of three moves, based on x's position relative to its parent and grandparent, until x is the root:

Zig — the parent is already the root. One rotation (left or right, whichever makes x take the parent's place) finishes the splay.
Zig-zig — x and its parent are both left children (or both right children). Rotate the grandparent first, then the parent — same direction twice.
Zig-zag — x is a left child and its parent is a right child (or vice versa). Rotate the parent, then the grandparent — opposite directions.

class SplayNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None

def rotate_right(x):
    y = x.left
    x.left = y.right
    if y.right:
        y.right.parent = x
    y.parent = x.parent
    if x.parent is None:
        pass
    elif x is x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.right = x
    x.parent = y

def rotate_left(x):
    y = x.right
    x.right = y.left
    if y.left:
        y.left.parent = x
    y.parent = x.parent
    if x.parent is None:
        pass
    elif x is x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x
    x.parent = y

def splay(x):
    while x.parent is not None:
        parent, grand = x.parent, x.parent.parent
        if grand is None:
            # Zig: parent is the root, one rotation settles it.
            rotate_right(parent) if x is parent.left else rotate_left(parent)
        elif x is parent.left and parent is grand.left:
            # Zig-zig (left-left)
            rotate_right(grand)
            rotate_right(parent)
        elif x is parent.right and parent is grand.right:
            # Zig-zig (right-right)
            rotate_left(grand)
            rotate_left(parent)
        elif x is parent.left and parent is grand.right:
            # Zig-zag (left then right)
            rotate_right(parent)
            rotate_left(grand)
        else:
            # Zig-zag (right then left)
            rotate_left(parent)
            rotate_right(grand)
    return x  # x is now the root

def find(root, key):
    node, last = root, None
    while node:
        last = node
        if key == node.key:
            return splay(node)
        node = node.left if key < node.key else node.right
    return splay(last) if last else None   # splay the last node visited even on a miss

def insert(root, key):
    if root is None:
        return SplayNode(key)
    node, parent = root, None
    while node:
        parent = node
        if key == node.key:
            return splay(node)   # already present; still splay it to the root
        node = node.left if key < node.key else node.right
    new_node = SplayNode(key)
    new_node.parent = parent
    if key < parent.key:
        parent.left = new_node
    else:
        parent.right = new_node
    return splay(new_node)

struct SplayNode {
    int key;
    SplayNode *left, *right, *parent;
    SplayNode(int k) : key(k), left(nullptr), right(nullptr), parent(nullptr) {}
};

void rotateRight(SplayNode* x) {
    SplayNode* y = x->left;
    x->left = y->right;
    if (y->right) y->right->parent = x;
    y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->left) x->parent->left = y;
        else x->parent->right = y;
    }
    y->right = x;
    x->parent = y;
}

void rotateLeft(SplayNode* x) {
    SplayNode* y = x->right;
    x->right = y->left;
    if (y->left) y->left->parent = x;
    y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->left) x->parent->left = y;
        else x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

SplayNode* splay(SplayNode* x) {
    while (x->parent != nullptr) {
        SplayNode* parent = x->parent;
        SplayNode* grand = parent->parent;
        if (grand == nullptr) {
            if (x == parent->left) rotateRight(parent); else rotateLeft(parent);   // zig
        } else if (x == parent->left && parent == grand->left) {
            rotateRight(grand); rotateRight(parent);                              // zig-zig LL
        } else if (x == parent->right && parent == grand->right) {
            rotateLeft(grand); rotateLeft(parent);                                // zig-zig RR
        } else if (x == parent->left && parent == grand->right) {
            rotateRight(parent); rotateLeft(grand);                               // zig-zag
        } else {
            rotateLeft(parent); rotateRight(grand);                               // zig-zag
        }
    }
    return x;
}

SplayNode* find(SplayNode* root, int key) {
    SplayNode *node = root, *last = nullptr;
    while (node) {
        last = node;
        if (key == node->key) return splay(node);
        node = (key < node->key) ? node->left : node->right;
    }
    return last ? splay(last) : nullptr;
}

class SplayNode {
    int key;
    SplayNode left, right, parent;
    SplayNode(int key) { this.key = key; }
}

public class SplayTree {
    static void rotateRight(SplayNode x) {
        SplayNode y = x.left;
        x.left = y.right;
        if (y.right != null) y.right.parent = x;
        y.parent = x.parent;
        if (x.parent != null) {
            if (x == x.parent.left) x.parent.left = y; else x.parent.right = y;
        }
        y.right = x;
        x.parent = y;
    }

    static void rotateLeft(SplayNode x) {
        SplayNode y = x.right;
        x.right = y.left;
        if (y.left != null) y.left.parent = x;
        y.parent = x.parent;
        if (x.parent != null) {
            if (x == x.parent.left) x.parent.left = y; else x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    static SplayNode splay(SplayNode x) {
        while (x.parent != null) {
            SplayNode parent = x.parent;
            SplayNode grand = parent.parent;
            if (grand == null) {
                if (x == parent.left) rotateRight(parent); else rotateLeft(parent);   // zig
            } else if (x == parent.left && parent == grand.left) {
                rotateRight(grand); rotateRight(parent);                              // zig-zig LL
            } else if (x == parent.right && parent == grand.right) {
                rotateLeft(grand); rotateLeft(parent);                                // zig-zig RR
            } else if (x == parent.left && parent == grand.right) {
                rotateRight(parent); rotateLeft(grand);                               // zig-zag
            } else {
                rotateLeft(parent); rotateRight(grand);                               // zig-zag
            }
        }
        return x;
    }

    static SplayNode find(SplayNode root, int key) {
        SplayNode node = root, last = null;
        while (node != null) {
            last = node;
            if (key == node.key) return splay(node);
            node = (key < node.key) ? node.left : node.right;
        }
        return last != null ? splay(last) : null;
    }
}

Trace: start from the degenerate chain $4 \to 3 \to 2 \to 1$ (each node is the left child of the previous one — the worst possible BST shape), and splay(1):

Step	x, parent, grandparent	Case	Rotations applied	New local root
1	x=1, parent=2, grand=3	Zig-zig (LL)	rotate_right(3), then rotate_right(2)	1 (now a child of 4)
2	x=1, parent=4, grand=none	Zig	rotate_right(4)	1 (whole-tree root)

After both steps, node 1 is the root with 1.right = 4, 4.left = 2, and 2.right = 3 — still a valid BST (inorder is unchanged: 1, 2, 3, 4), just reshaped around the newly accessed node.

9. Splay Tree: Working-Set / Amortized Analysis

A splay tree has no invariant to point to as proof of balance — a single splay really can take $O(n)$ time on an unlucky chain, exactly as the trace above hints at (splaying the deepest node of a chain does not instantly produce a perfectly balanced tree). What Sleator and Tarjan proved is an amortized guarantee: over any sequence of $m$ operations on an $n$-node splay tree, the total cost is $O(m \log n + n \log n)$ — an average of $O(\log n)$ per operation, even though individual operations can be expensive.

The proof uses a potential function $\Phi$ — a single number summarizing "how much rebalancing potential is stored in the tree's current shape," defined (conceptually) as $\Phi(T) = \sum_{v} \log(\text{size of the subtree rooted at } v)$. Splaying an unbalanced node does real rotation work, but it also lowers the potential by roughly the same amount, so the sum of (real work) + (change in potential) — the amortized cost charged to that operation — comes out to $O(\log n)$. This is the same aggregate-style argument used for dynamic array doubling in Algorithm Analysis, just with a cleverer potential function; the full derivation (the "access lemma") is beyond this lesson's scope.

                Working-set intuition: splaying moves an accessed node to the root, which also shortens the path to every node that was on the way there. So the "working set theorem" holds: accessing an item costs $O(\log k)$ amortized, where $k$ is the number of distinct items accessed since that item was last touched. Recently-touched items stay cheap to re-access — exactly the temporal-locality pattern an LRU cache exploits, which is why splay trees are a natural fit for caches and other locality-heavy workloads.

10. Cartesian Tree

                Core insight: Given an array, build a binary tree so that (a) it is a min-heap (or max-heap) on the array's values, and (b) an inorder traversal recovers the array's original order. These two constraints together pin down exactly one tree shape for any array with distinct values, and it can be built in $O(n)$ — no comparisons-based sorting or explicit rotation needed at construction time at all.

The construction keeps a stack of node indices with increasing values from bottom to top (a monotonic stack — the same maintain-and-pop mechanic covered in depth in Monotonic Stacks, Queues & Histogram Problems; this lesson only applies it, it doesn't re-derive the technique). For each new element, pop everything larger off the stack — the last node popped becomes the new element's left child (it was the largest thing smaller elements couldn't beat) — then attach the new element as the right child of whatever remains on top of the stack (or make it the new root if the stack emptied).

class CTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def build_cartesian_tree(arr):
    """Min-heap Cartesian tree: O(n) via a monotonic increasing stack of indices."""
    nodes = [CTNode(v) for v in arr]
    stack = []  # indices whose values increase from bottom to top
    root = 0
    for i in range(len(arr)):
        last_popped = -1
        while stack and arr[stack[-1]] > arr[i]:
            last_popped = stack.pop()
        if stack:
            nodes[stack[-1]].right = nodes[i]
        else:
            root = i
        if last_popped != -1:
            nodes[i].left = nodes[last_popped]
        stack.append(i)
    return nodes[root], nodes

def inorder(node):
    return inorder(node.left) + [node.value] + inorder(node.right) if node else []

arr = [9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5]
root, nodes = build_cartesian_tree(arr)
print("Inorder recovers the array:", inorder(root) == arr)  # True

#include <iostream>
#include <vector>

struct CTNode {
    int value;
    CTNode *left, *right;
    CTNode(int v) : value(v), left(nullptr), right(nullptr) {}
};

CTNode* buildCartesianTree(const std::vector<int>& arr, std::vector<CTNode*>& nodes) {
    int n = arr.size();
    nodes.resize(n);
    for (int i = 0; i < n; ++i) nodes[i] = new CTNode(arr[i]);

    std::vector<int> stack;  // indices with increasing values, bottom to top
    int root = 0;
    for (int i = 0; i < n; ++i) {
        int lastPopped = -1;
        while (!stack.empty() && arr[stack.back()] > arr[i]) {
            lastPopped = stack.back();
            stack.pop_back();
        }
        if (!stack.empty()) {
            nodes[stack.back()]->right = nodes[i];
        } else {
            root = i;
        }
        if (lastPopped != -1) {
            nodes[i]->left = nodes[lastPopped];
        }
        stack.push_back(i);
    }
    return nodes[root];
}

void inorder(CTNode* node, std::vector<int>& out) {
    if (!node) return;
    inorder(node->left, out);
    out.push_back(node->value);
    inorder(node->right, out);
}

int main() {
    std::vector<int> arr{9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5};
    std::vector<CTNode*> nodes;
    CTNode* root = buildCartesianTree(arr, nodes);

    std::vector<int> values;
    inorder(root, values);
    std::cout << "Inorder matches input: " << (values == arr) << '\n';  // 1
}

import java.util.*;

class CTNode {
    int value;
    CTNode left, right;
    CTNode(int value) { this.value = value; }
}

public class CartesianTree {
    static CTNode build(int[] arr, CTNode[] nodes) {
        int n = arr.length;
        for (int i = 0; i < n; i++) nodes[i] = new CTNode(arr[i]);

        Deque<Integer> stack = new ArrayDeque<>();  // increasing values, bottom to top
        int root = 0;
        for (int i = 0; i < n; i++) {
            int lastPopped = -1;
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                lastPopped = stack.pop();
            }
            if (!stack.isEmpty()) {
                nodes[stack.peek()].right = nodes[i];
            } else {
                root = i;
            }
            if (lastPopped != -1) {
                nodes[i].left = nodes[lastPopped];
            }
            stack.push(i);
        }
        return nodes[root];
    }

    static void inorder(CTNode node, List<Integer> out) {
        if (node == null) return;
        inorder(node.left, out);
        out.add(node.value);
        inorder(node.right, out);
    }

    public static void main(String[] args) {
        int[] arr = {9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5};
        CTNode[] nodes = new CTNode[arr.length];
        CTNode root = build(arr, nodes);

        List<Integer> values = new ArrayList<>();
        inorder(root, values);
        boolean matches = true;
        for (int i = 0; i < arr.length; i++) matches &= (values.get(i) == arr[i]);
        System.out.println("Inorder matches input: " + matches);  // true
    }
}

The RMQ connection: because the Cartesian tree recursively places the minimum of a range at the root of that range's subtree, the lowest common ancestor (LCA) of positions $i$ and $j$ in the tree is exactly the position of the minimum value in $arr[i..j]$. So range-minimum query = LCA once the Cartesian tree is built — a classic reduction (used, for example, in the $O(n)$-preprocessing / $O(1)$-query Bender–Farach-Colton RMQ algorithm).

# Illustrative only (not O(1) per query — a real RMQ structure adds an LCA index):
def parent_map(node, parent, out):
    out[id(node)] = parent
    if node.left:
        parent_map(node.left, node, out)
    if node.right:
        parent_map(node.right, node, out)

def path_to_root(node, parents):
    path = []
    while node is not None:
        path.append(id(node))
        node = parents.get(id(node))
    return path

def lca(u, v, root):
    parents = {}
    parent_map(root, None, parents)
    ancestors_of_u = set(path_to_root(u, parents))
    node = v
    while id(node) not in ancestors_of_u:
        node = parents[id(node)]
    return node

i, j = 3, 8   # query range: arr[3..8]
result = lca(nodes[i], nodes[j], root)
print(f"min(arr[{i}..{j}]) =", result.value)  # 1 — matches min(arr[3:9])

The Treap connection: a Cartesian tree is a Treap — the BST key is the element's position in the array (so inorder traversal recovers the array), and the heap priority is the element's actual value instead of an independent random number. When the array's values arrive in an effectively random order, the resulting tree has the same expected $O(\log n)$ height as a Treap; feed it an already-sorted (or adversarially ordered) array, though, and there is no randomness left to rely on — the tree degenerates to a chain, height $O(n)$.

11. Complexity Analysis

                Treap: $O(\log n)$ expected time for search, insert, delete, split, and merge. Worst case is $O(n)$ (an adversarial priority assignment), but that is exponentially unlikely with independent random priorities. Space is $O(n)$.
Splay Tree: $O(\log n)$ amortized time per operation over any sequence of operations; a single operation's worst case is $O(n)$. No extra per-node bookkeeping (no heights, no colors, no priorities) beyond child/parent pointers.
Cartesian Tree: $O(n)$ one-time construction from an array via the monotonic-stack method. Height is $O(\log n)$ on average for randomly-ordered input (equivalent to a Treap), but can degrade to $O(n)$ for adversarial input such as an already-sorted array, since nothing here is randomized unless the input itself is.

            

12. Applications & Alternatives

Where each structure earns its keep

Treap / Implicit Treap: competitive-programming "rope"-style array structures (fast insert/delete/reverse anywhere in a sequence), mergeable ordered sets, persistent data structures (splitting/merging without in-place mutation).
Splay Tree: caches and working-set-sensitive workloads, the classic Unix splay(3) library, LRU-like access patterns, and as the base structure for link-cut trees in advanced graph algorithms.
Cartesian Tree: the RMQ <=> LCA reduction used inside $O(n)$/$O(1)$ range-minimum-query algorithms; also a backbone for treap-style "merge sort tree" and suffix-array-adjacent techniques.
When to prefer AVL/Red-Black instead: when you need a hard worst-case guarantee on every single operation (real-time systems, adversarial inputs) rather than an expected or amortized one.

13. Exercises & Mastery

Easy

Implement search(root, key) for a Treap (plain BST search — priorities don't affect where a key lives, only the tree's shape).

Medium

Using an Implicit Treap, reverse an arbitrary range [l, r] of an array in $O(\log n)$, then verify the result against a naive $O(n)$ array reversal on several random ranges.

Hard

Build a Cartesian tree from an array, then answer a range-minimum query by computing the LCA of the two endpoint nodes. Verify against a naive $O(n)$-per-query linear scan.

Mastery challenge: design an in-memory text editor's "document buffer" using an Implicit Treap: support insert-character-at-cursor, delete-character-at-cursor, and select-and-reverse-a-range, all in $O(\log n)$. State what breaks if two clients edit concurrently (hint: this is the entry point to CRDT-style rope structures).

Review rhythm: tomorrow, redraw the Treap heap-order-plus-BST-order picture and the three splay cases from memory; next week, implement all three structures' core operation (Treap insert, Splay Tree splay, Cartesian tree build) without notes; several weeks later, explain to someone who knows AVL trees why none of these three needs a height or color field.

14. Summary Cheat Sheet

Treap = BST-order on keys + heap-order on random priorities; balance comes from randomness, not an explicit rule.
Treap insert/delete reuse the same rotation primitives as AVL, just triggered by a broken heap-order property instead of a broken height balance.
Treap split/merge are what AVL/Red-Black trees can't do cheaply without extra machinery — that's Treap's signature advantage.
Implicit Treap swaps the key for subtree size/rank, turning the tree into an $O(\log n)$ array (insert/delete/reverse anywhere).
Splay Tree has zero balance invariant; every access splays the touched node to the root via zig / zig-zig / zig-zag.
Splay Tree's guarantee is $O(\log n)$ amortized (via a potential-function argument), not worst-case per operation.
Working-set intuition: recently-touched nodes in a Splay Tree stay cheap to re-access.
Cartesian Tree = min/max-heap on array values + inorder recovers array order; built in $O(n)$ via a monotonic stack.
Cartesian Tree's LCA = RMQ; a Cartesian Tree is literally a Treap with array values standing in for random priorities.

Cookie Consent

Treap, Splay Tree & Cartesian Tree: Randomized and Self-Adjusting Trees

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. Treap: Core Insight

4. Treap: Rotation-Based Insert/Delete

5. Treap: Split and Merge

6. Treap: Implicit Treap

7. Splay Tree: Core Insight

8. Splay Tree: Splaying Cases

9. Splay Tree: Working-Set / Amortized Analysis

10. Cartesian Tree

11. Complexity Analysis

12. Applications & Alternatives

Where each structure earns its keep

13. Exercises & Mastery

Easy

Medium

Hard

14. Summary Cheat Sheet

Cookie Consent

Treap, Splay Tree & Cartesian Tree: Randomized and Self-Adjusting Trees

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. Treap: Core Insight

4. Treap: Rotation-Based Insert/Delete

5. Treap: Split and Merge

6. Treap: Implicit Treap

7. Splay Tree: Core Insight

8. Splay Tree: Splaying Cases

9. Splay Tree: Working-Set / Amortized Analysis

10. Cartesian Tree

11. Complexity Analysis

12. Applications & Alternatives

Where each structure earns its keep

13. Exercises & Mastery

Easy

Medium

Hard

14. Summary Cheat Sheet

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Part 10: BST & Balanced Trees

Monotonic Stacks, Queues & Histogram Problems