Skip to main content

Treap implementation

Here given code implementation process.

/*
    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 
			node.left = addNode(node.left, 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
			node.right = addNode(node.right, 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)
	{
		this.root = this.addNode(this.root, 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();
		// Add tree node
		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;
	}
	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 
			node->left = this->addNode(node->left, 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
			node->right = this->addNode(node->right, 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)
	{
		this->root = this->addNode(this->root, 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();
	// Add tree node
	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 
			node.left = this.addNode(node.left, 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
			node.right = this.addNode(node.right, 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)
	{
		this.root = this.addNode(this.root, 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();
		// Add tree node
		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;
	}
	public	function addNode($node, $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 
			$node->left = $this->addNode($node->left, $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
			$node->right = $this->addNode($node->right, $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)
	{
		$this->root = $this->addNode($this->root, $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();
	// Add tree node
	$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;
	}
	addNode(node, 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 
			node.left = this.addNode(node.left, 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
			node.right = this.addNode(node.right, 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)
	{
		this.root = this.addNode(this.root, 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();
	// Add tree node
	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
	
	def addNode(self, node, data) :
		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 
			node.left = self.addNode(node.left, 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
			node.right = self.addNode(node.right, 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) :
		self.root = self.addNode(self.root, 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()
	#  Add tree node
	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_reader :data, :priority, :left, :right
	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_reader :root
	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

	def addNode(node, data) 
		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 
			node.left = self.addNode(node.left, 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
			node.right = self.addNode(node.right, 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) 
		self.root = self.addNode(self.root, 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()
	#  Add tree node
	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 
			node.left = addNode(node.left, 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
			node.right = addNode(node.right, 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 = {
		this.root = this.addNode(this.root, data);
	}
	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();
		// Add tree node
		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 
			node!.left = self.addNode(node!.left, 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
			node!.right = self.addNode(node!.right, 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)
	{
		self.root = self.addNode(self.root, data);
	}
	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();
	// Add tree node
	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 
			node.left = this.addNode(node.left, 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
			node.right = this.addNode(node.right, 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
	{
		this.root = this.addNode(this.root, data);
	}
	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();
	// Add tree node
	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]
Last updated on by Kalkicode




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.

New Comment