Treap (Tree + Heap)

Treap is a unique combination of two well-known data structures: the Binary Search Tree (BST) and the Heap. This combination allows the Treap to maintain both the properties of a BST and the balancing benefits of a heap, making it an efficient tool for many computational tasks.

What is a Treap?

A Treap is a randomized binary search tree that also maintains a heap property based on node priorities. Specifically, it maintains these properties

• Binary Search Tree (BST) property: A tree where the left child of a node has a value less than the node, and the right child has a value greater than the node.
• Heap property: A tree where each node has a value (‘priority’) that is greater than the values of its children (in a max heap) or smaller than the values of its children (in a min heap).

Binary Search Tree and Heap are already discussed in these posts:

• Binary Search Tree in C/C++
• Binary Search Tree in C/C++ [2]
• Heap Data structure | Heap Sort in C++
• C++ Standard Template Library (STL) – [Heap]

In a Treap, we maintain the binary search tree property with respect to the keys and the heap property with respect to the priorities. These properties allow for fast searching (O(logn)), insertion (O(logn)), and deletion (O(logn)) operations. And, unlike AVL or Red-Black trees, Treaps balance themselves probabilistically through randomized priorities.

Why use a Treap?

Treaps have practical applications in areas where both fast searching and frequent modifications (insertions/deletions) are needed. Some examples include:

• Balanced Search Trees: Treaps ensure balanced trees without complex balancing algorithms like in AVL or Red-Black trees.
• Dynamic Ordered Sets: Treaps efficiently maintain a set of elements that can be modified dynamically.
• Priority Queues: Treaps allow you to access the element with the highest priority while also keeping elements in sorted order.
• Randomized Algorithms: The randomness in Treap priorities helps avoid worst-case scenarios, making Treaps useful in randomized algorithms.

Structure of a Treap

A Treap node contains three important elements:

1. Key: used to maintain the binary search tree property.
2. Priority: a random value, used to maintain the heap property.
3. Left and Right Pointers: pointers to the left and right children of the node.

The Treap ensures two properties:

• The binary search tree property: Keys in the left subtree are smaller, and keys in the right subtree are larger.
• The heap property: A node’s priority must be greater than the priority of its children.

Basic Operations of a Treap

1. Insertion: We insert a new node by following the BST insertion rules, and then we restore the heap property by performing rotations.
2. Deletion: We find the node to delete using the BST property and remove it by rotating it downward until it becomes a leaf, then removing it.
3. Search: We search the node with a given ‘key’ and return true if it is present, false otherwise.

Pseudocode

Rotation (for maintaining heap property)

Rotate-Right(y)
    x ← y.left
    T2 ← x.right
    x.right ← y
    y.left ← T2
    return x

Rotate-Left(y)
    x ← y.right
    T2 = x.left
    x.left ← y
    y.right ← T2
    return x

Insertion

Treap-Insert(T, x)
    if T is NULL
        return new node with Key 'x' and random Priority value 'priority'
    if x < T.key
        T.left ← Treap-Insert(T.left, x)
        if T.left.priority > T.priority
            T ← Rotate-Right(T)
    else
        T.right ← Treap-Insert(T.right, x)
        if T.right.priority > T.priority
            T ← Rotate-Left(T)
    return T

Deletion

Treap-Delete(T, x)
    if T is NULL
        return T
    if x < T.key
        T.left ← Treap-Delete(T.left, x)
    else if x > T.key
        T.right ← Treap-Delete(T.right, x)
    else
        if T.left is NULL or T.right is NULL
            temp ← T.left ? T.left : T.right
            free T
            return temp
        else if T.left.priority > T.right.priority
            T ← Rotate-Right(T)
            T.right ← Treap-Delete(T.right, x)
        else
            T ← Rotate-Left(T)
            T.left ← Treap-Delete(T.left, x)
    return T

Search

Treap-Search(T, x)
    if T is NULL
        return false
    if x = T.key
        return true
    else if x < T.key
        return Treap-Search(T.left, x)
    else
        return Treap-Search(T.right, x)

Code Implementation

//
//  main.cpp
//  Treap
//
//  Created by Himanshu on 30/09/24.
//

#include <iostream>
#include <cstdlib>  // For rand()
#include <ctime>    // For random seed

// Node structure for Treap
struct TreapNode {
    int key, priority;
    TreapNode* left;
    TreapNode* right;

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

// Right rotation to maintain heap property
TreapNode* rotateRight(TreapNode* y) {
    TreapNode* x = y->left;
    TreapNode* T2 = x->right;
    x->right = y;
    y->left = T2;
    return x;
}

// Left rotation to maintain heap property
TreapNode* rotateLeft(TreapNode* y) {
    TreapNode* x = y->right;
    TreapNode* T2 = x->left;
    x->left = y;
    y->right = T2;
    return x;
}

// Insert a new node with a given key
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 {
        root->right = insert(root->right, key);
        if (root->right->priority > root->priority)
            root = rotateLeft(root);
    }

    return root;
}

// Delete a node with a given key
TreapNode* deleteNode(TreapNode* root, int key) {
    if (!root)
        return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        if (!root->left) {
            TreapNode* temp = root->right;
            delete root;
            root = temp;
        } else if (!root->right) {
            TreapNode* temp = root->left;
            delete root;
            root = temp;
        } else if (root->left->priority > root->right->priority) {
            root = rotateRight(root);
            root->right = deleteNode(root->right, key);
        } else {
            root = rotateLeft(root);
            root->left = deleteNode(root->left, key);
        }
    }
    
    return root;
}

// Search for a key in the Treap
bool search(TreapNode* root, int key) {
    if (!root)
        return false;
    if (root->key == key)
        return true;
    if (key < root->key)
        return search(root->left, key);
    
    return search(root->right, key);
}

// Inorder traversal to display the Treap
void inorderTraversal(TreapNode* root) {
    if (root) {
        inorderTraversal(root->left);
        std::cout << "Key: " << root->key << " | Priority: " << root->priority << std::endl;
        inorderTraversal(root->right);
    }
}

int main() {
    srand(time(0));  // Seed for random priorities

    TreapNode* root = nullptr;

    // Insert nodes
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);

    std::cout << "Treap Inorder Traversal:\n";
    inorderTraversal(root);

    // Search for a key
    std::cout << "\nSearch for 40: ";
    if (search(root, 40)) std::cout << "Found!\n";
    else std::cout << "Not Found!\n";

    // Delete a key
    root = deleteNode(root, 40);
    std::cout << "\nAfter deleting 40:\n";
    inorderTraversal(root);

    return 0;
}

Output

Treap Inorder Traversal:
Key: 20 | Priority: 1432268860
Key: 30 | Priority: 682686416
Key: 40 | Priority: 66127264
Key: 50 | Priority: 2096479644
Key: 60 | Priority: 1469792575
Key: 70 | Priority: 930239436
Key: 80 | Priority: 985102354

Search for 40: Found!

After deleting 40:
Key: 20 | Priority: 1432268860
Key: 30 | Priority: 682686416
Key: 50 | Priority: 2096479644
Key: 60 | Priority: 1469792575
Key: 70 | Priority: 930239436
Key: 80 | Priority: 985102354

Explanation of the Code

Node Structure
The TreapNode structure holds the key (for BST property), priority (for heap property), and pointers to the left and right children. The priority is assigned randomly to ensure probabilistic balancing.

Insertion

• The node is first inserted as in a binary search tree.
• After insertion, rotations (right or left) are performed to restore the heap property if the priority of the new node is higher than its parent.

Deletion

• To delete a node, we first find the node as in a BST.
• If the node has two children, we rotate it with the child that has the higher priority, and the process is repeated until the node is a leaf and can be removed.

Rotations

• Right Rotation: The node’s left child becomes its parent, maintaining both the heap and BST properties.
• Left Rotation: The node’s right child becomes its parent, similarly preserving both properties.

Search
The search operation is similar to that of a standard binary search tree. We traverse the tree based on the key values, either moving left or right depending on whether the key is smaller or larger than the current node’s key.

Treap is an efficient and simple data structure that combines the best of both binary search trees and heaps. It provides the benefits of efficient search, insert, and delete operations, while avoiding the complexity of strict balancing rules required by other balanced trees. The use of randomized priorities ensures that the tree remains balanced on average, making it a great choice for applications requiring dynamic insertion and deletion with fast lookup times.