Treaps (pronounced as “trees” and “heaps”) are a data structure that is combination of Binary Search Tree and Heap. It is a binary search tree that is also a heap. We can call it a randomized data structure that maintains a dynamic set of elements, it ensures both the binary search order and the heap order.
Imagine a scenario where you have to organize a bookshelf. You want these book to be in a sorted order, but you also want to keep the books that you read most often at the top. Treaps are the data structure that can help you in this scenario.
Properties of Treaps
Following are the properties of Treaps −
- Combined with two major data structures: Binary Search Tree and Heap.
- Hence it is BST, keys in left sub-tree are less than the root and keys in right subtree are greater than the root.
- Has time complexity of O(log n) for search, insert and delete operations.
- Randomized data structure.
- It is a balanced binary search tree.
- The tree height is O(log n) on average.
Structure of Treaps
Each node in a Treap has two fields:
- Key: The key is the value of the node.
- Priority: The priority is a random number that is assigned to the node.
The key field is used to maintain the binary search tree property, and the priority field is used to maintain the heap property. The priority of a node is always greater than the priority of its children.
Here is an example of a Treap:
50
/ \
30 70
/ \ / \
20 40 60 80
Operations on Treaps
There are many operations that can be performed on Treaps. Some of the major operations are:
- Search
- Insert
- Delete
Implementation of Treaps
Now we will see how to implement Treaps in C, C++, Java and Python.
Algorithm for Inserting a Node in Treaps
1. If the root is NULL, create a new node with the key and priority and return the node. 2. If the key is less than the root, insert in the left subtree. 3. If the key is greater than the root, insert in the right subtree. 4. If the priority of the new node is greater than the priority of the root, rotate the new node with the root. 5. Repeat the process until the new node is inserted.
Code for Implementing Treaps
Now, let’s understand the code for implementing Treaps in C, C++, Java and Python.
For implementing treaps, we need to create a structure for the node and define the functions for inserting and rotating the nodes. After that we can insert the nodes and perform the operations on the treap.
// C program to implement Treaps#include <stdio.h>#include <stdlib.h>structNode{int key;int priority;structNode*left,*right;};structNode*newNode(int key){structNode* temp =(structNode*)malloc(sizeof(structNode));
temp->key = key;
temp->priority =rand()%100;
temp->left = temp->right =NULL;return temp;}voidrightRotate(structNode**y){structNode*x =(*y)->left;structNode*T2 = x->right;
x->right =*y;(*y)->left = T2;*y = x;}voidleftRotate(structNode**x){structNode*y =(*x)->right;structNode*T2 = y->left;
y->left =*x;(*x)->right = T2;*x = y;}structNode*insert(structNode* root,int key){if(root ==NULL)returnnewNode(key);if(key <= root->key){
root->left =insert(root->left, key);if(root->left->priority > root->priority)rightRotate(&root);}else{
root->right =insert(root->right, key);if(root->right->priority > root->priority)leftRotate(&root);}return root;}voidinorder(structNode* root){if(root){inorder(root->left);printf("%d ", root->key);inorder(root->right);}}intmain(){structNode* root =NULL;
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);printf("Inorder traversal of the given Treap: ");inorder(root);return0;}
Output
Following is the output of the above C program:
Inorder traversal of the given Treap: 20 30 40 50 60 70 80
Search Operation on Treaps
Searching in a Treap is similar to searching in a Binary Search Tree. We start from the root and compare the key with the root. If the key is less than the root, we move to the left subtree. If the key is greater than the root, we move to the right subtree. We continue this process until we find the key or reach a NULL node.
Algorithm for Searching in Treaps
1. Start from the root. 2. If the root is NULL, return NULL. 3. If the key is equal to the root, return the root. 4. If the key is less than the root, search in the left subtree. 5. If the key is greater than the root, search in the right subtree. 6. Repeat the process until the key is found or NULL is reached.
Code for Searching in Treaps
Now, let’s see the code for searching in Treaps in C, C++, Java and Python.
// C program to implement Treaps#include <stdio.h>#include <stdlib.h>structNode{int key;int priority;structNode*left,*right;};structNode*newNode(int key){structNode* temp =(structNode*)malloc(sizeof(structNode));
temp->key = key;
temp->priority =rand()%100;
temp->left = temp->right =NULL;return temp;}voidrightRotate(structNode**y){structNode*x =(*y)->left;structNode*T2 = x->right;
x->right =*y;(*y)->left = T2;*y = x;}voidleftRotate(structNode**x){structNode*y =(*x)->right;structNode*T2 = y->left;
y->left =*x;(*x)->right = T2;*x = y;}structNode*insert(structNode* root,int key){if(root ==NULL)returnnewNode(key);if(key <= root->key){
root->left =insert(root->left, key);if(root->left->priority > root->priority)rightRotate(&root);}else{
root->right =insert(root->right, key);if(root->right->priority > root->priority)leftRotate(&root);}return root;}structNode*search(structNode* root,int key){if(root ==NULL|| root->key == key)return root;if(root->key < key)returnsearch(root->right, key);returnsearch(root->left, key);}intmain(){structNode* root =NULL;
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);structNode* result =search(root,40);if(result !=NULL)printf("Key %d found\n", result->key);elseprintf("Key not found\n");return0;}
Output
Following is the output of the above C program:
Key found 40
Deletion Operation on Treaps
Deletion in a Treap is similar to deletion in a Binary Search Tree. We first search for the key to be deleted. If the key is found, we delete the node and rearrange the tree to maintain the heap property. We can delete the node by replacing it with the node that has the smallest priority in the right subtree or the node that has the largest priority in the left subtree.
Algorithm for Deleting a Node in Treaps
1. Search for the key to be deleted. 2. If the key is not found, return NULL. 3. If the key is found, delete the node. 4. If the node has no children, delete the node. 5. If the node has one child, replace the node with the child. 6. If the node has two children, replace the node with the node that has the smallest priority in the right subtree or the node that has the largest priority in the left subtree. 7. Repeat the process until the node is deleted.
Code for Deleting a Node in Treaps
Now, let’s see the code for deleting a node in Treaps in C, C++, Java and Python.
// C program to implement Treaps#include <stdio.h>#include <stdlib.h>structNode{int key;int priority;structNode*left,*right;};// Function to create a new nodestructNode*newNode(int key){structNode* temp =(structNode*)malloc(sizeof(structNode));
temp->key = key;
temp->priority =rand()%100;
temp->left = temp->right =NULL;return temp;}// Right rotation functionstructNode*rightRotate(structNode*y){structNode*x = y->left;structNode*T2 = x->right;
x->right = y;
y->left = T2;return x;}// Left rotation functionstructNode*leftRotate(structNode*x){structNode*y = x->right;structNode*T2 = y->left;
y->left = x;
x->right = T2;return y;}// Insert functionstructNode*insert(structNode* root,int key){if(root ==NULL)returnnewNode(key);if(key <= root->key){
root->left =insert(root->left, key);if(root->left->priority > root->priority)
root =rightRotate(root);}else{
root->right =insert(root->right, key);if(root->right->priority > root->priority)
root =leftRotate(root);}return root;}// Inorder traversal functionvoidinorder(structNode* root){if(root !=NULL){inorder(root->left);printf("%d ", root->key);inorder(root->right);}}// Delete functionstructNode*deleteNode(structNode* root,int key){if(root ==NULL)return root;if(key < root->key)
root->left =deleteNode(root->left, key);elseif(key > root->key)
root->right =deleteNode(root->right, key);else{if(root->left ==NULL){structNode* temp = root->right;free(root);return temp;}elseif(root->right ==NULL){structNode* temp = root->left;free(root);return temp;}if(root->left->priority < root->right->priority){
root =rightRotate(root);
root->right =deleteNode(root->right, key);}else{
root =leftRotate(root);
root->left =deleteNode(root->left, key);}}return root;}intmain(){structNode* root =NULL;
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);printf("Inorder traversal of the given Treap: ");inorder(root);printf("\n");
root =deleteNode(root,20);printf("Inorder traversal of the Treap after deletion: ");inorder(root);printf("\n");return0;}
Output
Following is the output of the above C program:
Inorder traversal of the given Treap: 20 30 40 50 60 70 80 Inorder traversal of the given Treap after deletion: 30 40 50 60 70 80
Time Complexity of Treaps
Following is the time complexity of Treaps:
- Insertion: O(log n) on average.
- Deletion: O(log n) on average.
- Search: O(log n) on average.
Applications of Treaps
- It is used in the implementation of priority queues.
- Also used in online algorithms.
- Useful in dynamic optimization problems.
- Helpful in interval scheduling.
Conclusion
In this chapter, we learned about Treaps, which are a combination of Binary Search Trees and Heaps. We saw the structure of Treaps, the operations that can be performed on Treaps, and the implementation of Treaps in C, C++, Java and Python. We also saw the time and space complexity of Treaps along with the applications of Treaps.
Leave a Reply