Treap.java

package general;
import java.util.Random;
import java.util.Stack;

public class Treap<E extends Comparable<E>>{
	private class Node<E>{
		public E data;// key for the search
		public int priority;// random heap priority
		public Node<E> left;
		public Node<E> right;
		
		//Creates a new node with the given data and priority. The pointers to child nodes are
		//null. Throw exceptions if data is null
		public Node(E data, int priority) 
		{
			//check if values are null
			if (data == null) 
			{
				throw new IllegalArgumentException();
			} 
			else 
			{
				this.data = data;
				this.priority = priority;
				this.left = null;
				this.right = null;
			}
		}
		//rotateRight() performs a right rotation, Update the data and priority attributes as well as the left and right pointers of the involved nodes accordingly
		public Node<E> rotateRight() 
		{
			Node<E> first = this.left;
			Node<E> left = first.right;
			first.right = this;
			this.left = left;
			return first;
		}	
		//performs a left rotation, Update the data and priority attributes as well as the left and right pointers of the involved nodes accordingly
		public Node<E> rotateLeft() 
		{
			Node<E> first = this.right;
			Node<E> right = first.left;
			first.left = this;
			this.right = right;
			return first;
		}
	}
	
	private Random priorityGenerator;
	private Node<E> root;
	
	public Treap() 
	{
		root = null;
		priorityGenerator = new Random();
	}
	
	public Treap(long seed) 
	{
		root = null;
		priorityGenerator = new Random(seed);
	}
	
	public void reheap(Node<E> val, Stack<Node<E>> route) 
	{
		while (!route.isEmpty()) 
		{
			Node<E> parent = route.pop();
			if (parent.priority < val.priority)
			{
				if (parent.data.compareTo(val.data) > 0) 
				{
					val = parent.rotateRight();
				} 
				else 
				{
					val = parent.rotateLeft();
				}
				if (!route.isEmpty()) 
				{
					if (route.peek().left == parent) 
					{
						route.peek().left = val;
					} 
					else 
					{
						route.peek().right = val;
					}
				} 
				else 
				{ 
					this.root = val;
				}
			} 
			else 
			{
				break;
			}
		}
	}
	
	boolean add(E key, int priority) {
		if (root == null) 
		{
			root = new Node<E>(key, priority);
			return true;
		} 
		else 
		{
			Stack<Node<E>> temp = new Stack<Node<E>>();
			Node<E> temp2 = new Node<E>(key, priority);
			
			Node<E> current = root;
			while (current != null) 
			{
				int comparison = current.data.compareTo(key);
				if (comparison == 0) 
				{
					return false;
				} 
				else 
				{
					if (comparison < 0) 
					{
						temp.push(current);
						if (current.right == null) 
						{
							current.right = temp2;
							reheap(temp2, temp);
							return true;
						} 
						else 
						{
							current = current.right;
						}
					} 
					else 
					{
						temp.push(current);
						if (current.left == null) 
						{
							current.left = temp2;
							reheap(temp2, temp);
							return true;
						} 
						else 
						{
							current = current.left;
						}
					}
				}
			}
			return false;
		}
	}
//To insert the given element into the tree, create a new node containing key as its data and
//a random priority generated by priorityGenerator	
	boolean add(E key) {
		return add(key, priorityGenerator.nextInt());
	}
	//deletes the node with the given key from the treap and returns true. If
	//the key was not found, the method does not modify the treap and returns false
	private Node<E> deletehelper(E key, Node<E> val){
		if (val == null) 
		{
			return val;
		} 
		else 
		{
			if (val.data.compareTo(key) < 0) 
			{
				val.right = deletehelper(key, val.right);
			} 
			else 
			{
				if (val.data.compareTo(key) > 0) 
				{
					val.left = deletehelper(key, val.left);
				} 
				else 
				{
					if (val.right == null) 
					{
						val = val.left;
					} 
					else if (val.left == null) 
					{
						val= val.right;
					} 
					else 
					{
						if (val.right.priority < val.left.priority) 
						{
							val = val.rotateRight();
							val.right = deletehelper(key, val.right);
						} 
						else 
						{
							val = val.rotateLeft();
							val.left = deletehelper(key, val.left);
						}
					}
				}
			}
		}
		return val;
	}

	public boolean delete(E key) {
		if (root == null || find(key) == false) 
		{
			return false;
		} 
		else 
		{
			root = deletehelper(key, root);
			return true;
		}
	}
	//Finds a node with the given key in the treap rooted
	//at root and returns true if it finds it and false otherwise
	private boolean find(Node<E> n, E key) {
		if (n == null) 
		{	
			return false;
		} 
		else 
		{
			int comparison = n.data.compareTo(key);
			if (comparison == 0) 
			{
				return true;
			} 
			else 
			{
				return find(n.right, key) || find(n.left, key);
			}
		}
	}

	public boolean find(E key) {
		return find(root, key);
	}

	private String stringhelp(Node<E> val, int x) {
		StringBuilder total = new StringBuilder();
		for (int i=0;i<x;i++) 
		{
			total.append("--");
		}
		if (val==null)
		{
			total.append("null");
		} else 
		{
			total.append("(key = " + val.data +", priority = " + val.priority + ")" );
			total.append("\n");
			total.append(stringhelp(val.left, x+1));
			total.append("\n");
			total.append(stringhelp(val.right, x+1));
		}
		return total.toString();
		
	}
	
// Carries out a preorder traversal of the tree and returns a representation of the nodes as a string.
	public String toString() 
	{
		return stringhelp(root,0);
	}
	
	public static void main(String[] args) {
		Treap<Integer> testTree = new Treap<Integer>();
		testTree.add(4,19);
		testTree.add(2,31);
		testTree.add(6,70);
		testTree.add(1,84);
		testTree.add(3,12);
		testTree.add(5,83);
		testTree.add(7,26);
	}
}