Binary Search Tree with duplicates allowed

bst.java

public class bst<Key extends Comparable<Key>,Value> {
	
	private Node root;
	
	private class Node{
		Node(Key k,Value v, int n){
			this.key = k; this.val = v; this.N = n;
		}
		
		Key key;
		Value val;
		Node left,right;
		int N;
		
	}
	
	/*****************************************************
	 * SIZE IMPLEMENTATION
	 * ***************************************************/
	
	public int size(){
		return size(root);
	}
	
	private int size(Node x){
		if(x==null) return 0;
		else return x.N;
	}
	
	/*****************************************************
	 * GET IMPLEMENTATION
	 * ***************************************************/
	
	public Value get(Key key){
		return get(root,key);
	}
	
	private Value get(Node x, Key key){
		if(x==null) return null;
		int cmp = key.compareTo(x.key);
		if(cmp<0) return get(x.left,key);
		else if (cmp>0) return get(x.right,key);
		else return x.val;
	}
	
	/*****************************************************
	 * PUT IMPLEMENTATION
	 * ***************************************************/	
	
	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,1);
		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);
		
		x.N = size(x.left)+ size(x.right) + 1;
		return x;
	}
	
	/*****************************************************
	 * MIN IMPLEMENTATION
	 * ***************************************************/	
	
	public Key min(){
		return min(root).key;
	}
	
	private Node min(Node x){
		if(x.left == null) return x;
		return min(x.left);
	}
	
	/*****************************************************
	 * FLOOR IMPLEMENTATION
	 * ***************************************************/	
	
	public Key floor(Key key){
		Node x = floor(root,key);
		if(x==null) return null;
		else 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;
	}
	
	/*****************************************************
	 * SELECT IMPLEMENTATION
	 * ***************************************************/	
	
	public Key select(int k){
		return select(root,k).key;
	}
	
	private Node select(Node x,int k){
		if(x==null) return null;
		int t = size(x.left);
		if(t>k) return select(x.left,k);
		else if(t<k) return select(x.right,k-t-1);
		else return x;
	}
		
	
	/*****************************************************
	 * RANK IMPLEMENTATION - returns number of keys less than a key
	 * ***************************************************/	
	
	public int rank(Key key){
		return rank(root,key);
	}
	
	private int rank(Node x, Key key){
		if(x==null) return 0;
		int cmp = key.compareTo(x.key);
		if(cmp <0) return rank(x.left,key);
		else if(cmp>0) return 1+size(x.left)+rank(x.right,key);
		else return size(x.left);
	}
	

	/*****************************************************
	 * DELETEMIN IMPLEMENTATION
	 * ***************************************************/	
	
	public void deletemin(){
		root = deletemin(root);
	}
	
	private Node deletemin(Node x){
		if(x.left == null) return x.right;
		x.left = deletemin(x.left);
		x.N = size(x.left)+size(x.right)+1;
		return x;
	}
	
	/*****************************************************
	 * DELETE IMPLEMENTATION
	 * ***************************************************/	
	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);
		else if(cmp>0) x.right = delete(x.right,key);
		else{
			
			if(x.left == null) return x.right;
			if(x.right == null) return x.left;
			
			Node t = x;
			x = min(t.right);
			x.right = deletemin(t.right);
			x.left = t.left;
			
		}
		x.N = size(x.left)+ size(x.right)+ 1;
		return x;
	}
	
	/*****************************************************
	 * PRINT IMPLEMENTATION
	 * ***************************************************/	
	
	public void printOrder(){
		String st = printOrder(root);
		StdOut.print(st);
	}
	
	private String printOrder(Node x){
		if(x== null) return "";
		String st = "";
		st = printOrder(x.left)+ x.val + printOrder(x.right);
		return st;
	}
	
	/*****************************************************
	 * HEIGHT IMPLEMENTATION
	 * ***************************************************/	
	
	
	public int height(){
		return height(root);
	}
	
	private int height(Node x){
		if(x==null) return 0;
		if( 1+height(x.left)<= 1+height(x.right)){
			return 1+height(x.right);
		} else {
			return 1+height(x.left);
		}
	}
	
	
	
}