Treap.java

// YOU SHOULD NOT MODIFY THIS FILE AT ALL.
// (This version will be used by the autograder; not yours!)

import java.util.Comparator;
import java.util.Random;


public class Treap<T> extends
		BinarySearchTree<Treap.Node<T>, T> implements SSet<T> {
	/**
	 * A random number source
	 */
	Random rand;

	protected static class Node<T> extends BinarySearchTree.BSTNode<Node<T>,T> {
		int p;
	}
	
	public Treap(Comparator<T> c) {
		super(new Node<T>(), c);
		rand = new Random();
	}

	public Treap() {
		this(new DefaultComparator<T>());	
	}
	
	public boolean add(T x) {
		Node<T> u = newNode();
		u.x = x;
		u.p = rand.nextInt();
		if (super.add(u)) {
			bubbleUp(u);
			return true;
		}
		return false;
	}

	protected void bubbleUp(Node<T> u) {
		while (u.parent != nil && u.parent.p > u.p) {
			if (u.parent.right == u) {
				rotateLeft(u.parent);
			} else {
				rotateRight(u.parent);
			}
		}
		if (u.parent == nil) {
			r = u;
		}
	}

	public boolean remove(T x) {
		Node<T> u = findLast(x);
		if (u != nil && c.compare(u.x, x) == 0) {
			trickleDown(u);
			splice(u);
			return true;
		}
		return false;
	}

	/**
	 * Do rotations to make u a leaf
	 */
	protected void trickleDown(Node<T> u) {
		while (u.left != nil || u.right != nil) {
			if (u.left == nil) {
				rotateLeft(u);
			} else if (u.right == nil) {
				rotateRight(u);
			} else if (u.left.p < u.right.p) {
				rotateRight(u);
			} else {
				rotateLeft(u);
			}
			if (r == u) {
				r = u.parent;
			}
		}
	}
}