Motivation

  1. Imagine implementing a balanced binary search tree (BST) without needing any rotations.
  2. Now imagine an array where you can:
    • Insert or delete an element at any index in O(log n).
    • Reverse a sub-array in O(log n).
    • Swap two sub-arrays in O(log n).
    This article introduces a powerful implementation — the Treap — that can handle these tasks.

Note: While this article focuses on a Treap implementation, other data structures can achieve similar tasks.

Introduction

The Treap is a binary search tree where each node has a randomly assigned numeric priority. You can learn more from Wikipedia.

Definitions

  1. Right tree (r): All keys are greater than a specific key.
  2. Left tree (l): All keys are less than or equal to a specific key.

Implementation Details

This section outlines a basic Treap implementation with the following operations:

  1. Split: Given a tree and key, returns two trees l and r.
  2. Insert: Inserts a node into the tree.
  3. Merge: Combines two trees (l and r) back into one.
  4. Erase: Removes a key from the tree.
  5. Reverse: Swaps the left and right children at each node in the tree.

Data Structure


struct Node {
    int priority;
    int key;
    Node* l;
    Node* r;

    Node() : priority(0), key(0), l(NULL), r(NULL) {}
    Node(int priority, int key) : priority(priority), key(key), l(NULL), r(NULL) {}
};

Each node holds a key (for BST ordering), a priority (for heap ordering), and pointers to its left (l) and right (r) subtrees. Use a random number generator, like rand() in C++, for priority values.

Split Function


void split(Node* root, int key, Node*& l, Node*& r) {
    if (!root)
        l = r = NULL;
    else if (key < root->key) {
        r = root;
        split(root->l, key, l, root->l);
    } else {
        l = root;
        split(root->r, key, root->r, r);
    }
}

The split function divides the tree into two: nodes ≤ key go to l, and nodes > key go to r.

Insert Function


Node* insert(Node* root, Node* node) {
    if (!root)
        return node;
    if (node->priority > root->priority) {
        split(root, node->key, node->l, node->r);
        return node;
    }
    if (node->key < root->key)
        root->l = insert(root->l, node);
    else
        root->r = insert(root->r, node);
    return root;
}

The insert function finds the right spot for a node based on priority and key, preserving both BST and heap properties.

Merge Function


void merge(Node*& root, Node* l, Node* r) {
    if (!l || !r)
        root = l ? l : r;
    else if (l->priority > r->priority) {
        root = l;
        merge(root->r, l->r, r);
    } else {
        root = r;
        merge(root->l, l, r->l);
    }
}

The merge function combines two trees into one, respecting the heap priority rules.

Erase Function


void erase(Node*& root, int key) {
    if (!root)
        return;
    if (root->key == key)
        merge(root, root->l, root->r);
    else if (key < root->key)
        erase(root->l, key);
    else
        erase(root->r, key);
}

To erase a node, find it and merge its left and right subtrees.

References

  • 2016 Camp at 72B El Manial Street (explained by Coach Fegla).
  • E-maxx.ru (implementation details in Russian).