import java.util.*;
import java.lang.*;
import java.io.*;
 
class Tree <Key extends Comparable<Key>, Value> {
	
	private class Node {
		Key key;
		Value value;
		Node left, right;
		public Node (Key key, Value value) {
			this.key = key;
			this.value = value;
			this.left = this.right = null;
		}
	}
	
	private Node root;
	
	public Key getRootKey(){
		return root.key;
	}
	public Value getRootValue(){
		return root.value;
	}
	
	private Node add (Node node,Key key, Value value){
		//возвращает измененный узел (после добавления значения)
		if (node == null){
			Node newnode = new Node(key,value);
			return newnode;
		}
		int compareResult = key.compareTo(node.key);
                if(compareResult == 0) {
                    node.value = value;
                    return node;
                }
                else if(compareResult < 0)
                    node.left = add(node.left, key, value);
                else 
                    node.right = add(node.right, key, value);
        return node;
	}
        
        public Key MinKey(){
           Node cur = root;
           // спускаемся к самому левому листу, по свойству дерева - наименьший ключ там
           for(; cur.left != null; cur = cur.left){}
           return cur.key;
        }
        public Key MaxKey(){
           Node cur = root;
           // спускаемся к самому правому листу, по свойству дерева - наибольший ключ там
           for(; cur.right != null; cur = cur.right){}
           return cur.key;
        }
       
        //вспомогательная функция, которая нигде не используется.
        private Node NodeMinKey(Node node){
           Node cur = node;
           for(; cur.left != null; cur = cur.left){}
           return cur;
        }
	
	public void add(Key key, Value value) {
		root = add(root, key, value);
	}
	
        //удаление вершины
	public void delete(Key key) {
            Node cur = root;
            Node prev = null;
            //спускаемся по дереву, пока не найдем вершину или не уткнемся в null
            for(; true; ){
                if(cur == null) return;
                if(key.compareTo(cur.key) < 0){
                    prev = cur; cur = cur.left;
                }
                else if(key.compareTo(cur.key) > 0){
                    prev = cur;
                    cur = cur.right;
                }
                else break;
            }
            /*
             * Итак, у нас есть элемент, который нужно удалить (cur) и его предок (prev)
             * Теперь нас ждет разбор частных случаев:
             *      1)Если правый сын удаляемого элемента не существует, мы можем просто выкинуть этот элемент из
             *        цепи prev -> cur -> left, оставив prev -> left.
             *      2)Если же правый сын существует, так просто выкинуть вершину мы не можем. 
             *        Чтобы сохранить свойство дерева мы найдем узел с наименьшим ключом в правом поддереве cur,
             *        присоединим к найденному узлу левого сына cur и заменим cur на этот узел.
             */
            if(cur.right == null)
                if(cur == prev.right)
                    prev.right = cur.left;
                else
                    prev.left = cur.left;
            else{
                Node mostLeft = cur.right;
                prev = null;
                for(; mostLeft.left != null;){
                    prev = mostLeft;
                    mostLeft = mostLeft.left;
                }
                if(prev != null)
                    prev.left = mostLeft.right;
                else
                    cur.right = mostLeft.right;
                cur.key = mostLeft.key;
                cur.value = mostLeft.value;
            }
                
	}
	
	public Value get(Key key) {
            Node cur = root;
            for(; true; ){
                if(cur == null) break;
                if(key.compareTo(cur.key) < 0)
                    cur = cur.left;
                else if(key.compareTo(cur.key) > 0)
                    cur = cur.right;
                else break;
            }
            return cur != null? cur.value : (Value)null;
	}
	
	private void print(Node node, int level) {
		if (node != null) {
			print(node.right, level+1);
			for (int i=0; i < level; i++) {
				System.out.print("\t");
			}
			System.out.println(node.key + " => " + node.value); 
			print(node.left, level + 1);
		}
	}
	
	public void print() {
		print(root, 0);
	}
	
 
 
public static void main (String[] args){
		Tree<Double, Double> a = new Tree<Double, Double>();
		int n = 100;
		for(int i = 0; i < n; i++){
			a.add( Math.round(Math.random() * 1000.0) + 1.0*i,  Math.round(Math.random() * 1000000.0) + 1.0*i);
		}
		System.out.println(a.MaxKey() + " => " + a.get(a.MaxKey()));
		System.out.println(a.MinKey() + " => " + a.get(a.MinKey()));
                System.out.println();
                System.out.println();
                System.out.println();
                System.out.println("First print");
		a.print();
		a.delete(a.getRootKey());
                System.out.println();
                System.out.println();
                System.out.println();
                System.out.println("Second print");
		a.print();
	}
}