Treap / Randomized cartesian tree

Reading time: 20 minutes | Coding time: 10 minutes

Algorithm

Insert operation

Insert operation is done for the whole sequence to build the tree.

1. Create new node with the given key value x and random priority value.
2. Start from root and perform search for x by using key values to perform
    a binary search. When a leaf node is reached, insert new node at the
    leaf. This is basically a binary search tree insertion.
3. Rotate up to make sure heap property is satisfied with respect to
    priority values.

The image above shows insert operation for key 15. Green values in nodes are keys and orange values are priorities. Priority of 8 is assigned to node with key 15 randomly.

Search operation

Search operation is same as search in binary search tree since rotation maintains BST property.

1. Start from root to search for a key x.
2. Compare key of the node. If key is equal to x, return the node.
3. If key is less than x go to right child and repeat step 2.
4. If key is greater than x go to left child and repeat step 2.
5. If key is not equal to x and node has no children, then x is not
    present in tree.

Delete operation

1. Search for the node to be deleted.
2. If the node is at leaf, delete it directly.
3. Otherwise, set the node to lowest priority and perform rotations until
    heap property of tree is satisfied.
4. Delete the node when it is at leaf.

For step 3, if tree is a max heap, set node's priority to negative infinity and 
if tree is a min heap, set priority to infinity.

Complexity

$\bf{Space \hspace{1mm }complexity:}\hspace{1mm} O(N)$

$\bf{Time\hspace{1mm }complexities:}$

• $\bf{Search:} \hspace{1mm} O(log_2{N})$
• $\bf{Insert:} \hspace{1mm} O(log_2{N})$
• $\bf{Delete:} \hspace{1mm} O(log_2{N})$

Implementations

C++ 11

/* 
 * c++ 11 code to construct a Treap. Inorder traversal gives a sorted array.
 */

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

struct Node{
    int key, priority;
    Node *left, *right;
    Node(int x){
        key = x;
        priority = rand() % 10000;
        left = right = NULL;
    }
};

class Treap{
private:
    Node *root;

    Node * rotateLeft(Node *p){
        Node *q = p->right;
        
        p->right = q->left;
        q->left = p;

        return q;
    }

    Node * rotateRight(Node *q){
        Node *p = q->left;

        q->left = p->right;
        p->right = q;

        return p;
    }

     Node * insert(Node *sub_tree, int key){
        // If leaf is reached
        if(sub_tree == NULL)
            return new Node(key);
        
        if(sub_tree->key < key){
            // Run insert for right sub-tree
            sub_tree->right = insert(sub_tree->right, key);

            // Check if right subtree satisfies min-heap property
            if(sub_tree->right->priority < sub_tree->priority){
                // Perform left rotate
                sub_tree = rotateLeft(sub_tree);
                
            }
        }
        else{
            // Run insert for left sub-tree
            sub_tree->left = insert(sub_tree->left, key);

            // Check if left subtree satisfies min-heap property
            if(sub_tree->left->priority < sub_tree->priority){
                // Perform right rotate
                sub_tree = rotateRight(sub_tree);
            }
        }
        return sub_tree;
    }

    Node * search(Node *sub_tree, int key){
        if(sub_tree == NULL)
            return NULL;
        
        if(sub_tree->key == key)
            return sub_tree;
        else if(sub_tree->key < key){
            return(search(sub_tree->right, key));
        }
        else return(search(sub_tree->left, key));
    }

    void inorderTraversal(Node *node){
        if(node == NULL)
            return;
        inorderTraversal(node->left);
        std::cout << node->key << ' ';
        inorderTraversal(node->right);
    }
public:
    Treap(){
        root = NULL;
    }

    void insert(int x){
        root = insert(root, x);
    }

    void Search(int x){
        Node *temp = search(root, x);
        if(temp == NULL)
            std::cout << "Key not found\n";
        else
            std::cout << "Key found with priority " << temp->priority
                      << '\n';
    }

    void inorderTraversal(){
        inorderTraversal(root);
    }
    
};

int main() {
    std::vector<int> ar = {5, 4, 3, 2, 1};
    Treap tree;
    for(auto x : ar)
        tree.insert(x);
    tree.inorderTraversal();
    std::cout << '\n';
}

Applications

• Treap is used as a self balancing binary tree.
• Treap is used to solve connectivity problems.

References/ Further reading

• Wikipedia article on Treap
• Read about red-black tree: a simpler data structure that does the same task as a treap.