`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

**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**

`n`

`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

**which is inefficient in terms of time complexity.**

`O(logN)`

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

**. look for the immediate successor**

`case ii`

**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`

**, and**

`searchNode`

**for**

`printTreap`

`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

**and**

`rightRotate`

**functions are separately written which provides the adequate rotation to the treap for maintaining its balanced form.**

`leftRotate`

**is a boolean function and is used to search for a given node in the treap in**

`SearchNode`

**as per according to the binary searching procedure.**

`O(logN)`

**is the function that deletes the target node by searching it in**

`DeleteNode`

**per according to the binary search procedure and then deletes the node.**

`O(logN)`

**function is used to print the Treap.**

`printTreap`

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.