import net.datastructures.*;

public class verify2 {

	public static void main(String[] args) {
		
		AVLTree tempTree=null;
		BinarySearchTree tempTree2=null;

		int currentNodes=5;
		int nTrees=1000;

		System.out.println("Nodes \t AVL Height \t\t\t BST Height \n");
		System.out.println("\tMin\tMax\tAverage\t\tMin\tMax\tAverage\t\tLog(n)");
		
		for(int i=1; i<=5; i++){ // Different number of nodes
		
			int totalHeight=0;
			int totalHeight2=0;
			int AVL_min=currentNodes,AVL_max=0,BST_min=currentNodes,BST_max=0;

			for(int j=1; j<=nTrees;j++) { // differnt trees with same number of bnodes
				
				tempTree= new AVLTree(); 
				tempTree2= new BinarySearchTree(); 
				
				//		loop to insert all nodes into tree
				for(int k=1; k<=currentNodes;k++){ 
					// creat random key between 0 and currentNode value
					int randKey=(int) (Math.random()*currentNodes);
					// to make sure the genrated random key is not used before!!
					if(tempTree.find(new Integer(randKey))==null){
						tempTree.insert(new Integer(randKey), null);
						tempTree2.insert(new Integer(randKey), null);
					}else k--;
					
				}

				
				//System.out.println(treeHeight(tempTree,tempTree.root()));
				int avlH=treeHeight(tempTree,tempTree.root())-1;
				int bstH=treeHeight(tempTree2,tempTree2.root())-1;
				totalHeight+=avlH;
				totalHeight2+=bstH;
				if(avlH>AVL_max) AVL_max=avlH;
				if(avlH<AVL_min) AVL_min=avlH;
				if(bstH>BST_max) BST_max=bstH;
				if(bstH<BST_min) BST_min=bstH;
			}
			System.out.print(" "+currentNodes+"\t"+AVL_min+"\t"+AVL_max+"\t"+(((double) totalHeight/nTrees)));
			System.out.print("\t\t"+BST_min+"\t"+BST_max+"\t"+(((double) totalHeight2/nTrees)));
			System.out.println("\t\t"+((int)(Math.log(currentNodes)*1000.0)/1000.0));
			currentNodes=currentNodes*2;
		}
	}
	static public int treeHeight(BinaryTree t, Position r){
		if(t.isInternal(r)){
			if(treeHeight(t,t.left(r))>treeHeight(t,t.right(r)))
				return 	treeHeight(t,t.left(r))+1;
			else return treeHeight(t,t.right(r))+1;
		}
		else return 0;	
		
	}
	
}