using System;

namespace ALGA {
	public class Node {
		public int number;

		public Node left, right;

		public Node(int number) {
			this.number = number;
		}

		public Node insert(int value) {
			if (number == value) return this;

			if (value > number) {
				if (right != null)
					right = right.insert(value);
				else
					right = new Node(value);
			} else {
				if (left != null)
					left = left.insert(value);
				else
					left = new Node(value);
			}

			int balance = depth(left) - depth(right);

			if (Math.Abs(balance) <= 1) return this;

			if (balance > 0) {
				if (value > left.number)
					left = left.rotateLeft();
				return rotateRight();
			} else {
				if (value < right.number)
					right = right.rotateRight();
				return rotateLeft();
			}
		}

		public Node rotateLeft() {
			if (right == null) return null;
			Node pivot = right;
			(right, right.left) = (right.left, this);
			return pivot;
		}

		public Node rotateRight() {
			if (left == null) return null;
			Node pivot = left;
			(left, left.right) = (left.right, this);
			return pivot;
		}

		public bool isBalanced() {
			if (Math.Abs(depth(left) - depth(right)) > 1) return false;
			if (left != null && !left.isBalanced()) return false;
			if (right != null && !right.isBalanced()) return false;
			return true;
		}

		private int depth(Node here) {
			if (here == null) return 0;
			return 1 + Math.Max(depth(here.left), depth(here.right));
		}
	}
}