public class MyTreeMap {

	private Node root;
	private int size;
	private Node nullNode;

	public int getValue(double key) {
		return find(key);
	}

	public MyTreeMap() {
		nullNode = new Node();
        nullNode.left = nullNode;
     	nullNode.right = nullNode;
       	nullNode.parent = null;
        nullNode.color = 1;
        nullNode.key = 0.0;
        root = nullNode;
        size = 0;
    }

    public boolean isEmpty() {
    	return size == 0;
    }

    public int size() {
    	return size;
    }

	public int find(double key) {
		Node start = root;

		while (start != nullNode) {
			if (start.key > key)
				start = start.left;
			else if (start.key < key)
				start = start.right;
			else
				return start.value;
		}
		return 0;
	}

	public void insert(double key, int value) {
		Node start = root;
		Node p = null;

		++size;
		while (start != nullNode) {
			p = start;
			if (start.key > key)
				start = start.left;
			else if (start.key < key)
				start = start.right;
			else {
				start.value = value;
				return;
			}
		}

		start = new Node();
		start.key = key;
		start.value = value;
		start.parent = p;
		start.left = nullNode;
		start.right = nullNode;
		start.color = 0;

		if (p != null)
			if (p.key > key)
				p.left = start;
			else
				p.right = start;
		else
			root = start;

		while (start != root && start.parent.color == 0) {
			if (start.parent.parent.left == start.parent) {
				if (start.parent.parent.right.color == 0) {
					start.parent.color = 1;
					start.parent.parent.right.color = 1;
					start.parent.parent.color = 0;
					start = start.parent.parent;
				}
				else {
					if (start.parent.left != start) {
						start = start.parent;
						rotateLeft(start);
					}

					start.parent.color = 1;
					start.parent.parent.color = 0;
					rotateRight(start.parent.parent);
				}
			}
			else {
				if (start.parent.parent.left.color == 0) {
					start.parent.color = 1;
					start.parent.parent.left.color = 1;
					start.parent.parent.color = 0;
					start = start.parent.parent;
				}
				else {
					if (start.parent.right != start) {
						start = start.parent;
						rotateRight(start);
					}

					start.parent.color = 1;
					start.parent.parent.color = 0;
					rotateLeft(start.parent.parent);
				}
			}
		}
		root.color = 1;
	}

	private void rotateLeft(Node v) {
		Node temp = v.right;
		v.right = temp.left;
		if (temp.left != nullNode)
			temp.left.parent = v;
		if (temp != nullNode)
			temp.parent = v.parent;
		if (v.parent != null)
			if (v.parent.left == v)
				v.parent.left = temp;
			else
				v.parent.right = temp;
		else
			root = temp;
		temp.left = v;
		if (v != nullNode)
			v.parent = temp;
	}

	private void rotateRight(Node v) {
		Node temp = v.left;
		v.left = temp.right;
		if (temp.right != nullNode)
			temp.right.parent = v;
		if (temp != nullNode)
			temp.parent = v.parent;
		if (v.parent != null)
			if (v.parent.left == v)
				v.parent.left = temp;
			else
				v.parent.right = temp;
		else
			root = temp;
		temp.right = v;
		v.parent = temp;
	}

}