/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;
import java.security.Key;

/**
 * Created by green on 26.11.15.
 */
class BST <Key extends Comparable<Key>, Value> {

    private class Node {
        Key key;
        Value value;
        Node left, right, father;
        public Node (Key key, Value value) {
            this.key = key;
            this.value = value;
            this.left = this.right = null;
            this.father = null;
        }
        public Node (Key key, Value value, Node father) {
            this.key = key;
            this.value = value;
            this.left = this.right = null;
            this.father = father;
        }
    }

    private Node root;

    private Node add (Node node,Key key, Value value, Node father){
        if (node == null){
            Node newnode = new Node(key,value, father);
            return newnode;
        }
        int compareResult = key.compareTo(node.key);
        if (compareResult > 0) node.right = add(node.right, key, value, node);
        else if(compareResult < 0) node.left = add(node.left, key, value, node);
        else{
            node.value = value;
        }
        return node;
    }

    public void add(Key key, Value value) {
        root = add(root, key, value, root);
    }

    private Node delete(Node node, Key key){
        if(node == null) return null;
        int compareResult = key.compareTo(node.key);
        if(compareResult > 0){
            node.right = delete(node.right, key);
        }else if(compareResult < 0){
            node.left = delete(node.left, key);
        }else{
            if(node.right == null && node.left == null){
                return node = null;
            }else if(node.right == null){
                return node = node.left;
            }else if(node.left == null){
                return node = node.right;
            }else{
                if(node.right.left == null){
                    node.right.left = node.left;
                    node.right.father = node.father;
                    return node = node.right;
                }else{
                    Node res = min(node.right);
                    node.key = res.key;
                    node.value = res.value;
                    delete(node.right, node.key);
                    return node;
                }
            }
        }
        return node;
    }

    public void delete(Key key) {
        root = delete(root, key);
    }

    public Value minKey(){
        return min(root).value;
    }

    public Value maxKey(){
        return max(root).value;
    }

    private Node min(Node node){
        if(node.left == null) return node;
        return min(node.left);
    }

    private Node max(Node node){
        if(node.right == null) return node;
        return min(node.right);
    }

    private Value get(Node node, Key key){
        if(node == null) return null;
        int compareResult = key.compareTo(node.key);
        if(compareResult == 0){
            return node.value;
        }else if(compareResult > 0){
            return get(node.right, key);
        }else{
            return get(node.left, key);
        }
    }

    public Value get(Key key) {
        return get(root, key);
    }

    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);
    }

}

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BST<Integer, String> tree = new BST<>();
        tree.add(10, "Test1");
        tree.add(12, "Test2");
        tree.add(1, "Test3");
        tree.add(5, "Test4");
        tree.add(6, "Test5");
        tree.add(3, "Test6");
        tree.print();
        tree.delete(5);
        tree.print();
        System.out.println(tree.get(1));
        System.out.println(tree.minKey());
        System.out.println(tree.maxKey());
        System.out.println(tree.get(3));
	}
}