class AVLNode
    {

        public int value { get; private set; }

        public AVLNode lChild { get; private set; }
        public AVLNode rChild { get; private set; }

        public int _height { get; private set; }

        public AVLNode(int value)
        {
            this.lChild = null;
            this.rChild = null;
            this.value = value;
        }

        public static AVLNode insert(AVLNode node, int value)
        {
            if (node == null)
                node = new AVLNode(value);

            else if (node.value > value)
            {
                node.lChild = insert(node.lChild, value);
                node = balance(node);
            }

            else
            {
                node.rChild = insert(node.rChild, value);
                node = balance (node);
            }

            return node;
        }


        // Balance AVL Tree
        public static AVLNode balance(AVLNode temp)
        {
            int bal_factor = difference(temp);

            if (bal_factor > 1)
            {
                if (difference(temp.lChild) > 0)
                    temp = ll_rotation(temp);

                else
                    temp = lr_rotation(temp);
            }

            else if (bal_factor < -1)
            {
                if (difference(temp.rChild) > 0)
                    temp = rl_rotation(temp);

                else
                    temp = rr_rotation(temp);
            }

            return temp;
        }

        private static int height(AVLNode node)
        {
            int h = 0;
            if (node != null)
            {
                int l_height = height(node.lChild);
                int r_height = height(node.rChild);

                int max_height = l_height > r_height ? l_height : r_height;
                h = max_height + 1;
            }

            return h;
        }

        private static int difference(AVLNode node)
        {
            int l_height = height(node.lChild);
            int r_height = height(node.rChild);

            int b_factor = l_height - r_height;

            return b_factor;
        }

        // Right - Right Rotation
        private static  AVLNode rr_rotation(AVLNode parent)
        {
            AVLNode temp;
            temp = parent.rChild;
            parent.rChild = temp.lChild;
            temp.lChild = parent;

            return temp;
        }

        //Left - Left Rotation
        private static AVLNode ll_rotation(AVLNode parent)
        {
            AVLNode temp;
            temp = parent.lChild;
            parent.lChild = temp.rChild;
            temp.rChild = parent;

            return temp;
        }

        // Left - Right Rotation
        private static AVLNode lr_rotation(AVLNode parent)
        {
            AVLNode temp;
            temp = parent.lChild;
            parent.lChild = rr_rotation(temp);

            return ll_rotation(parent);
        }

        // Right- Left Rotation
        private static AVLNode rl_rotation(AVLNode parent)
        {
            AVLNode temp;
            temp = parent.rChild;
            parent.rChild = ll_rotation(temp);

            return rr_rotation(parent);
        }

        public static int setRightSubtree(AVLNode root, int offset, int depth)
        {
            if (root == null) { return 0; }

            int width = 3;
            int left  = setRightSubtree(root.lChild, offset,                depth + 1);
            int right = setRightSubtree(root.rChild, offset + left + width, depth + 1);

            root.Location = new Point(373 + (offset + left) * 9, 40 * depth + 12);

            return left + right + width;
        }

        public static int setLeftSubtree(AVLNode root, int offset, int depth)
        {
            if (root == null) { return 0; }

            int width = 3;
            int right = setLeftSubtree(root.rChild, offset,                 depth + 1);
            int left  = setLeftSubtree(root.lChild, offset + right + width, depth + 1);

            root.Location = new Point(319 - (offset + right) * 9, 40 * depth + 12);

            return left + right + width;
        }

        public static AVLNode deleteNode(AVLNode node, int key)
        {
            if (node == null)
                return node;

            if ( key < node.value )
                node.lChild = deleteNode(node.lChild, key);

            else if( key > node.value )
                node.rChild = deleteNode(node.rChild, key);

            else
            {
                if( (node.lChild == null) || (node.rChild == null) )
                {
                    AVLNode temp = node.lChild != null ? node.lChild : node.rChild;

                    if (temp == null)
                    {
                        temp = node;
                        node = null;
                    }
                    else
                     node = temp;
                }
                else
                {
                    AVLNode temp = minValueNode(node.rChild);
                    node.value = temp.value;
                    node.rChild = deleteNode(node.rChild, temp.value);
                }
            }

            if (node == null)
                return node;

            node = balance(node);

            return node;
        }

        public static AVLNode minValueNode(AVLNode node)
        {
            AVLNode current = node;

            while (current.lChild != null)
                current = current.lChild;

            return current;
        }

        public static int getBalance(AVLNode N)
        {
            if (N == null)
                return 0;

            return N.lChild._height - N.rChild._height;
        }
    }