Binary Search Trees.java

//Binary Search Tree: java implementation
private class Node {
	private Key key;
	private Value val;
	private Node left, right;
	public Node(Key key, Value, val){
		this.key = key;
		this.val = val;
	}
}
public Value get(Key key) {
	Node x = root;
	while (x!=null){
		int cmp = key.compareTo(x.key);
		if (cmp < 0) x = x.left;
		else if (cmp > 0) x = x.right;
		else return x.val;
	}
	return null;
}
public void put(Key key, Value val) {
	root = put (root, key, val);
}
private Node put(Node x, Key key, Value val) {
	if (x == null) return new Node(key, val);
	int cmp = key.compareTo(x.key);
	if (cmp < 0)
		x.left = put(x.left, key, val);
	else if (cmp > 0)
		x.right = put(x.right, key, val);
	else
		x.val = val;
	return x;
}
//computing the floor: largest key less than given key
public Key floor(Key key) {
	Node x = floor (root , key);
	if (x == null) return null;
	return x.key;
}
private Node floor (Node x, Key key) {
	if (x == null) return null;
	int cmp = key.compareTo(x.key);
	if(cmp == 0) return x;
	if(cmp < 0) return floor(x.left, key);
	Node t = floor(x.right, key);
	if(t != null) return t;
	else return x; //t == null right subtree 里面没有floor
}
//subtree counts
private class Node {
	private Key key;
	private Value val;
	private Node left;
	private Node right;
	private int count;
}
public int size(){
	return size(root);
}
private int size(Node x) {
	if(x == null) return 0;
	return x.count;
}
public void put(Key key, Value val) {
    root = put (root, key, val);
}
private Node put(Node x, Key key, Value val) {
    if (x == null) return new Node(key, val);
    int cmp = key.compareTo(x.key);
    if (cmp < 0)
        x.left = put(x.left, key, val);
    else if (cmp > 0)
        x.right = put(x.right, key, val);
    else
        x.val = val;
	x.count = 1 + size(x.left) + size.(x.right); // one more line
    return x;
}

//Rank: how many keys < k?
public int rank (Key, key){
	return rank(key, root);
}
private int rank(Key key, Node x) {
	if (x == null) return 0;
	int cmp = key.compareTo(x.key);
	if (cmp < 0) return rank(key, x.left);
	else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right);
	else if (cmp == 0) return size(x.left);
}

//Inorder traversal
public Iterable<Key> keys(){
	Queue<Key> q = new Queue<Key>();
	inorder(root, q);
	return q;
}
private void inorder (Node x, Queue<Key> q) {
	if(x == null) return;
	inorder(x.left, q);
	q.enqueue(x.key);
	inorder(x.right, q);
}

//delete the minimum
public void deleteMin() {
	root = deleteMin(root);
}
private Node deleteMin(Node x) {
	if(x.left == null) return x.right;
	x.left = deleteMin(x.left);
	x.count = 1 +size(x.left) + size(x.right);
	return x;
}

//Hibbard deletion:delete a node with key k, search for node t containing key k.Find successor x of t which is the minimum in t's right subtree. put x in t's spot.
public void delete(Key,key) {
	root = delete(root, key);
}
private Node delete(Node x, Key, key) {
	if (x == null) return null;
	int cmp = key.compareTo(x.key);	
	if (cmp < 0) x.left = delete(x.left, key); //search for key
	else if(cmp > 0) x.right = delete(x.right, key);
	else {
		if(x.right == null) return x.left; //no right child
		if(x.left == null) return x.right; // no left child
		Node t = x;
		x = min(t.right);
		x.right = deleteMin(t.right);
		x.left = t.left;
	}
	x.count = size(x.left) + size(x.right) + 1;
	return x;
}