Posted on by Kalkicode
Code Tree

Treap implementation

Treap, short for Tree + Heap, is a combination of a binary search tree and a max heap. In a treap, each node has both a value and a priority. The binary search tree property ensures that the nodes are ordered according to their values, while the max heap property ensures that the nodes are also ordered according to their priorities. This combination allows for efficient operations in both the search tree and the heap.

Problem Statement

The problem we're addressing is the implementation of a treap, which involves adding nodes to the treap while maintaining both the binary search tree property and the max heap property. We will also implement rotations to ensure that the priorities are maintained correctly.

Example

Consider the following treap:

``````
10 (72)
/ \
/   \
5 (38)  15 (41)
\       / \
8 (94) 20 (54)

``````

In this treap, each node has both a value and a priority in parentheses. The treap properties ensure that the values are ordered as a binary search tree, and the priorities are ordered as a max heap.

Idea to Solve

To implement a treap, we need to follow these steps:

1. Define the TreeNode class with fields for data (value), priority, left child, and right child.
2. Implement rotation methods (rightRotate and leftRotate) for maintaining the max heap property during insertion.
3. Implement the addNode method to insert a new node while considering the priorities.
4. Implement the insert method to add a new value to the treap using the addNode method.
5. Implement the inorder traversal method to display the nodes in order.

Pseudocode

``````
TreeNode class:
data
priority
left
right

TreapTree class:
root

rightRotate(node):
temp = node.left
point = node.left.right
temp.right = node
node.left = point
return temp

leftRotate(node):
temp = node.right
point = node.right.left
temp.left = node
node.right = point
return temp

if node is null:
return new TreeNode(data)
else if data <= node.data:
if node.left.priority > node.priority:
return rightRotate(node)
else:
if node.right.priority > node.priority:
return leftRotate(node)
return node

insert(data):

inorder(node):
if node is not null:
inorder(node.left)
print("Data:", node.data, "[ priority:", node.priority, "]")
inorder(node.right)

Main method:
tree = new TreapTree()
tree.insert(10)
tree.insert(5)
tree.insert(15)
tree.insert(8)
tree.insert(20)
print("\n Inorder")
tree.inorder(tree.root)

``````

Algorithm Explanation

The pseudocode describes the implementation of a treap. It includes defining the TreeNode class, implementing rotation methods for maintaining the max heap property, implementing the addNode method to insert nodes while considering priorities, implementing the insert method to add new values to the treap, and implementing the inorder traversal method to display the nodes in order.

Code Solution

``````/*
Java Program for
Treap implementation
*/
//  Treap Tree node
class TreeNode
{
public int data;
public int priority;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
this.priority = 1 + (int)(Math.random() * (100));
}
}
public class TreapTree
{
public TreeNode root;
public TreapTree()
{
this.root = null;
}
// Perform right rotation
public TreeNode rightRotate(TreeNode node)
{
TreeNode temp = node.left;
TreeNode point = node.left.right;
temp.right = node;
node.left = point;
return temp;
}
// Perform left rotation
public TreeNode leftRotate(TreeNode node)
{
TreeNode temp = node.right;
TreeNode point = node.right.left;
temp.left = node;
node.right = point;
return temp;
}
public TreeNode addNode(TreeNode node, int data)
{
if (node == null)
{
// Case 1
// return a new tree node
return new TreeNode(data);
}
else if (data <= node.data)
{
// Case 2
// When added data is less than or equal to given node data
if (node.left.priority > node.priority)
{
// right rotate based on priority
return rightRotate(node);
}
}
else
{
// Case 3
// When added data is greater than to given node data
if (node.right.priority > node.priority)
{
// left rotate based on priority
return leftRotate(node);
}
}
return node;
}
// Handles the request to add new node in Treap
public void insert(int data)
{
}
public void inorder(TreeNode node)
{
if (node != null)
{
inorder(node.left);
System.out.print(" Data : " + node.data + " [ priority : " + node.priority + "] \n");
inorder(node.right);
}
}
public static void main(String[] args)
{
TreapTree tree = new TreapTree();
tree.insert(7);
tree.insert(3);
tree.insert(2);
tree.insert(10);
tree.insert(12);
tree.insert(5);
tree.insert(8);
tree.insert(11);
tree.insert(13);
tree.insert(17);
// Display tree node
System.out.print("\n Inorder \n");
tree.inorder(tree.root);
}
}``````

input

`````` Inorder
Data : 2 [ priority : 3]
Data : 3 [ priority : 50]
Data : 5 [ priority : 58]
Data : 7 [ priority : 53]
Data : 8 [ priority : 6]
Data : 10 [ priority : 96]
Data : 11 [ priority : 79]
Data : 12 [ priority : 53]
Data : 13 [ priority : 26]
Data : 17 [ priority : 11]``````
``````// Include header file
#include <iostream>
#include <math.h>
#include <time.h>
using namespace std;
/*
C++ Program for
Treap implementation
*/

//  Treap Tree node
class TreeNode
{
public: int data;
int priority;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
this->priority = rand()%(100);
}
};
class TreapTree
{
public: TreeNode *root;
TreapTree()
{
this->root = NULL;
}
// Perform right rotation
TreeNode *rightRotate(TreeNode *node)
{
TreeNode *temp = node->left;
TreeNode *point = node->left->right;
temp->right = node;
node->left = point;
return temp;
}
// Perform left rotation
TreeNode *leftRotate(TreeNode *node)
{
TreeNode *temp = node->right;
TreeNode *point = node->right->left;
temp->left = node;
node->right = point;
return temp;
}
{
if (node == NULL)
{
// Case 1
// return a new tree node
return new TreeNode(data);
}
else if (data <= node->data)
{
// Case 2
// When added data is less than or equal to given node data
if (node->left->priority > node->priority)
{
// right rotate based on priority
return this->rightRotate(node);
}
}
else
{
// Case 3
// When added data is greater than to given node data
if (node->right->priority > node->priority)
{
// left rotate based on priority
return this->leftRotate(node);
}
}
return node;
}
// Handles the request to add new node in Treap
void insert(int data)
{
}
void inorder(TreeNode *node)
{
if (node != NULL)
{
this->inorder(node->left);
cout << " Data : " << node->data
<< " [ priority : " << node->priority << "] \n";
this->inorder(node->right);
}
}
};
int main()
{
TreapTree *tree = new TreapTree();
tree->insert(7);
tree->insert(3);
tree->insert(2);
tree->insert(10);
tree->insert(12);
tree->insert(5);
tree->insert(8);
tree->insert(11);
tree->insert(13);
tree->insert(17);
// Display tree node
cout << "\n Inorder \n";
tree->inorder(tree->root);
return 0;
}``````

input

`````` Inorder
Data : 2 [ priority : 77]
Data : 3 [ priority : 86]
Data : 5 [ priority : 35]
Data : 7 [ priority : 83]
Data : 8 [ priority : 86]
Data : 10 [ priority : 15]
Data : 11 [ priority : 92]
Data : 12 [ priority : 93]
Data : 13 [ priority : 49]
Data : 17 [ priority : 21]``````
``````// Include namespace system
using System;
/*
Csharp Program for
Treap implementation
*/
//  Treap Tree node
public class TreeNode
{
public int data;
public int priority;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
Random rand = new Random();
// Set node value
this.data = data;
this.left = null;
this.right = null;
this.priority = rand.Next(1, 100);
}
}
public class TreapTree
{
public TreeNode root;
public TreapTree()
{
this.root = null;
}
// Perform right rotation
public TreeNode rightRotate(TreeNode node)
{
TreeNode temp = node.left;
TreeNode point = node.left.right;
temp.right = node;
node.left = point;
return temp;
}
// Perform left rotation
public TreeNode leftRotate(TreeNode node)
{
TreeNode temp = node.right;
TreeNode point = node.right.left;
temp.left = node;
node.right = point;
return temp;
}
public TreeNode addNode(TreeNode node, int data)
{
if (node == null)
{
// Case 1
// return a new tree node
return new TreeNode(data);
}
else if (data <= node.data)
{
// Case 2
// When added data is less than or equal to given node data
if (node.left.priority > node.priority)
{
// right rotate based on priority
return this.rightRotate(node);
}
}
else
{
// Case 3
// When added data is greater than to given node data
if (node.right.priority > node.priority)
{
// left rotate based on priority
return this.leftRotate(node);
}
}
return node;
}
// Handles the request to add new node in Treap
public void insert(int data)
{
}
public void inorder(TreeNode node)
{
if (node != null)
{
this.inorder(node.left);
Console.Write(" Data : " + node.data + " [ priority : " + node.priority + "] \n");
this.inorder(node.right);
}
}
public static void Main(String[] args)
{
TreapTree tree = new TreapTree();
tree.insert(7);
tree.insert(3);
tree.insert(2);
tree.insert(10);
tree.insert(12);
tree.insert(5);
tree.insert(8);
tree.insert(11);
tree.insert(13);
tree.insert(17);
// Display tree node
Console.Write("\n Inorder \n");
tree.inorder(tree.root);
}
}``````

input

`````` Inorder
Data : 2 [ priority : 61]
Data : 3 [ priority : 92]
Data : 5 [ priority : 30]
Data : 7 [ priority : 94]
Data : 8 [ priority : 51]
Data : 10 [ priority : 30]
Data : 11 [ priority : 93]
Data : 12 [ priority : 68]
Data : 13 [ priority : 91]
Data : 17 [ priority : 14]``````
``````<?php
/*
Php Program for
Treap implementation
*/
//  Treap Tree node
class TreeNode
{
public \$data;
public \$priority;
public \$left;
public \$right;
public	function __construct(\$data)
{
// Set node value
\$this->data = \$data;
\$this->left = NULL;
\$this->right = NULL;
\$this->priority =  rand(1, 100);
}
}
class TreapTree
{
public \$root;
public	function __construct()
{
\$this->root = NULL;
}
// Perform right rotation
public	function rightRotate(\$node)
{
\$temp = \$node->left;
\$point = \$node->left->right;
\$temp->right = \$node;
\$node->left = \$point;
return \$temp;
}
// Perform left rotation
public	function leftRotate(\$node)
{
\$temp = \$node->right;
\$point = \$node->right->left;
\$temp->left = \$node;
\$node->right = \$point;
return \$temp;
}
{
if (\$node == NULL)
{
// Case 1
// return a new tree node
return new TreeNode(\$data);
}
else if (\$data <= \$node->data)
{
// Case 2
// When added data is less than or equal to given node data
if (\$node->left->priority > \$node->priority)
{
// right rotate based on priority
return \$this->rightRotate(\$node);
}
}
else
{
// Case 3
// When added data is greater than to given node data
if (\$node->right->priority > \$node->priority)
{
// left rotate based on priority
return \$this->leftRotate(\$node);
}
}
return \$node;
}
// Handles the request to add new node in Treap
public	function insert(\$data)
{
}
public	function inorder(\$node)
{
if (\$node != NULL)
{
\$this->inorder(\$node->left);
echo(" Data : ".\$node->data.
" [ priority : ".\$node->priority.
"] \n");
\$this->inorder(\$node->right);
}
}
}

function main()
{
\$tree = new TreapTree();
\$tree->insert(7);
\$tree->insert(3);
\$tree->insert(2);
\$tree->insert(10);
\$tree->insert(12);
\$tree->insert(5);
\$tree->insert(8);
\$tree->insert(11);
\$tree->insert(13);
\$tree->insert(17);
// Display tree node
echo("\n Inorder \n");
\$tree->inorder(\$tree->root);
}
main();``````

input

`````` Inorder
Data : 2 [ priority : 98]
Data : 3 [ priority : 99]
Data : 5 [ priority : 24]
Data : 7 [ priority : 27]
Data : 8 [ priority : 47]
Data : 10 [ priority : 16]
Data : 11 [ priority : 5]
Data : 12 [ priority : 15]
Data : 13 [ priority : 89]
Data : 17 [ priority : 23]``````
``````/*
Node JS Program for
Treap implementation
*/
//  Treap Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
this.priority = Math.floor(Math.random() * (100) );
}
}
class TreapTree
{
constructor()
{
this.root = null;
}
// Perform right rotation
rightRotate(node)
{
var temp = node.left;
var point = node.left.right;
temp.right = node;
node.left = point;
return temp;
}
// Perform left rotation
leftRotate(node)
{
var temp = node.right;
var point = node.right.left;
temp.left = node;
node.right = point;
return temp;
}
{
if (node == null)
{
// Case 1
// return a new tree node
return new TreeNode(data);
}
else if (data <= node.data)
{
// Case 2
// When added data is less than or equal to given node data
if (node.left.priority > node.priority)
{
// right rotate based on priority
return this.rightRotate(node);
}
}
else
{
// Case 3
// When added data is greater than to given node data
if (node.right.priority > node.priority)
{
// left rotate based on priority
return this.leftRotate(node);
}
}
return node;
}
// Handles the request to add new node in Treap
insert(data)
{
}
inorder(node)
{
if (node != null)
{
this.inorder(node.left);
process.stdout.write(" Data : " + node.data + " [ priority : " + node.priority + "] \n");
this.inorder(node.right);
}
}
}

function main()
{
var tree = new TreapTree();
tree.insert(7);
tree.insert(3);
tree.insert(2);
tree.insert(10);
tree.insert(12);
tree.insert(5);
tree.insert(8);
tree.insert(11);
tree.insert(13);
tree.insert(17);
// Display tree node
process.stdout.write("\n Inorder \n");
tree.inorder(tree.root);
}
main();``````

input

`````` Inorder
Data : 2 [ priority : 63]
Data : 3 [ priority : 21]
Data : 5 [ priority : 12]
Data : 7 [ priority : 91]
Data : 8 [ priority : 36]
Data : 10 [ priority : 46]
Data : 11 [ priority : 29]
Data : 12 [ priority : 6]
Data : 13 [ priority : 44]
Data : 17 [ priority : 49]``````
``````import math
import random
#    Python 3 Program for
#    Treap implementation

#   Treap Tree node
class TreeNode :
def __init__(self, data) :
#  Set node value
self.data = data
self.left = None
self.right = None
self.priority = random.randint(1,100)

class TreapTree :
def __init__(self) :
self.root = None

#  Perform right rotation
def rightRotate(self, node) :
temp = node.left
point = node.left.right
temp.right = node
node.left = point
return temp

#  Perform left rotation
def leftRotate(self, node) :
temp = node.right
point = node.right.left
temp.left = node
node.right = point
return temp

if (node == None) :
#  Case 1
#  return a new tree node
return TreeNode(data)
elif (data <= node.data) :
#  Case 2
#  When added data is less than or equal to given node data
if (node.left.priority > node.priority) :
#  right rotate based on priority
return self.rightRotate(node)

else :
#  Case 3
#  When added data is greater than to given node data
if (node.right.priority > node.priority) :
#  left rotate based on priority
return self.leftRotate(node)

return node

#  Handles the request to add new node in Treap
def insert(self, data) :

def inorder(self, node) :
if (node != None) :
self.inorder(node.left)
print(" Data : ", node.data ," [ priority : ", node.priority ,"] ")
self.inorder(node.right)

def main() :
tree = TreapTree()
tree.insert(7)
tree.insert(3)
tree.insert(2)
tree.insert(10)
tree.insert(12)
tree.insert(5)
tree.insert(8)
tree.insert(11)
tree.insert(13)
tree.insert(17)
#  Display tree node
print("\n Inorder ")
tree.inorder(tree.root)

if __name__ == "__main__": main()``````

input

`````` Inorder
Data :  2  [ priority :  4 ]
Data :  3  [ priority :  77 ]
Data :  5  [ priority :  31 ]
Data :  7  [ priority :  25 ]
Data :  8  [ priority :  50 ]
Data :  10  [ priority :  90 ]
Data :  11  [ priority :  55 ]
Data :  12  [ priority :  37 ]
Data :  13  [ priority :  62 ]
Data :  17  [ priority :  12 ]``````
``````#    Ruby Program for
#    Treap implementation

#   Treap Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :priority, :left, :right
def initialize(data)
#  Set node value
self.data = data
self.left = nil
self.right = nil
r = Random.new
self.priority = r.rand(1...100)
end

end

class TreapTree
# Define the accessor and reader of class TreapTree
attr_accessor :root
def initialize()
self.root = nil
end

#  Perform right rotation
def rightRotate(node)
temp = node.left
point = node.left.right
temp.right = node
node.left = point
return temp
end

#  Perform left rotation
def leftRotate(node)
temp = node.right
point = node.right.left
temp.left = node
node.right = point
return temp
end

if (node == nil)
#  Case 1
#  return a new tree node
return TreeNode.new(data)
elsif (data <= node.data)
#  Case 2
#  When added data is less than or equal to given node data
if (node.left.priority > node.priority)
#  right rotate based on priority
return self.rightRotate(node)
end

else

#  Case 3
#  When added data is greater than to given node data
if (node.right.priority > node.priority)
#  left rotate based on priority
return self.leftRotate(node)
end

end

return node
end

#  Handles the request to add new node in Treap
def insert(data)
end

def inorder(node)
if (node != nil)
self.inorder(node.left)
print(" Data : ", node.data ,
" [ priority : ", node.priority ,"] \n")
self.inorder(node.right)
end

end

end

def main()
tree = TreapTree.new()
tree.insert(7)
tree.insert(3)
tree.insert(2)
tree.insert(10)
tree.insert(12)
tree.insert(5)
tree.insert(8)
tree.insert(11)
tree.insert(13)
tree.insert(17)
#  Display tree node
print("\n Inorder \n")
tree.inorder(tree.root)
end

main()``````

input

`````` Inorder
Data : 2 [ priority : 26]
Data : 3 [ priority : 48]
Data : 5 [ priority : 49]
Data : 7 [ priority : 1]
Data : 8 [ priority : 23]
Data : 10 [ priority : 51]
Data : 11 [ priority : 60]
Data : 12 [ priority : 9]
Data : 13 [ priority : 2]
Data : 17 [ priority : 43]
``````
``````/*
Scala Program for
Treap implementation
*/
//  Treap Tree node
class TreeNode(var data: Int,
var priority: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data,0,null,null);
this.priority = this.rnd();
}
def rnd() : Int =
{
val r = new scala.util.Random;
return 1 + r.nextInt(99);
}
}
class TreapTree(var root: TreeNode)
{
def this()
{
this(null);
}
// Perform right rotation
def rightRotate(node: TreeNode): TreeNode = {
var temp: TreeNode = node.left;
var point: TreeNode = node.left.right;
temp.right = node;
node.left = point;
return temp;
}
// Perform left rotation
def leftRotate(node: TreeNode): TreeNode = {
var temp: TreeNode = node.right;
var point: TreeNode = node.right.left;
temp.left = node;
node.right = point;
return temp;
}
def addNode(node: TreeNode, data: Int): TreeNode = {
if (node == null)
{
// Case 1
// return a new tree node
return new TreeNode(data);
}
else if (data <= node.data)
{
// Case 2
// When added data is less than or equal to given node data
if (node.left.priority > node.priority)
{
// right rotate based on priority
return rightRotate(node);
}
}
else
{
// Case 3
// When added data is greater than to given node data
if (node.right.priority > node.priority)
{
// left rotate based on priority
return leftRotate(node);
}
}
return node;
}
// Handles the request to add new node in Treap
def insert(data: Int): Unit = {
}
def inorder(node: TreeNode): Unit = {
if (node != null)
{
inorder(node.left);
print(" Data : " + node.data + " [ priority : " + node.priority + "] \n");
inorder(node.right);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: TreapTree = new TreapTree();
tree.insert(7);
tree.insert(3);
tree.insert(2);
tree.insert(10);
tree.insert(12);
tree.insert(5);
tree.insert(8);
tree.insert(11);
tree.insert(13);
tree.insert(17);
// Display tree node
print("\n Inorder \n");
tree.inorder(tree.root);
}
}``````

input

`````` Inorder
Data : 2 [ priority : 91]
Data : 3 [ priority : 50]
Data : 5 [ priority : 96]
Data : 7 [ priority : 33]
Data : 8 [ priority : 79]
Data : 10 [ priority : 52]
Data : 11 [ priority : 59]
Data : 12 [ priority : 22]
Data : 13 [ priority : 78]
Data : 17 [ priority : 27]``````
``````import Foundation;
/*
Swift 4 Program for
Treap implementation
*/
//  Treap Tree node
class TreeNode
{
var data: Int;
var priority: Int;
var left: TreeNode? ;
var right: TreeNode? ;
func random_no() -> Int
{
//Calculate random number
var number: Int = 1;
#if os(Linux)
number = Int(random() % (100))
#else
number = Int(arc4random_uniform(100))
#endif
return number;
}
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
self.priority = 0;
self.priority = random_no();
}

}
class TreapTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
// Perform right rotation
func rightRotate(_ node: TreeNode? ) -> TreeNode?
{
let temp = node!.left;
let point = node!.left!.right;
temp!.right = node;
node!.left = point;
return temp;
}
// Perform left rotation
func leftRotate(_ node: TreeNode? ) -> TreeNode?
{
let temp = node!.right;
let point = node!.right!.left;
temp!.left = node;
node!.right = point;
return temp;
}
func addNode(_ node: TreeNode? , _ data : Int) -> TreeNode?
{
if (node == nil)
{
// Case 1
// return a new tree node
return TreeNode(data);
}
else if (data <= node!.data)
{
// Case 2
// When added data is less than or equal to given node data
if (node!.left!.priority > node!.priority)
{
// right rotate based on priority
return self.rightRotate(node);
}
}
else
{
// Case 3
// When added data is greater than to given node data
if (node!.right!.priority > node!.priority)
{
// left rotate based on priority
return self.leftRotate(node);
}
}
return node;
}
// Handles the request to add new node in Treap
func insert(_ data: Int)
{
}
func inorder(_ node: TreeNode? )
{
if (node  != nil)
{
self.inorder(node!.left);
print(" Data : ", node!.data, " [ priority : ", node!.priority, "] ");
self.inorder(node!.right);
}
}
}
func main()
{
let tree = TreapTree();
tree.insert(7);
tree.insert(3);
tree.insert(2);
tree.insert(10);
tree.insert(12);
tree.insert(5);
tree.insert(8);
tree.insert(11);
tree.insert(13);
tree.insert(17);
// Display tree node
print("\n Inorder ");
tree.inorder(tree.root);
}
main();``````

input

`````` Inorder
Data :  2  [ priority :  77 ]
Data :  3  [ priority :  86 ]
Data :  5  [ priority :  35 ]
Data :  7  [ priority :  83 ]
Data :  8  [ priority :  86 ]
Data :  10  [ priority :  15 ]
Data :  11  [ priority :  92 ]
Data :  12  [ priority :  93 ]
Data :  13  [ priority :  49 ]
Data :  17  [ priority :  21 ]``````
``````/*
Kotlin Program for
Treap implementation
*/
//  Treap Tree node
class TreeNode
{
var data: Int;
var priority: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
this.priority = (Math.random() * (100)).toInt();
}
}
class TreapTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
// Perform right rotation
fun rightRotate(node: TreeNode ? ): TreeNode ?
{
val temp: TreeNode? = node?.left;
val point: TreeNode? = node?.left!!.right;
temp?.right = node;
node.left = point;
return temp;
}
// Perform left rotation
fun leftRotate(node: TreeNode ? ): TreeNode ?
{
val temp: TreeNode? = node?.right;
val point: TreeNode? = node?.right!!.left;
temp?.left = node;
node.right = point;
return temp;
}
fun addNode(node: TreeNode ? , data : Int): TreeNode ?
{
if (node == null)
{
// Case 1
// return a new tree node
return TreeNode(data);
}
else if (data <= node.data)
{
// Case 2
// When added data is less than or equal to given node data
if (node.left!!.priority > node.priority)
{
// right rotate based on priority
return this.rightRotate(node);
}
}
else
{
// Case 3
// When added data is greater than to given node data
if (node.right!!.priority > node.priority)
{
// left rotate based on priority
return this.leftRotate(node);
}
}
return node;
}
// Handles the request to add new node in Treap
fun insert(data: Int): Unit
{
}
fun inorder(node: TreeNode ? ): Unit
{
if (node != null)
{
this.inorder(node.left);
print(" Data : " + node.data +
" [ priority : " + node.priority + "] \n");
this.inorder(node.right);
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: TreapTree = TreapTree();
tree.insert(7);
tree.insert(3);
tree.insert(2);
tree.insert(10);
tree.insert(12);
tree.insert(5);
tree.insert(8);
tree.insert(11);
tree.insert(13);
tree.insert(17);
// Display tree node
print("\n Inorder \n");
tree.inorder(tree.root);
}``````

input

`````` Inorder
Data : 2 [ priority : 34]
Data : 3 [ priority : 35]
Data : 5 [ priority : 68]
Data : 7 [ priority : 93]
Data : 8 [ priority : 23]
Data : 10 [ priority : 67]
Data : 11 [ priority : 2]
Data : 12 [ priority : 38]
Data : 13 [ priority : 4]
Data : 17 [ priority : 46]``````

Time Complexity

• The `addNode` method takes O(log n) time on average, where n is the number of nodes in the treap.
• The rotation methods (`rightRotate` and `leftRotate`) take constant time.
• The `insert` method calls the `addNode` method, so it also takes O(log n) time on average.
• The `inorder` traversal takes O(n) time, where n is the number of nodes in the treap.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post