Treap

Treap is a very useful data structure in computer science, it is used to solve various problems like connectivity problems, range query problems and can be used as good alternatives to segment trees/sparse tables and splay trees in some of the scenerios as they are relatively also easier to code.
It uses randomization of nodes which drives the spontaneous rotations to keep itself balanced in terms of height such that the operations that are performed on Treaps stay efficient in terms of time complexity.

Scope of article

• This article explains the Treap data structure in detail, its construction logic, implementation in C++ programming language, and the idea of tree rotations.
• It also explains some of the basic operations that can be performed on Treaps like Insert, Deletes, and Search along with implementations in the C++ programming language.
• We learn two measures of the efficiency of the above-mentioned operations on Treaps: Time and Space complexity.
• We learn various advantages of using Treap data structure in different domains like connectivity problems, range query problems, etc.
• This article does not compare Treaps with other data structures in detail.

Takeaways

Time Complexities of the different operations in Treap

• Search – O(logN)
• Insert – O(logN)
• Delete – O(logN)

Introduction to Treap

Treap is basically a combination of binary search tree (BST) and Heap. It is also called Cartesian tree or randomized BST.

• In other words, Treap is a binary tree containing only pairs (X, Y) at each node where it is a binary search tree by the parameter X which implies all the left children have X values less than X value of root and all the right children have X values greater than or equal to the X value of the root i.e. (X.left < X <= X.right) which is recursively true for all nodes implies this condition must be satisfied by all nodes of BST.
• It is heap by the parameter Y such that the Y value of the root node is greatest among all its children i.e. (Y.left < Y > Y.right) which is recursively true for all nodes implies this condition must be satisfied by all nodes of BST.
• Randomized binary search trees have a high probability to have a logarithmic height O(logN) where N represents the number of keys in the BST.

In the above tree it can be observed that for all pairs (X, Y) in each node all X values follow a BST property and all Y values follow a Max-heap property.

We will be addressing the questions like why do we need to construct such data structure i.e. the problems with normal binary search tree and how to assign priorities etc and explaining the stepwise thought process in building the Treap data structure.

We shall be explaining the BST structure and its modification into treap, problems that are to be overcome by treap as follows

Binary Search Tree

Highlights:

• Binary search tree contains nodes such that the key of the left child is strictly less than the parent and of a right child is greater than or equal to the parent.
• Each node in a Binary search tree has at most two children.
• There is a requirement of “Prioritizing” the nodes of BST.

Binary search tree also called ordered or sorted binary tree is a rooted binary tree (having at most 2 children for each node) such that the left child stores the key lesser than the root node and the right child stores the key greater than the root key which is recursively valid for all nodes.

Operations like search, insert can be done in O(log N) because at each node one can delete half of the tree based on the comparison and therefore it take logarithmic comparisions to reach the right node (where the element is to be added or deleted).
In this tree there can be multiple arrangements like the same tree as shown above can be represented as a skewed binary search tree (same as a linked list) as shown below:

This type of tree causes the operations i.e. insert, delete to have the complexity as O(n), where n is the number of nodes because one has to traverse over all the nodes in the path to reach the right node which can be the last node in the worst case, for example, suppose we want to add 100 in the tree, so we start from the root node which is 30 < 100.

Therefore, we move to the right, we keep moving right until the value of the node is less than 100 and eventually reach the end of the linked list where this node is added, in the process we need to traverse the entire tree of n nodes which takes O(n) time complexity.

Similar arguments can be made for the deletion operation. These types of trees are called degenerate trees and in such trees, the complexity of the commonly performed operations like search, delete, and insert becomes linear i.e. O(n) instead of staying O(logN) which is inefficient in terms of time complexity.

Hence, by modifying these trees into treaps i.e. prioritized BST, one can solve all these problems in one go which is explained in the next point.

How to Modify Binary Search Tree

Highlights:

• Prioritization of BST helps to keep the tree balanced in terms of height.
• Construction of the Treap must follow the so-called “BST-rule” and “Max-Heap rule“.
• Rotations in the Treap are spontaneously driven because of the prioritization and they do not break the “BST rule“.

To solve the above problems, the tree must balance itself in terms of height upon adding and deletion of nodes so that the cost of these operations stays the same i.e. O(logN) and it does not turn into skewed form, to do so we can prioritize the nodes i.e. set random priority to each node.
For example, assume the nodes which are prioritized randomly below:

Now, while adding the nodes in the tree, they are rotated (tree rotations are explained below) based on the priorities, note that those rotations do not break the rule of the binary search tree.

Start constructing the BST by the following rules:

1.BST Rule: Each left child value is smaller than its parent’s while the right child value is greater than its parent’s.

2. Max Heap rule: Each child priority is smaller than its parent priority

Rotation:
BSTs perform rotations after insertion, deletion in order to balance itself in terms of height, it performs two types of rotations namely left rotation and right rotation without violating the property of a binary search tree.

With respect to the above figure, the different rotations are explained below:

Left rotation:
When a left rotation is performed about node X, then Y becomes the new root of the subtree initially rooted at X, Node X becomes the left child of node Y and subtree B becomes the right child of the node X.

Right rotation:
When a right rotation is performed about node Y, then X becomes the new root of the subtree initially rooted at Y, Node Y becomes the right child of node X and subtree B becomes the left child of the node Y.

Note: The rotation in the tree does not change its BST property.

The stepwise procedure for insertion of a node in treap is as follows:

While inserting a node

1) Walk down comparing values as usual.

2) If the priority of the node is greater than that of its parent, do tree rotations until fixed.

In this way, a treap is constructed as follows:

Basic operations on Treap

Highlights:

• There are many operations that can be performed on Treap like insert, delete, search, etc.
• Prioritization hence balance in height indeed helped to bring the complexity of the above-mentioned operations to O(logN).

Now, after the structure of the Treap is explicit, the next move is to learn the operations that can be performed on it. Although many operations can be performed on a Treap like an insert, delete, search, union, intersection but we will be discussing the basic ones like search, insert and delete

1) Search:

It involves searching a node with a key-value $X$, similarly to BST, the key $X$ is first compared with the root node and if the value of the node says $X0$ is greater than the $X$ then we completely discard the right subtree and search for $X$ in the left subtree else we completely eliminate the left subtree and search for $X$ in the right subtree. we do this recursively until the value $X$ is not found or we reach the end of the tree(leaf node not equal to $X$).
For example: In the Treap given below, we need to search for X = 4, It will be done as follows:

1) Initially, comparing $X$ with root node $2$, $X > 2$ implies we reduce our search space to the right subtree.

2) Compare root of right subtree i.e. $5$ with $X$, $X < 5$ implies we reduce our search space to the left subtree of the current subtree.

3) Compare the root of the left subtree i.e. 4 with $X$, $X == 4$ implies we found the required element.

Same is depicted below:

Time Complexity:
$O(logN)$,Where $N$ are the number of nodes.
Each comparison will reduce the search space to half of the previous one, therefore there will be a total $logN$ comparison which is also the height of the tree i.e. at each level there will be exactly one comparison.

2) Insert:

It involves the insertion of the new node into the tree. To do so one needs to insert a new key $X$ with a random priority $Y$. Then one needs to binary search in the BST to find the right position for $X$, then if the priority of the $X$ i.e. $Y$ is larger than its parent perform tree rotations until all its children have lower priority and ancestors have greater priority as per according to the rotation rule.
For example : In the treap below we need to insert $X = 9$ with priority $Y = 399$, it will be done as follows:

1) Initially, we do the standard Binary search, compare root $2$ with the given $X$ i.e. $X > 2$ implies a move to the right subtree.

2) Compare the root of right subtree $5$ with $X$ i.e. $X > 5$ implies moving further to right subtree.

3) Compare the root of right subtree $7$ with $X$ i.e. $X > 7$ implies moving further to right subtree.

4) Compare the root of the right subtree $8$ with X i.e. $X > 8$ implies move further right but $8$ is the leaf node, hence we must add the $X$ as the right child of $8$.

5) But the priority of the leaf node $8$ is less than $X$ hence, a rotation is performed to balance the nodes according to priorities.

6) Finally, after rotation $8$ is attached as the right child of $X$.

Same is depicted below:

Time Complexity:
O(logN),Where $N$ are the number of nodes.
Each comparison will reduce the search space to half of the previous one, therefore there will be a total $logN$ comparison which is also the height of the tree i.e. at each level there will be exactly one comparison.

3)Delete:

It involves the removal of a node $X$, but the removal of $X$ depends on the type of node $X$ and there are three causes for the type of $X$.

1) if $X$ is a leaf node then simply remove it.

2) If $X$ has one child then remove X and make the child of $X$ as the child of the parent of $X$.

3) If $X$ has two children then find the max of left and right children.

• i) If a left child has a higher priority than the node then perform right rotation at the node.
• ii) If a right child has higher priority than the node then perform left rotation at the node.

In case $3$ we will keep moving down such that it ends up being case 1 or case 2.

For example: In the treap below we need to delete 7

1) Initially, search for the desired node i.e. X = 7 in the BST using the standard binary search procedure.

2) Once, X is found in the tree, we need to check which type of node it is, in this case, it is of the third type i.e. having both children.

3) Therefore, we convert it to case i or case ii. look for the immediate successor Z of X in sorted order and swap it with that. It may violate the heap property, for that rotation are performed to balance the heap property.

Same is depicted as follows:

Time Complexity:
O(logN),Where N are the number of nodes.
Each comparison will reduce the search space to half of the previous one, therefore there will be a total $logN$ comparison which is also the height of the tree i.e. at each level there will be exactly one comparison.

Implementation:

Highlights:

• Implementation of different operations of Treaps like deletion, insertion, search, etc in C++ programming language.
• Brief explanation of working of each operation.

The following implementation of Treap builds the Treap structure from the array of keys X and also implements the basic operations like delete, insert, search which are explained before:

We will be creating a structure of TreapNode which represents the node structure containing the key BST key X, random priority Y, and two pointers left and right pointing to the left and right child of the node.

We will be building the Treap using an array of BST keys X say keys[], where a node is created corresponding to each key and a random priority is assigned to it, then it is inserted at the right position in the tree and make rotations as when required i.e. whenever heap property is violated, note that BST property will never be violated by rotations.

we will also be writing different functions for the different operations like deleteNode, insertNode, searchNode, and printTreap for deleting, inserting, searching and printing the nodes of the treap.

#include<bits/stdc++.h>
using namespace std;

//Treap node
struct TreapNode{
   int data;
   int priority;
   TreapNode* left, *right;

   //Constructor
   TreapNode(int data){
        this->data = data;
        this->priority = rand()%100;
        this->left = this->right = nullptr;
   }
};

//Funtion to rotate the treap left
void rotateLeft(TreapNode* &root){

    TreapNode* R = root->right;
    TreapNode* X = root->right->left;
 
    // rotate
    R->left = root;
    root->right = X;
 
    // set a new root
    root = R;
}

//Function to rotate the treap right
void rotateRight(TreapNode* &root){
   TreapNode* L = root->left;
    TreapNode* Y = root->left->right;
 
    // rotate
    L->right = root;
    root->left = Y;
 
    // set a new root
    root = L;
}

// Recursive function to insert a given key with a priority into treap
// using a reference parameter 
void insertNode(TreapNode* &root, int data){

  //base case
  if(root == nullptr){
    root = new TreapNode(data);
    return;
  }

  //If the given data is less than the root node, insert in 
  // the left subtree
  // otherwise, insert in the right subtree.
  if(data < root->data){
    insertNode(root->left , data);

    //rotate right if the heap property is voilated
    if(root->left != nullptr && root->left->priority > root->priority){
      rotateRight(root);
    }
  }
  else{

    insertNode(root->right, data);
        
        //Rotate left if heap property is voilated
        if(root->right != nullptr && root->right->priority > root->priority){
          rotateLeft(root);
        }
  }

}

// Recursive function to search for a key in a given treap
bool searchNode(TreapNode* root , int key){

   //If the key is not present in the treap
  if(root == nullptr){
    return false;
  }

   //If the key is found..
  if(root->data == key){
    return true;
  }

  //If the key is less than the root node, search in the left subtree
  if(key < root->data){
    return searchNode(root->left,key);
  }

  //Otherwise, search in the right subtree..
  return searchNode(root->right,key);
}

//Recursive function to delete a key from a given treap
void deleteNode(TreapNode* &root,  int key){
   //Base case: the key is not found in the tree
  if(root == nullptr){
    return;
  }

  //If the key is less than the root node, recurr for the left subtree
  if(key < root->data){
    deleteNode(root->left,key);
  }

  //If the key is greater than the root node, reccur for the right subtree 
  else if(key > root->data){
    deleteNode(root->right,key);
  }
  //If the key is found..
  else{
    //Case 1: node to be deleted has no children(it is a leaf node)
    if(root->left == nullptr && root->right == nullptr){
       //deallocate the memory and update the root to null
      delete root;
      root = nullptr;
    }
    // case 2: node to be deleted has two children.
    else if(root->left && root->right){

      //If the left child has less priority than the right 
      // child
      if(root->left->priority < root->right->priority){

        // call rotateLeft() on the root
                rotateLeft(root);
        // recursively delete the left child
                deleteNode(root->left, key);
      }
      else{

        //call 'rotateRight()' on the root
        rotateRight(root);

        // recursively delete the right child
        rotateLeft(root);
      }
    }

    //case 3: node to be deleted has only one child
    else{

      //choose a child node
      TreapNode* child = (root->left) ? root->left : root->right;
      TreapNode* curr = root;

      root = child;

      //deallocate the memory
      delete curr;
    }
  }
}

//Utility function to print two-dimensional view of a treap using 
// reverse inorder traversal
void printTreap(TreapNode *root, int space = 0 , int height = 10){

  //base case
  if(root == nullptr){
    return;
  }

  //increase distance between levels
  space += height;

  //Print the right child first
  printTreap(root->right, space);
  cout << endl;

  //Print the current node after padding with spaces
  for(int i=height;i<space;i++){
    cout << ' ';
  }

  cout << root->data << "(" << root->priority << ")\n";

  //print the left child..
  cout << endl;
  printTreap(root->left,space); 
} 
int main(){
      
   //Treap keys i.e. X values
   int keys[] = {5,3,1,24,9,10,8};

   int n = sizeof(keys)/sizeof(int);

   //Construct a treap
     TreapNode* root = nullptr;
     srand(time(nullptr));

     for(int key: keys){
      insertNode(root,key);
     }
     cout << "Constructed treap:\n\n";
    printTreap(root);
 
    cout << "\nDeleting node 1:\n\n";
    deleteNode(root, 5);
    printTreap(root);
 
    cout << "\nDeleting node 5:\n\n";
    deleteNode(root, 1);
    printTreap(root);
 
    cout << "\nDeleting node 9:\n\n";
    deleteNode(root, 10);
    printTreap(root);
 
    return 0;
}

In this code, insertNode function searches for the right position in the BST and add the node at the right position i.e. right in terms of BST and heap properties, and after adding make necessary rotations if required, for rotations rightRotate and leftRotate functions are separately written which provides the adequate rotation to the treap for maintaining its balanced form.
SearchNode is a boolean function and is used to search for a given node in the treap in O(logN) as per according to the binary searching procedure.
DeleteNode is the function that deletes the target node by searching it in O(logN) per according to the binary search procedure and then deletes the node.
printTreap function is used to print the Treap.

After discussing Treaps, their working and basic operations, let’s jump to the next part that is the Advantages of it in problem-solving.

Advantages of Treap:

Highlights:

• Discusses the various advantages of Treaps in problem-solving.
• Also, briefly state the problems in which they behave as good alternatives.

There are a lot of different advantages of Treap data structure and we will be discussing a few of them.

1) Treap is used as a self-balancing binary tree Since Treap is a randomized binary search tree i.e. each node of BST is assigned a random priority, it will bring more balance to the tree.

2) Treap is used to solve connectivity problems.

3) Treap can be used to find the sum, maximum and minimum in a given range similar to a segment tree or sparse table.

4) Treap can be used for adding/ painting in a given range.

Conclusion:

• To sum up the Treap data structure is a special binary search tree or we can say it is a height-balanced binary search tree that has many utilities in various problems and can be tweaked as per requirements of the problems.
• It can be used in place of segment trees and sparse tables in solving range query problems and also used in place of splay trees in programming contests as Treaps are way easier to code.