package fha.inf3.tree;
import java.util.*;
/**
* Implements an unbalanced binary search tree.
* Note that all "matching" is based on the compareTo method.
* @author Dominik Gruntz
*/
public class MyBinarySearchTree {
	private MyNode root;
	
	/**
	* Searches an item in the tree.
	* @param key the key to search for.
	* @return the matching item or null if not found.
	*/
	public Object search (Comparable key){
		return search(root, key);
	}
		
	private Object search (MyNode p, Comparable key){
		if(p == null)
			return null;
		else {
			int c = key.compareTo(p.key);
			if (c > 0) return search(p.right, key);
			else if (c < 0) return search(p.left, key);
			else return p.element;
		}
	}
	
	/**
	* Computes the number of nodes in the tree
	* @return size of the tree.
	*/
	public int size(){
		return size(root);
	}
	
	private int size(MyNode p){
		if(p==null)return 0;
		else return 1 + size(p.left) + size(p.right);
	}

	/**
	* Test if the tree is logically empty.
	* @return true if empty, false otherwise.
	*/
	public boolean isEmpty( ) {
		return root == null;
	}

	/**
	* Insert a value into the tree; if an element is already stored under
	* the given key the element is replaced by the new one.
	* @param key key with which the specified element is to be associated.
	* @param element element to be inserted into the tree.
	*/
	public void insert (Comparable key, Object element){
		root = insert(root, key, element);
	}

	/**
	* Internal method to insert into a subtree.
	* @param p the node that roots the tree.
	* @param key the key of the element to insert.
	* @param element the element to insert.
	* @return the new root.
	*/
	private MyNode insert(MyNode p, Comparable key, Object element){
		if (p==null) 
			return new MyNode(key, element);
		else {
			int c = key.compareTo(p.key);
			if (c < 0)
				p.left = insert(p.left, key, element);				
			else if(c > 0)
				p.right = insert(p.right, key, element);
			else
				p.element = element;
			return p;
		}
	}
	
	public String toString(){
		return root == null ? "[]" : root.toString();
	}

				
	/**
	* Remove from the tree. Nothing is done if key is not found.
	* @author Thomas Tardy
	* @param key the item to remove.
	*/
	public MyNode remove (Comparable key){
		if (key.compareTo(root.key) == 0) {
			if (root.left == null) {
				root = root.right;
			}
			else if (root.right == null) {
				root = root.left;
			}
			else {
				merge(root.left, root.right);
				root = root.left;
			}
		}
		else {
			MyNode parent = searchParent(root, key);
			MyNode toRemove = searchNode(root, key);
			MyNode newNode = null;
			if (toRemove != null) {
				if (toRemove.left == null) {
					newNode = toRemove.right;
				}
				else if (toRemove.right == null) {
					newNode = toRemove.left;
				}
				else {
					merge(toRemove.left, toRemove.right);
					newNode = toRemove.left;
				}
				if (parent.left == toRemove) {
					parent.left = newNode;
				}
				else {
					parent.right = newNode;
				}
			}
		}
		return root;
	}

	/**
	* Merge the addNode to the mainNode.
	* @author Thomas Tardy
	* @param mainNode Node, which becomes new Nodes.
	* @param addNode Node to add.
	*/
	private void merge (MyNode mainNode, MyNode addNode) {
		while (mainNode.right != null) {
			mainNode = mainNode.right;
		}
		mainNode.right = addNode;
	}

	/**
	* Search an Node in the tree.
	* @author Thomas Tardy
	* @param p node to check.
	* @param key the item to search.
	* @return Node with the key.
	*/
	private MyNode searchNode (MyNode p, Comparable key){
		if(p == null)
			return null;
		else {
			int c = key.compareTo(p.key);
			if (c > 0) return searchNode(p.right, key);
			else if (c < 0) return searchNode(p.left, key);
			else return p;
		}
	}

/**
	* Search the parent of a Node in the tree.
	* @author Thomas Tardy
	* @param key the item to search.
	* @return Node, which is the parent of the Node with key.
	*/
	private MyNode searchParent (MyNode p, Comparable key){
		if(p == null || (p.left == null && p.right == null)) {
			return null;
		}
		int c = key.compareTo(p.key);
		if (c > 0) {
			if (p.right == null) {
				return null;
			}
			else if (key.compareTo(p.right.key) == 0) {
				return p;
			}
			return searchParent(p.right, key);
		}
		else if	(c < 0) {
			if (p.left == null) {
				return null;
			}
			if (key.compareTo(p.left.key) == 0) {
				return p;
		}
			return searchParent(p.left, key);
		}
		else {
			return null;
		}
	}
	
	/**
	 * Solve the height of the tree.
	 * @author tardy
	 * @return the height of the tree.
	 */
	public int height() {
		return height(root);
	}
	
	/**
	 * Solve the maximum height of the two children of the given node.
	 * @author tardy
	 * @param root the parent of the children.
	 * @return the maximum height of the two children.
	 */
	private int height(MyNode root) {
		if (root == null) {
			return -1;
		}
		int left = height(root.left);
		int right = height(root.right);
		if (left > right) {
			return left+1;
		}
		else {
			return right+1;
		}
	}
	
	public void showHeight(int teil, int max) {
		Random rand = new Random();
		int k;
		for(int i = 0; i < max; i++) {
			Integer INT = new Integer(rand.nextInt());
			this.insert(INT, INT);
			if (i != 0 && i%teil == 0) {
				System.out.println("n = " + i + "\t\tHoehe = " + this.height() + "\t\tHoehe / log2(n) = " + (Math.log(this.height()/Math.log(2))));
			}
		}
	}
}

class MyNode {
	Comparable key;
	Object element;
	MyNode left, right;
	
	MyNode(Comparable key){this(key, null);}
	MyNode(Comparable key, Object element){
		this.key = key; this.element = element;
	}
	MyNode(Comparable key, Object element, MyNode left, MyNode right){
		this(key, element); this.left = left; this.right = right;
	}
	
	public String toString(){
		if(left == null && right == null)
			return "[" + key + "]";
		else
			return "[" + key + (left !=null?left.toString():"[]") 
				   		 + (right!=null?right.toString():"[]") + "]";
	}		

}