Treap data structure
In this article, we will discuss the treap data structure. The word treap is a combination of 'tree' and 'heap'. So, treap data structure is a combination of a heap and binary search tree.
So, for a better understanding of the treap, we should first understand the underlying data structures in the treap that are binary search tree and heap.
Binary Search tree
A binary search tree follows an order to arrange the elements. In a Binary search tree, the value of the left node must be smaller than the parent node, and the value of the right node must be greater than the parent node. This rule is applied recursively to the left and right subtree of the root.
Heap
Heaps are just binary trees with a "heap" feature. When we create a heap, we create an ordered binary tree that satisfies the "heap" characteristic.
Heap is classified into two categories: Max-heap and Min-heap. In a Max-heap, the parent's node value is greater than or equal to its children. Whereas in a Min-heap, the parent's node value is smaller than or equal to its children.
A treap is a hybrid of BST and a heap. Treap is a BST by key and a heap by priority.
In a treap, every node maintains the below two values –
Key – It follows the standard BST ordering, i.e., the left child is smaller while the right child is greater.
Priority – It is a randomly assigned value that follows the max-heap property.
A treap is constructed in a way that it is a BST for keys, i.e., the sequence elements, and a heap for priorities. Therefore, a treap follows the following properties –
- The key of a node is greater than the key of its left child.
- The key of a node is smaller than the key of its right child.
- The priority of a node should always be greater than its children.
The example of a treap data structure is shown in the below image –
In the above figure, the keys are denoted by K, whereas the letter P denotes the priority of every key. The keys in the above tree are arranged according to the BST, i.e., the left node is smaller than the parent while the right node is larger than the parent. And the priorities in the above figure are arranged according to the max-heap, i.e., the priority of a parent node is greater than the priority of its children. We can also arrange the priorities according to the min-heap.
A treap is a randomized data structure. Because of the randomized weights, there is a strong possibility that the tree will be balanced regardless of the sequence in which we add, remove, etc. (a random binary search tree has logarithmic height).
It is simply a binary search tree, therefore to print a sorted order of keys, traverse it in the same way as we would conventional BSTs. Searching for a treap is similar to searching for a tree.
Now, let's move towards the operations performed on the treap data structure.
Basic operations on treap
In a treap data structure, we can perform the following basic operations such as –
- Insertion
- Deletion
- Searching
Now, let's discuss the operations performed on treap data structure.
Insertion
We can perform the insertion operation in treap data structure by using the following procedure –
- First, we have to create a node with the value x along with a random priority. The value x is inserted in the tree according to the insert operation of the binary search tree.
- Then, we have to use rotations to move the value x up in the tree until its priority is smaller than its parent priority.
To move the value x up in the tree, we must examine whether x is a left child or a right child.
- If it is inserted in the left subtree, and the priority of the root of the left subtree is greater than x, then perform right rotation.
- If x is inserted in the right subtree, and the priority of root of the right subtree is greater than x, perform left rotation.
The pseudo-code for implementing the insert operation in a treap is given as follows –
/* It is a recursive implementation of insertion in Treap */
TreapNode* insert(TreapNode* root, int value)
{
/* If root is NULL, create a new node and return it */
if (!root)
return newNode(value);
/* If value to be inserted is smaller than the root node */
if (value <= root->value)
{
/* Insert it in the left subtree */
root->left = insert(root->left, value);
/* perform right rotation, if heap property is violated */
if (root->left->priority > root->priority)
root = rightRotate(root);
}
else
{
/* Otherwise, insert value in right subtree */
root->right = insert(root->right, value);
/* perform left rotation, if heap property is violated */
if (root->right->priority > root->priority)
root = leftRotate(root);
}
return root;
}
Deletion
Deletion in the treap data structure is completely different from insertion. Suppose we have to delete the node x from the tree, then we may use the below conditions –
- If node x is a leaf node, delete it.
- If node x has a single child, let's say z, then remove the node x from the tree, and make node z be the child of x's parent. If node x does not have any parent, then make z be the root of the tree.
- If node x has two children, then swap its position with its immediate successor in the sorted order. This may violate the heap-ordering property for the successor; therefore, we need to perform additional rotations to restore it.
/* It is recursive implementation of Delete() function */
TreapNode* deleteNode(TreapNode* root, int value)
{
if (root == NULL) return root;
/* If the value is smaller than root, recur for left subtree */
if (value < root->value)
root->left = deleteNode(root->left, value);
/* If the value is larger than root, recur for right subtree */
else if (value > root->value)
root->right = deleteNode(root->right, value);
// If left is NULL
else if (root->left == NULL)
{
TreapNode *temp = root->right;
delete(root);
root = temp; // Make right child as root
}
// If Right is NULL
else if (root->right == NULL)
{
TreapNode *temp = root->left;
delete(root);
root = temp;
}
/* When both left and right are not NULL */
else if (root->left->priority < root->right->priority)
{
root = leftRotate(root);
root->left = deleteNode(root->left, value);
}
else
{
root = rightRotate(root);
root->right = deleteNode(root->right, value);
}
return root;
}
Searching
Searching in a treap is similar to the searching in the binary search tree. In searching, priority is not an issue.
/* function to implement searching a node in BST */
TreapNode* search(TreapNode* root, int value)
{
/*If root is null or the value to be searched is present at root node*/
if (root == NULL || root->value == value)
return root;
/* If the value is greater than root's value */
if (root->value < value)
return search(root->right, value);
/* If the value is smaller than root's value */
return search(root->left, value);
}
Complexity analysis of treap data structure
Now, let's see the time complexity of the operations performed on treap data structure.
Time Complexity
| Operations | Best case time complexity | Average case time complexity | Worst-case time complexity |
| Insertion | O(log n) | O(log n) | O(n) |
| Deletion | O(log n) | O(log n) | O(n) |
| Search | O(log n) | O(log n) | O(n) |
Where 'n' is the number of nodes in the given tree.
Treap is the randomized BST; therefore, if we compute the running time of the operations performed, it turns out that every insertion, deletion, split, merge, and search operation takes O(log n) time for an n-node randomized BST.
Implementation of treap data structure
Now, let's see the implementation of treap data structure in C++.
In this code, there is a menu-driven approach containing the options like adding a new node to the treap, searching an already existing node, deleting a node from the treap, and display all the nodes in the treap.
User has to select an option to implement the corresponding function.
/*C++ program to implement the Treap data structure */
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
struct TreapNode {
int data;
int priority;
TreapNode* l, *r;
TreapNode(int value) { //constructor
this->data = value;
this->priority = rand() % 100;
this->l= this->r = nullptr;
}
};
/*function to perform left rotation*/
void rotLeft(TreapNode* &root) {
TreapNode* R = root->r;
TreapNode* X = root->r->l;
R->l = root;
root->r= X;
root = R;
}
/*function to perform right rotation*/
void rotRight(TreapNode* &root) {
TreapNode* L = root->l;
TreapNode* Y = root->l->r;
L->r = root;
root->l= Y;
root = L;
}
/*function to perform insertion operation in treap data structure*/
void insertNod(TreapNode* &root, int value) {
if (root == nullptr) {
root = new TreapNode(value);
return;
}
if (value <= root->data) {
insertNod(root->l, value);
if (root->l != nullptr && root->l->priority > root->priority)
rotRight(root); //rotate right
} else {
insertNod(root->r, value);
if (root->r!= nullptr && root->r->priority > root->priority)
rotLeft(root); //rotate left
}
}
/* function to implement searching a node in treap data structure */
bool searchNod(TreapNode* root, int key) {
if (root == nullptr || root->data == key)
return root;
else if (key < root->data)
return searchNod(root->l, key);
else
return searchNod(root->r, key);
}
/* function to perform deletion of a node in treap data structure */
void deleteNod(TreapNode* &root, int key) {
//node to be deleted which is a leaf node
if (root == nullptr)
return;
if (key < root->data)
deleteNod(root->l, key);
else if (key > root->data)
deleteNod(root->r, key);
//node to be deleted which has two children
else {
if (root->l ==nullptr && root->r == nullptr) {
delete root;
root = nullptr;
}
else if (root->l && root->r) {
if (root->l->priority < root->r->priority) {
rotLeft(root); //rotate left
deleteNod(root->l, key);
} else {
rotRight(root); //rotate right
deleteNod(root->r, key);
}
}
//node to be deleted has only one child
else {
TreapNode* child = (root->l)? root->l: root->r;
TreapNode* curr = root;
root = child;
delete curr;
}
}
}
/*function to print all the values of the treap*/
void displayTreap(TreapNode *root, int space = 0, int height =10) { //display treap
if (root == nullptr)
return;
space += height;
displayTreap(root->l, space);
cout << endl;
for (int i = height; i < space; i++)
cout << ' ';
cout << root->data << "(" << root->priority << ")";
cout << endl;
displayTreap(root->r, space);
}
int main() {
TreapNode* root = nullptr;
srand(time(nullptr));
int data;
char ch;
/* Perform tree operations */
do
{
cout<<"Choose any one of the operations given below - "<<endl;
cout<<"1. Insert a new node in the Treap Data Structure."<<endl;
cout<<"2. Display all the nodes of the Treap Data Structure."<<endl;
cout<<"3. Delete a node from the Treap Data Structure."<<endl;
cout<<"4. Search a node from the Treap Data Structure."<<endl;
int choice;
cin>>choice;
switch (choice)
{
case 1 :
cout<<"Enter the value of the node to be inserted: ";
cin>>data;
insertNod(root,data);
break;
case 2 :
cout<<"Contents of the Treap Data Structure are: ";
displayTreap(root);
break;
case 3 :
cout<<"Enter the value of the node that you want to delete: ";
cin>>data;
deleteNod(root,data);
break;
case 4 :
cout<<"Enter the word to search: ";
cin>>data;
if (searchNod(root, data))
cout<<data<<" found in Treap.";
else
cout<<data<<" not found in Treap.";
break;
default :
cout<<"Invalid choice \n ";
break;
}
cout<<"\nContinue? (Type y or n)";
cin>>ch;
} while (ch == 'Y'|| ch == 'y');
return 0;
}
Output
So, that's all about the article. Hope, it will be helpful and informative to you.