Description of the Algorithm
According to the definition of problem set 01, it gives the basic idea of binary search tree insert and then performing relevant rotations to restore the min-heap property. Each insertion to this data structure comprises of a key and a unique priority.
Conditions
ü if v is a left child of u, then key[v] < key[u]
ü if v is a right child of u, then key[v] > key[u]
ü if v is a child of u, then priority(v) > priority(u)
Assumptions
ü I expect that user will enter all the requests and then try to view the tree.
ü User will input valid inputs. (I have not validated the user inputs)
Pseudo Code of the Algorithm
Element x
While x != root and priority (x) < priority of parent (x)
BEGIN
if current root == nullNode
THEN
root == x;
If key of x < =key of parent WE CAN CHECK EQUALITY AND LESS THAN IF WE WANT TO ACCEPT DUPLICATE KEYS.
Insert into left child.
If priority of x > priority of parent
BEGIN RotateWithLeftChild(x);
END IF
END IF
If key of x > key of parent
BEGIN
Insert into left child.
THEN If priority of x < priority of parent
BEGIN
RotateWithRightChild(x);
END IF
END IF
END WHILE
Running time of the Algorithm
A treap with n nodes is equivalent to a randomly built binary search tree with n nodes. Because that assigning priorities to nodes as they are inserted into the treap is the same as inserting to the binary search tree n nodes in the increasing order defined by their priorities. So if we assign the priorities randomly, we get a random order of n priorities, which is the same as a random permutation of the n inputs, so we can view this as inserting the n items in random order.
TREAP-INSERT first inserts an item in the tree using the normal binary search tree
insert and then performs a number of rotations to restore the min-heap property. The normal binary-search-tree insertion algorithm TREE-INSERT always places the new item at a new leaf of tree. Therefore the time to insert an item into a treap is proportional to the height of a randomly built binary search tree, which as we saw in lecture is O(lg n) in expectation.
The maximum number of rotations occurs when the new item receives a priority less than all priorities in the tree. In this case it needs to be rotated from a leaf to the root. An upper bound on the number of rotations is therefore the height of a randomly built binary search tree, which is O(lg n) in expectation.
Because each rotation take constant time, the expected time to rotate is O(lg n).
Sources
/* Roshan Fernando
* Orginal Author Mark Weiss
* 2011-01-15
*/
package ProblemSet01;
// Basic node stored in treaps
import java.util.Random;
/** Note that this class is not accessible outside
* of package ProblemSet01
*/
class TreapNode {
private static Random randomObj = new Random();
// Constructors
TreapNode(Comparable theElement) {
this(theElement, null, null, 0);
}
TreapNode(Comparable theElement, TreapNode lt, TreapNode rt, int prior) {
element = theElement;
left = lt;
right = rt;
priority = prior;//randomObj.nextInt();
}
/**
* can use this Overload for the
* Auto generated Priorites
* @param theElement
* @param lt
* @param rt
*/
TreapNode(Comparable theElement, TreapNode lt, TreapNode rt) {
element = theElement;
left = lt;
right = rt;
priority = randomObj.nextInt();
}
// Friendly data; accessible by other package routines
Comparable element; // The data in the node
TreapNode left; // Left child
TreapNode right; // Right child
int priority; // Priority
}
/* Roshan Fernando
* Orginal Author Mark Weiss
* 2011-01-15
*/
package ProblemSet01;
import java.util.Random;
import java.util.Stack;// this is for the printing purpose only.
import java.util.Scanner;
public class Treap {
private TreapNode root;
private static TreapNode nullNode;
static // Static initializer for NullNode
{
nullNode = new TreapNode(null);
nullNode.left = nullNode.right = nullNode;
nullNode.priority = Integer.MAX_VALUE;
}
public Treap() {
root = nullNode;
}
/**
* Insert into the tree.
* @param x the item to insert.
* @param pr the priority
*/
public void insert(Comparable x, int pr) {
root = insert(x, root, pr);
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty() {
return root == nullNode;
}
/**
* Print the tree contents in sorted order.
*/
public void printTree() {
if (isEmpty()) {
System.out.println("Empty tree");
} else {
printTree(root);
}
}
/**
* Internal Overloaded method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the tree.
* @param pr the priority of the new Item.
* @return the new root.
*/
private TreapNode insert(Comparable x, TreapNode t, int pr) {
if (t == nullNode) {
t = new TreapNode(x, nullNode, nullNode, pr);
} else if (x.compareTo(t.element) <= 0) {
t.left = insert(x, t.left, pr);
if (t.left.priority <= t.priority) {
t = rotateWithLeftChild(t);
}
} else if (x.compareTo(t.element) > 0) {
t.right = insert(x, t.right, pr);
if (t.right.priority < t.priority) {
t = rotateWithRightChild(t);
}
}
return t;
}
/**
* Internal Overloaded method to insert into a subtree.
* for auto Generated priority.
* @param x the item to insert.
* @param t the node that roots the tree.
* @return the new root.
*/
private TreapNode insert(Comparable x, TreapNode t) {
if (t == nullNode) {
t = new TreapNode(x, nullNode, nullNode);
} else if (x.compareTo(t.element) <= 0) {
t.left = insert(x, t.left);
if (t.left.priority < t.priority) {
t = rotateWithLeftChild(t);
}
} else if (x.compareTo(t.element) > 0) {
t.right = insert(x, t.right);
if (t.right.priority < t.priority) {
t = rotateWithRightChild(t);
}
}
return t;
}
/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the tree.
*/
private void printTree(TreapNode t) {
if (t != t.left) {
printTree(t.left);
System.out.println(t.element.toString() + "\t[" + t.priority + "]");
printTree(t.right);
}
}
/**
* Rotate binary tree node with left child.
*/
private static TreapNode rotateWithLeftChild(TreapNode k2) {
TreapNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
return k1;
}
/**
* Rotate binary tree node with right child.
*/
private static TreapNode rotateWithRightChild(TreapNode k1) {
TreapNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
return k2;
}
/**
* Generates a letter,
* Duplicates are allowed.
* @return char Alphabet
*/
private static char letterGenerate() {
char alphabet[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
Random generator = new Random();
return alphabet[generator.nextInt(25)];
}
/**
* just to print the treap
*/
public void displayTree() {
System.out.println(" ! ... Visual Tree ... !");
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println("......................................................");
while (isRowEmpty == false) {
Stack localStack = new Stack();
isRowEmpty = true;
for (int j = 0; j < nBlanks; j++) {
System.out.print(" ");
}
while (globalStack.isEmpty() == false) {
TreapNode temp = (TreapNode) globalStack.pop();
if (temp != null && temp.element != null) {
System.out.print(temp.element + "[" + temp.priority + "]");
localStack.push(temp.left);
localStack.push(temp.right);
if (temp.left != null || temp.right != null) {
isRowEmpty = false;
}
} else {
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for (int j = 0; j < nBlanks * 2 - 2; j++) {
System.out.print(" ");
}
} // end while globalStack not empty
System.out.println();
nBlanks /= 2;
while (localStack.isEmpty() == false) {
globalStack.push(localStack.pop());
}
} // end while isRowEmpty is false
System.out.println("......................................................");
}
/**
* for manual input to the tree
* @param obj
* @return Treap
*/
private static Treap manualInput(Treap objTreap) {
Scanner objRead = new Scanner(System.in);
boolean isContinue = true;
try {
do {
System.out.println("Please Enter a Literal ");
char element = objRead.next().trim().charAt(0);
System.out.println("Please enter a priority (Integer)");
int pr = objRead.nextInt();
objTreap.insert(element, pr);
System.out.println("if you want to continue press 1,\n press any other key to exit.");
isContinue = objRead.next().trim().equals("1");
} while (isContinue);
} catch (Exception e) {
System.out.println("Error " + e.getMessage());
} finally {
return objTreap;
}
}
/**
* auto Generated Insert to tree
* @param objTreap
* @return objTreap
*/
private static Treap autoGenerate(Treap objTreap) {
Scanner objRead = new Scanner(System.in);
boolean isContinue = true;
do {
char c = letterGenerate();
int pr = new Random().nextInt();
System.out.println("Generated Alphabel character\t" + c + " priority [" + pr + "]");
objTreap.insert(c, pr);
System.out.println("if you want to continue press 1,\n press any other key to exit.");
isContinue = objRead.next().trim().equals("1");
} while (isContinue);
return objTreap;
}
// Test program
public static void main(String[] args) {
Treap objTreap = new Treap();
// checking the given values with their priorities.
objTreap.insert('A', 10);
objTreap.insert('B', 7);
objTreap.insert('E', 23);
objTreap.insert('G', 4);
objTreap.insert('H', 5);
objTreap.insert('K', 65);
objTreap.insert('I', 73);
objTreap.insert('C', 25);
objTreap.insert('D', 9);
objTreap.insert('F', 2);
Scanner objRead = new Scanner(System.in);
System.out.println("Press 0 for auto Generation, Press 1 for Manual inputs");
int intOption = objRead.nextInt();
switch (intOption) {
case 0:
objTreap = autoGenerate(objTreap);
break;
case 1:
objTreap = manualInput(objTreap);
break;
default:
System.out.println("Errorneous input");
}
System.out.println("! ... in Order Traversal ... !");
objTreap.printTree();
objTreap.displayTree();
}
}
No comments:
Post a Comment