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.