**Treap** is a unique combination of two well-known data structures: the Binary Search Tree (BST) and the Heap. This combination allows the Treap to maintain both the properties of a BST and the balancing benefits of a heap, making it an efficient tool for many computational tasks.

###### What is a Treap?

A Treap is a randomized binary search tree that also maintains a heap property based on node priorities. Specifically, it maintains these properties

**Binary Search Tree (BST) property:**A tree where the left child of a node has a value less than the node, and the right child has a value greater than the node.**Heap property:**A tree where each node has a value (‘priority’) that is greater than the values of its children (in a max heap) or smaller than the values of its children (in a min heap).

Binary Search Tree and Heap are already discussed in these posts:

- Binary Search Tree in C/C++
- Binary Search Tree in C/C++ [2]
- Heap Data structure | Heap Sort in C++
- C++ Standard Template Library (STL) – [Heap]

In a Treap, we maintain the binary search tree property with respect to the keys and the heap property with respect to the priorities. These properties allow for fast searching (O(logn)), insertion (O(logn)), and deletion (O(logn)) operations. And, unlike AVL or Red-Black trees, Treaps balance themselves probabilistically through randomized priorities.

###### Why use a Treap?

Treaps have practical applications in areas where both fast searching and frequent modifications (insertions/deletions) are needed. Some examples include:

**Balanced Search Trees**: Treaps ensure balanced trees without complex balancing algorithms like in AVL or Red-Black trees.**Dynamic Ordered Sets**: Treaps efficiently maintain a set of elements that can be modified dynamically.**Priority Queues**: Treaps allow you to access the element with the highest priority while also keeping elements in sorted order.**Randomized Algorithms**: The randomness in Treap priorities helps avoid worst-case scenarios, making Treaps useful in randomized algorithms.

###### Structure of a Treap

A Treap node contains three important elements:

**Key**: used to maintain the binary search tree property.**Priority**: a random value, used to maintain the heap property.**Left and Right Pointers**: pointers to the left and right children of the node.

The Treap ensures two properties:

- The
**binary search tree property**: Keys in the left subtree are smaller, and keys in the right subtree are larger. - The
**heap property**: A node’s priority must be greater than the priority of its children.

Basic Operations of a Treap

**Insertion**: We insert a new node by following the BST insertion rules, and then we restore the heap property by performing rotations.**Deletion**: We find the node to delete using the BST property and remove it by rotating it downward until it becomes a leaf, then removing it.**Search**: We search the node with a given ‘key’ and return true if it is present, false otherwise.

###### Pseudocode

**Rotation (for maintaining heap property)**

Rotate-Right(y)

x ← y.left

T2 ← x.right

x.right ← y

y.left ← T2

return x

Rotate-Left(y)

x ← y.right

T2 = x.left

x.left ← y

y.right ← T2

return x

**Insertion**

Treap-Insert(T, x)

if T is NULL

return new node with Key 'x' and random Priority value 'priority'

if x < T.key

T.left ← Treap-Insert(T.left, x)

if T.left.priority > T.priority

T ← Rotate-Right(T)

else

T.right ← Treap-Insert(T.right, x)

if T.right.priority > T.priority

T ← Rotate-Left(T)

return T

**Deletion**

Treap-Delete(T, x)

if T is NULL

return T

if x < T.key

T.left ← Treap-Delete(T.left, x)

else if x > T.key

T.right ← Treap-Delete(T.right, x)

else

if T.left is NULL or T.right is NULL

temp ← T.left ? T.left : T.right

free T

return temp

else if T.left.priority > T.right.priority

T ← Rotate-Right(T)

T.right ← Treap-Delete(T.right, x)

else

T ← Rotate-Left(T)

T.left ← Treap-Delete(T.left, x)

return T

**Search**

Treap-Search(T, x)

if T is NULL

return false

if x = T.key

return true

else if x < T.key

return Treap-Search(T.left, x)

else

return Treap-Search(T.right, x)

**Code Implementation**

```
//
// main.cpp
// Treap
//
// Created by Himanshu on 30/09/24.
//
#include <iostream>
#include <cstdlib> // For rand()
#include <ctime> // For random seed
// Node structure for Treap
struct TreapNode {
int key, priority;
TreapNode* left;
TreapNode* right;
TreapNode(int k) : key(k), priority(rand()), left(nullptr), right(nullptr) {}
};
// Right rotation to maintain heap property
TreapNode* rotateRight(TreapNode* y) {
TreapNode* x = y->left;
TreapNode* T2 = x->right;
x->right = y;
y->left = T2;
return x;
}
// Left rotation to maintain heap property
TreapNode* rotateLeft(TreapNode* y) {
TreapNode* x = y->right;
TreapNode* T2 = x->left;
x->left = y;
y->right = T2;
return x;
}
// Insert a new node with a given key
TreapNode* insert(TreapNode* root, int key) {
if (!root)
return new TreapNode(key);
if (key < root->key) {
root->left = insert(root->left, key);
if (root->left->priority > root->priority)
root = rotateRight(root);
} else {
root->right = insert(root->right, key);
if (root->right->priority > root->priority)
root = rotateLeft(root);
}
return root;
}
// Delete a node with a given key
TreapNode* deleteNode(TreapNode* root, int key) {
if (!root)
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) {
TreapNode* temp = root->right;
delete root;
root = temp;
} else if (!root->right) {
TreapNode* temp = root->left;
delete root;
root = temp;
} else if (root->left->priority > root->right->priority) {
root = rotateRight(root);
root->right = deleteNode(root->right, key);
} else {
root = rotateLeft(root);
root->left = deleteNode(root->left, key);
}
}
return root;
}
// Search for a key in the Treap
bool search(TreapNode* root, int key) {
if (!root)
return false;
if (root->key == key)
return true;
if (key < root->key)
return search(root->left, key);
return search(root->right, key);
}
// Inorder traversal to display the Treap
void inorderTraversal(TreapNode* root) {
if (root) {
inorderTraversal(root->left);
std::cout << "Key: " << root->key << " | Priority: " << root->priority << std::endl;
inorderTraversal(root->right);
}
}
int main() {
srand(time(0)); // Seed for random priorities
TreapNode* root = nullptr;
// Insert nodes
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);
std::cout << "Treap Inorder Traversal:\n";
inorderTraversal(root);
// Search for a key
std::cout << "\nSearch for 40: ";
if (search(root, 40)) std::cout << "Found!\n";
else std::cout << "Not Found!\n";
// Delete a key
root = deleteNode(root, 40);
std::cout << "\nAfter deleting 40:\n";
inorderTraversal(root);
return 0;
}
```

**Output**

Treap Inorder Traversal:

Key: 20 | Priority: 1432268860

Key: 30 | Priority: 682686416

Key: 40 | Priority: 66127264

Key: 50 | Priority: 2096479644

Key: 60 | Priority: 1469792575

Key: 70 | Priority: 930239436

Key: 80 | Priority: 985102354

Search for 40: Found!

After deleting 40:

Key: 20 | Priority: 1432268860

Key: 30 | Priority: 682686416

Key: 50 | Priority: 2096479644

Key: 60 | Priority: 1469792575

Key: 70 | Priority: 930239436

Key: 80 | Priority: 985102354

###### Explanation of the Code

**Node Structure**

The `TreapNode`

structure holds the key (for BST property), priority (for heap property), and pointers to the left and right children. The priority is assigned randomly to ensure probabilistic balancing.

**Insertion**

- The node is first inserted as in a binary search tree.
- After insertion, rotations (right or left) are performed to restore the heap property if the priority of the new node is higher than its parent.

**Deletion**

- To delete a node, we first find the node as in a BST.
- If the node has two children, we rotate it with the child that has the higher priority, and the process is repeated until the node is a leaf and can be removed.

**Rotations**

**Right Rotation**: The node’s left child becomes its parent, maintaining both the heap and BST properties.**Left Rotation**: The node’s right child becomes its parent, similarly preserving both properties.

**Search**

The search operation is similar to that of a standard binary search tree. We traverse the tree based on the key values, either moving left or right depending on whether the key is smaller or larger than the current node’s key.

Treap is an efficient and simple data structure that combines the best of both binary search trees and heaps. It provides the benefits of efficient search, insert, and delete operations, while avoiding the complexity of strict balancing rules required by other balanced trees. The use of randomized priorities ensures that the tree remains balanced on average, making it a great choice for applications requiring dynamic insertion and deletion with fast lookup times.