Good Evening, I have nearly finished my code. But for some reason when I am trying to print out my treap function. It seems as though it it missing certain nodes. Below you will see my code. With sample input, my actual output, then my desired output. Any assistance with what I may be doing wrong would be greatly appreciated.
import java.util.Random;
import java.util.Stack;
public class Treap <E extends Comparable<E>>{
private Random priorityGenerator;
private Node<E> root;
public Treap() {
root = null;
priorityGenerator = new Random();
}
public Treap(long seed) {
root = null;
priorityGenerator = new Random(seed);
}
private static class Node<E> {
public E data; //key for the search
public int priority; //random heap priority
public Node <E> left;
public Node <E> right;
/**This constructor creates an instance of the node class and passes through a data
* or key that will come into play later for searching for the node. As well as a
* heap priority. The head will have to be maintained throughout the code for it to be
* considered a treap
* @param data
* @param priority
*/
public Node (E data, int priority) {
if (data == null) {
throw new IllegalArgumentException("Data is Null");
}
this.data = data;
this.priority = priority;
this.left = null;
this.right = null;
}
/**implementation of rotateRight */
Node<E> rotateRight() {
Node<E> newRoot = new Node<E>(this.data, this.priority);
newRoot.right = this.right;
if (this.left.right != null) {
newRoot.left = this.left.right;
}
this.data = this.left.data;
this.priority = this.left.priority;
this.right = newRoot;
if (this.left.left != null) {
this.left = this.left.left;
} else {
this.left = null;
}
return newRoot;
}
/**implementation of rotateLeft */
Node<E> rotateLeft() {
Node<E> newRoot = new Node<E>(this.data, this.priority);
newRoot.left = this.left;
if (this.right.left != null) {
newRoot.right = this.right.left;
}
this.data = this.right.data;
this.priority = this.right.priority;
this.left = newRoot;
if (this.right.right != null) {
this.right = this.right.right;
} else {
this.right = null;
}
return newRoot;
}
}
boolean add(E key) {
int priority = priorityGenerator.nextInt();
return add(key, priority);
}
boolean add(E key, int priority) {
Node<E> newNode = new Node<E>(key, priority);
if (root == null) {
root = newNode;
return true;
}
Node<E> curr = root;
Stack<Node<E>> stack = new Stack<>();
while (curr != null) {
int cmp = key.compareTo(curr.data);
if (cmp == 0) {
return false; // key already exists, no need to add again
}
stack.push(curr);
if (cmp < 0) {
if (curr.left == null) {
curr.left = newNode;
reheap(stack, newNode);
return true;
}
curr = curr.left;
} else {
if (curr.right == null) {
curr.right = newNode;
reheap(stack, newNode);
return true;
}
curr = curr.right;
}
}
return false; // should never reach this point
}
private void reheap(Stack<Node<E>> stack, Node<E> curr) {
while (!stack.empty()) {
Node<E> parent = stack.pop();
if (parent.priority > curr.priority) {
return; // heap invariant already satisfied
}
if (curr == parent.left) {
parent.rotateRight();
} else {
parent.rotateLeft();
}
}
// if we reach this point, we have rotated the root node
root = curr;
}
/**Delete method, that was delete a desired node */
public boolean delete(E key) {
Node<E> curr = root;
Node<E> parent = null;
Stack<Node<E>> stack = new Stack<>();
while (curr != null) {
int cmp = key.compareTo(curr.data);
if (cmp == 0) {
break;
}
parent = curr;
stack.push(parent);
if (cmp < 0) {
curr = curr.left;
} else {
curr = curr.right;
}
}
if (curr == null) {
return false; // key not found
}
while (curr.left != null || curr.right != null) {
if (curr.right == null || (curr.left != null && curr.left.priority > curr.right.priority)) {
curr.rotateRight();
if (parent == null) {
root = curr;
} else if (parent.left == curr) {
parent.left = curr;
} else {
parent.right = curr;
}
parent = curr;
curr = curr.right;
} else {
curr.rotateLeft();
if (parent == null) {
root = curr;
} else if (parent.left == curr) {
parent.left = curr;
} else {
parent.right = curr;
}
parent = curr;
curr = curr.left;
}
}
if (parent == null) {
root = null;
} else if (parent.left == curr) {
parent.left = null;
} else {
parent.right = null;
}
return true;
}
/**Find operation */
/**
* Recursively 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> root, E key) {
if (root == null) {
return false;
}
int cmp = key.compareTo(root.data);
if (cmp == 0) {
return true;
} else if (cmp < 0) {
return find(root.left, key);
} else {
return find(root.right, key);
}
}
/**
* Finds a node with the given key in the treap and returns true if it finds it
* and false otherwise.
*/
public boolean find(E key) {
return find(root, key);
}
/** toString operation */
public String toString() {
return toString(root);
}
private String toString(Node<E> node) {
if (node == null) {
return "null";
}
String leftString = toString(node.left);
String rightString = toString(node.right);
String nodeString = "(key = " + node.data.toString() + " , priority = " + node.priority + ")";
if (node.left == null && node.right == null) {
return nodeString;
} else if (node.left == null) {
return nodeString + " (null) " + rightString;
} else if (node.right == null) {
return nodeString + " " + leftString + " (null)";
} else {
return nodeString + " " + leftString + " " + rightString;
}
}
}
Main function !
public class main_ {
public static void main(String[] args) {
Treap<Integer> testTree = new Treap <Integer>();
// Add nodes to the treap
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);
// Print the treap using the toString method
System.out.println(testTree.toString());
}
}
actual output:
(key = 1 , priority = 84) (null) (key = 5 , priority = 83) (key = 3 , priority = 12) (key = 7 , priority = 26)
desired output:
(key =1 , priority =84)
null
( key =5 , priority =83)
( key =2 , priority =31)
null
( key =4 , priority =19)
( key =3 , priority =12)
null
null
null
( key =6 , priority =70)
null
( key =7 , priority =26)
null
besides it printing on a new line. You can see that I am missing some nodes.
I don't exactly understand what you wanna do. But I consider there's something wrong with the
reheapfunction. Therootshouldn't be assigned ascurrsince it seems to me thatparentis still the root of the subtree after rotation. Another point is that in thereheapfunction you usecurr == parent.leftwhich uses memory address not value for comparison. But in therotatefunction you actually create a new Node object.