Treap (A Randomized Binary Search Tree)

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> struct Node{ int key; int priority; struct Node *left, *right; }; struct Node* newNode(int key){ struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->key = key; temp->priority = rand()%100; temp->left = temp->right = NULL; return temp; } void rightRotate(struct Node **y){ struct Node *x = (*y)->left; struct Node *T2 = x->right; x->right = *y; (*y)->left = T2; *y = x; } void leftRotate(struct Node **x){ struct Node *y = (*x)->right; struct Node *T2 = y->left; y->left = *x; (*x)->right = T2; *x = y; } struct Node* insert(struct Node* root, int key){ if(root == NULL) return newNode(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; } void inorder(struct Node* root){ if(root){ inorder(root->left); printf("%d ", root->key); inorder(root->right); } } int main(){ struct Node* 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); return 0; } 

 Inorder traversal of the given Treap: 20 30 40 50 60 70 80 

 // C++ program to implement Treaps #include <iostream> #include <cstdlib> using namespace std; struct Node{ int key; int priority; struct Node *left, *right; }; struct Node* newNode(int key){ struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->key = key; temp->priority = rand()%100; temp->left = temp->right = NULL; return temp; } void rightRotate(struct Node **y){ struct Node *x = (*y)->left; struct Node *T2 = x->right; x->right = *y; (*y)->left = T2; *y = x; } void leftRotate(struct Node **x){ struct Node *y = (*x)->right; struct Node *T2 = y->left; y->left = *x; (*x)->right = T2; *x = y; } struct Node* insert(struct Node* root, int key){ if(root == NULL) return newNode(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; } void inorder(struct Node* root){ if(root){ inorder(root->left); cout << root->key << " "; inorder(root->right); } } int main(){ struct Node* 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); cout << "Inorder traversal of the given Treap: "; inorder(root); return 0; } 

 Inorder traversal of the given Treap: 20 30 40 50 60 70 80 

 // Java program to implement Treaps import java.util.*; class Node{ int key; int priority; Node left, right; Node(int key){ this.key = key; this.priority = new Random().nextInt(100); this.left = this.right = null; } } public class Treaps{ Node root; Node rightRotate(Node y){ Node x = y.left; Node T2 = x.right; x.right = y; y.left = T2; return x; } Node leftRotate(Node x){ Node y = x.right; Node T2 = y.left; y.left = x; x.right = T2; return y; } Node insert(Node root, int key){ if(root == null) return new Node(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; } void inorder(Node root){ if(root != null){ inorder(root.left); System.out.print(root.key + " "); inorder(root.right); } } public static void main(String[] args){ Treaps treap = new Treaps(); treap.root = treap.insert(treap.root, 50); treap.root = treap.insert(treap.root, 30); treap.root = treap.insert(treap.root, 20); treap.root = treap.insert(treap.root, 40); treap.root = treap.insert(treap.root, 70); treap.root = treap.insert(treap.root, 60); treap.root = treap.insert(treap.root, 80); System.out.print("Inorder traversal of the given Treap: "); treap.inorder(treap.root); } } 

 Inorder traversal of the given Treap: 20 30 40 50 60 70 80 

 # Python program to implement Treaps import random class Node: def __init__(self, key): self.key = key self.priority = random.randint(0, 100) self.left = None self.right = None def rightRotate(y): x = y.left T2 = x.right x.right = y y.left = T2 return x def leftRotate(x): y = x.right T2 = y.left y.left = x x.right = T2 return y def insert(root, key): if root is None: return Node(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 def inorder(root): if root: inorder(root.left) print(root.key, end=" ") inorder(root.right) root = None 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) print("Inorder traversal of the given Treap: ", end="") inorder(root) 

 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> struct Node{ int key; int priority; struct Node *left, *right; }; struct Node* newNode(int key){ struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->key = key; temp->priority = rand()%100; temp->left = temp->right = NULL; return temp; } void rightRotate(struct Node **y){ struct Node *x = (*y)->left; struct Node *T2 = x->right; x->right = *y; (*y)->left = T2; *y = x; } void leftRotate(struct Node **x){ struct Node *y = (*x)->right; struct Node *T2 = y->left; y->left = *x; (*x)->right = T2; *x = y; } struct Node* insert(struct Node* root, int key){ if(root == NULL) return newNode(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; } struct Node* search(struct Node* root, int key){ if(root == NULL || root->key == key) return root; if(root->key < key) return search(root->right, key); return search(root->left, key); } int main(){ struct Node* 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); struct Node* result = search(root, 40); if(result != NULL) printf("Key %d found\n", result->key); else printf("Key not found\n"); return 0; } 

 Key found 40 

 // C++ program to implement Treaps #include <iostream> #include <cstdlib> using namespace std; struct Node{ int key; int priority; struct Node *left, *right; }; struct Node* newNode(int key){ struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->key = key; temp->priority = rand()%100; temp->left = temp->right = NULL; return temp; } void rightRotate(struct Node **y){ struct Node *x = (*y)->left; struct Node *T2 = x->right; x->right = *y; (*y)->left = T2; *y = x; } void leftRotate(struct Node **x){ struct Node *y = (*x)->right; struct Node *T2 = y->left; y->left = *x; (*x)->right = T2; *x = y; } struct Node* insert(struct Node* root, int key){ if(root == NULL) return newNode(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; } struct Node* search(struct Node* root, int key){ if(root == NULL || root->key == key) return root; if(root->key < key) return search(root->right, key); return search(root->left, key); } int main(){ struct Node* 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); struct Node* result = search(root, 40); if(result != NULL) cout << "Key found" << " " << result->key << endl; else cout << "Key not found" << endl; return 0; } 

 Key found 

 // Java program to implement Treaps import java.util.*; class Node { int key; int priority; Node left, right; Node(int key) { this.key = key; this.priority = new Random().nextInt(100); this.left = this.right = null; } } public class Treaps { Node root; // Search key in Treap Node search(Node root, int key) { if (root == null || root.key == key) return root; if (root.key < key) return search(root.right, key); else return search(root.left, key); } // Right rotation Node rightRotate(Node y) { if (y == null || y.left == null) return y; // Safety check Node x = y.left; Node T2 = x.right; x.right = y; y.left = T2; return x; } // Left rotation Node leftRotate(Node x) { if (x == null || x.right == null) return x; // Safety check Node y = x.right; Node T2 = y.left; y.left = x; x.right = T2; return y; } // Insert key into Treap Node insert(Node root, int key) { if (root == null) return new Node(key); if (key <= root.key) { root.left = insert(root.left, key); if (root.left != null && root.left.priority > root.priority) root = rightRotate(root); } else { root.right = insert(root.right, key); if (root.right != null && root.right.priority > root.priority) root = leftRotate(root); } return root; } public static void main(String[] args) { Treaps treap = new Treaps(); treap.root = treap.insert(treap.root, 50); treap.root = treap.insert(treap.root, 30); treap.root = treap.insert(treap.root, 20); treap.root = treap.insert(treap.root, 40); treap.root = treap.insert(treap.root, 70); treap.root = treap.insert(treap.root, 60); treap.root = treap.insert(treap.root, 80); Node result = treap.search(treap.root, 40); if (result != null) System.out.println("Key" + " " + result.key + " " + "found"); else System.out.println("Key not found"); } } 

 Key 40 found 

 # Python program to implement Treaps import random class Node: def __init__(self, key): self.key = key self.priority = random.randint(0, 100) self.left = None self.right = None def search(root, key): if root is None or root.key == key: return root if root.key < key: return search(root.right, key) return search(root.left, key) def rightRotate(y): x = y.left T2 = x.right x.right = y y.left = T2 return x def leftRotate(x): y = x.right T2 = y.left y.left = x x.right = T2 return y def insert(root, key): if root is None: return Node(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 root = None 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) result = search(root, 40) if result: print("Key " + str(result.key) + " found") else: print("Key not found") 

 Key 40 found 

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> struct Node { int key; int priority; struct Node *left, *right; }; // Function to create a new node struct Node* newNode(int key) { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->key = key; temp->priority = rand() % 100; temp->left = temp->right = NULL; return temp; } // Right rotation function struct Node* rightRotate(struct Node *y) { struct Node *x = y->left; struct Node *T2 = x->right; x->right = y; y->left = T2; return x; } // Left rotation function struct Node* leftRotate(struct Node *x) { struct Node *y = x->right; struct Node *T2 = y->left; y->left = x; x->right = T2; return y; } // Insert function struct Node* insert(struct Node* root, int key) { if (root == NULL) return newNode(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 function void inorder(struct Node* root) { if (root != NULL) { inorder(root->left); printf("%d ", root->key); inorder(root->right); } } // Delete function struct Node* deleteNode(struct Node* root, int key) { if (root == NULL) return root; if (key < root->key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { if (root->left == NULL) { struct Node* temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct Node* 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; } int main() { struct Node* 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"); return 0; } 

 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 

 #include <iostream> #include <cstdlib> using namespace std; struct Node { int key; int priority; Node *left, *right; Node(int k) { key = k; priority = rand() % 100; left = right = nullptr; } }; // Right rotation function Node* rightRotate(Node* y) { Node* x = y->left; Node* T2 = x->right; x->right = y; y->left = T2; return x; } // Left rotation function Node* leftRotate(Node* x) { Node* y = x->right; Node* T2 = y->left; y->left = x; x->right = T2; return y; } // Insert function Node* insert(Node* root, int key) { if (root == nullptr) return new Node(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 function void inorder(Node* root) { if (root != nullptr) { inorder(root->left); cout << root->key << " "; inorder(root->right); } } // Delete function Node* deleteNode(Node* root, int key) { if (root == nullptr) return root; if (key < root->key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { if (root->left == nullptr) { Node* temp = root->right; delete root; return temp; } else if (root->right == nullptr) { Node* temp = root->left; delete 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; } int main() { Node* root = nullptr; 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); cout << "Inorder traversal of the given Treap: "; inorder(root); cout << "\n"; root = deleteNode(root, 20); cout << "Inorder traversal of the Treap after deletion: "; inorder(root); cout << "\n"; return 0; } 

 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 

 // Java program to implement Treaps import java.util.*; class Node{ int key; int priority; Node left, right; Node(int key){ this.key = key; this.priority = new Random().nextInt(100); this.left = this.right = null; } } public class Treaps{ Node root; Node deleteNode(Node root, int key){ if(root == null) return root; if(key < root.key) root.left = deleteNode(root.left, key); else if(key > root.key) root.right = deleteNode(root.right, key); else{ if(root.left == null){ Node temp = root.right; return temp; } else if(root.right == null){ Node temp = root.left; 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; } Node rightRotate(Node y){ Node x = y.left; Node T2 = x.right; x.right = y; y.left = T2; return x; } Node leftRotate(Node x){ Node y = x.right; Node T2 = y.left; y.left = x; x.right = T2; return y; } Node insert(Node root, int key){ if(root == null) return new Node(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; } static void inorder(Node root){ if(root != null){ inorder(root.left); System.out.print(root.key + " "); inorder(root.right); } } public static void main(String[] args){ Treaps treap = new Treaps(); treap.root = treap.insert(treap.root, 50); treap.root = treap.insert(treap.root, 30); treap.root = treap.insert(treap.root, 20); treap.root = treap.insert(treap.root, 40); treap.root = treap.insert(treap.root, 70); treap.root = treap.insert(treap.root, 60); treap.root = treap.insert(treap.root, 80); System.out.print("Inorder traversal of the given Treap: "); treap.inorder(treap.root); treap.root = treap.deleteNode(treap.root, 20); System.out.println(); System.out.print("Inorder traversal of the given Treap after deletion: "); treap.inorder(treap.root); } } 

 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 

 # Python program to implement Treaps import random class Node: def __init__(self, key): self.key = key self.priority = random.randint(0, 100) self.left = None self.right = None def rightRotate(y): x = y.left T2 = x.right x.right = y y.left = T2 return x def leftRotate(x): y = x.right T2 = y.left y.left = x x.right = T2 return y def insert(root, key): if root is None: return Node(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 def inorder(root): if root: inorder(root.left) print(root.key, end=" ") inorder(root.right) def deleteNode(root, key): if root is None: return root if key < root.key: root.left = deleteNode(root.left, key) elif key > root.key: root.right = deleteNode(root.right, key) else: if root.left is None: temp = root.right return temp elif root.right is None: temp = root.left 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 root = None 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) print("Inorder traversal of the given Treap: ", end="") inorder(root) print() root = deleteNode(root, 20) print("Inorder traversal of the given Treap after deletion: ", end="") inorder(root) 

 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.