// AVLTree.java

public class AVLTree 
{
   public static final int NO_ERROR = 0, DUPLICATE_ELEMENT = 1,
                           ELEMENT_NOT_FOUND = 2;
   public Node root, current;
   private int errorCode;

   public AVLTree()
   {
      root = current = null;
      errorCode = NO_ERROR;
   }

   private void updateLevels(Node p, int level)
   {
      if (p != null)
      {
         updateLevels(p.left, level + 1);
         p.level = level;
         updateLevels(p.right, level + 1);
      }
   }

   private void LLrotation(Node p)
   {
      Node cur = p, old1 = cur.left, old2 = old1.left;
      cur.left = old1.right;
      if (cur.left != null)
         cur.left.parent = cur;
      old1.right = cur;
      old1.left = old2;
      old1.parent = cur.parent;
      cur.parent = old1;
      if (old1.parent != null)
         if (old1.compareTo(old1.parent.state) < 0)
            old1.parent.left = old1;
         else
            old1.parent.right = old1;
      if (old1.parent == null)
      {
         updateLevels(old1, 0);
         root = old1;
      }
      else
         updateLevels(old1.parent, old1.parent.level);
      current = cur;
   }

   private void RRrotation(Node p)
   {
      Node cur = p, old1 = cur.right, old2 = old1.right;
      cur.right = old1.left;
      if (cur.right != null)
         cur.right.parent = cur;
      old1.left = cur;
      old1.right = old2;
      old1.parent = cur.parent;
      cur.parent = old1;
      if (old1.parent != null)
         if (old1.compareTo(old1.parent.state) > 0)
            old1.parent.right = old1;
         else
            old1.parent.left = old1;
      if (old1.parent == null)
      {
         updateLevels(old1, 0);
         root = old1;
      }
      else
         updateLevels(old1.parent, old1.parent.level);
      current = cur;
   }

   private void LRrotation(Node p)
   {
      Node cur = p, old1 = cur.left, old2 = old1.right;
      cur.left = old2.right;
      if (cur.left != null)
         cur.left.parent = cur;
      old1.right = old2.left;
      if (old1.right != null)
         old1.right.parent = old1;
      old2.parent = cur.parent;
      cur.parent = old2;
      old1.parent = old2;
      old2.left = old1;
      old2.right = cur;
      if (old2.parent != null)
         if (old2.compareTo(old2.parent.state) < 0)
            old2.parent.left = old2;
         else
            old2.parent.right = old2;
      if (old2.parent == null)
      {
         updateLevels(old2, 0);
         root = old2;
      }
      else
         updateLevels(old2.parent, old2.parent.level);
      current = cur;
   }

   private void RLrotation(Node p)
   {
      Node cur = p, old1 = cur.right, old2 = old1.left;
      cur.right = old2.left;
      if (cur.right != null)
         cur.right.parent = cur;
      old1.left = old2.right;
      if (old1.left != null)
         old1.left.parent = old1;
      old2.parent = cur.parent;
      cur.parent = old2;
      old1.parent = old2;
      old2.left = cur;
      old2.right = old1;
      if (old2.parent != null)
         if (old2.compareTo(old2.parent.state) > 0)
            old2.parent.right = old2;
         else
            old2.parent.left = old2;
      if (old2.parent == null)
      {
         updateLevels(old2, 0);
         root = old2;
      }
      else
         updateLevels(old2.parent, old2.parent.level);
      current = cur;
   }

   private Node findParent(int[] key)
   {
      Node p = root, prev = null;
      while ((p != null) && (p.compareTo(key) != 0))
      {
         prev = p;
         if (p.compareTo(key) < 0)
            p = p.right;
         else
            p = p.left;
      }
      return prev;
   }

   private int max(int x, int y)
   {
      if (x > y)
         return x;
      else
         return y;
   }

   private int findHeight(Node p)
   {
      if (p == null)
         return 0;
      else
      {
         int leftHeight = 1 + findHeight(p.left),
             rightHeight = 1 + findHeight(p.right);
         return max(leftHeight, rightHeight);
      }
   }

   public Node findNode(int[] key)
   {
      Node p = root;
      while ((p != null) && (p.compareTo(key) != 0))
         if (p.compareTo(key) < 0)
            p = p.right;
         else
            p = p.left;
      return p;
   }

   private Node findRightMost(Node p)
   {
      while (p.right != null)
         p = p.right;
      return p;
   }

   public void insert(Node toInsert)
   {
      toInsert.left = toInsert.right = toInsert.parent = null;
      if (root == null)
      {
         root = current = toInsert;
         errorCode = NO_ERROR;
      }
      else
      {
         Node p = findNode(toInsert.state);
         if (p == null)
         {
            Node parent = findParent(toInsert.state), par = null;
            if (parent.compareTo(toInsert.state) > 0)
               parent.left = current = toInsert;
            else
               parent.right = current = toInsert;
            current.parent = parent;
            current.level = parent.level + 1;
            boolean done = false;
            int leftHeight = 0, rightHeight = 0;
            char dir1 = ' ', dir2 = ' ';
            while ((current != root) && (!done))
            {
               par = current.parent;
               dir2 = dir1;
               if (par.left == current)
                  dir1 = 'L';
               else
                  dir1 = 'R';
               leftHeight = findHeight(par.left);
               rightHeight = findHeight(par.right);
               if ((leftHeight == rightHeight) ||
                   (Math.abs(leftHeight - rightHeight) > 1))
                  done = true;
               else
                  current = par;
            }
            if ((dir1 != ' ') && (dir2 != ' ') &&
                (dir1 != dir2) && (Math.abs(leftHeight - rightHeight) > 1))
               if (dir1 == 'L')
                  LRrotation(par);
               else
                  RLrotation(par);
            else if (Math.abs(leftHeight - rightHeight) > 1)
               if (par.left == current)
                  LLrotation(par);
               else
                  RRrotation(par);
            errorCode = NO_ERROR;
         }
         else
            errorCode = DUPLICATE_ELEMENT;
      }
   }

   public void remove(int[] key)
   {
      Node p = findNode(key);
      if (p != null)
      {
         Node parent = p.parent;
         if ((p.left == null) && (p.right == null))
            if (parent != null)
               if (parent.left == p)
                  parent.left = null;
               else
                  parent.right = null;
            else
               root = null;
         else if ((p.left == null) && (p.right != null))
            if (parent != null)
            {
               if (parent.left == p)
                  parent.left = p.right;
               else
                  parent.right = p.right;
               p.right.parent = parent;
            }
            else
            {
               root = p.right;
               root.parent = null;
            }
         else if ((p.left != null) && (p.right == null))
            if (parent != null)
            {
               if (parent.left == p)
                  parent.left = p.left;
               else
                  parent.right = p.right;
               p.left.parent = parent;
            }
            else
            {
               root = p.left;
               root.parent = null;
            }
         else if ((p.left != null) && (p.right != null))
         {
            Node righty = findRightMost(p.left),
                 rightyParent = righty.parent,
                 temp = righty.copyOfNode();
            temp.left = p.left;
            temp.right = p.right;
            temp.parent = p.parent;
            if (rightyParent != p)
               rightyParent.right = righty.left;
            else
               p.left = righty.left;
            if (righty.left != null)
               righty.left.parent = rightyParent;
            p = righty;
         }
         p = null;
         current = parent;
         boolean done = false;
         int leftHeight, rightHeight;
         while ((current != null) && (!done))
         {
            char dir1, dir2;
            leftHeight = findHeight(current.left);
            rightHeight = findHeight(current.right);
            if ((leftHeight == rightHeight) && (leftHeight != 0))
               done = true;
            else if (Math.abs(leftHeight - rightHeight) > 1)
            {
               Node temp;
               if (leftHeight > rightHeight)
               {
                  dir1 = 'L';
                  temp = current.left;
               }
               else
               {
                  dir1 = 'R';
                  temp = current.right;
               }
               leftHeight = findHeight(temp.left);
               rightHeight = findHeight(temp.right);
               if (leftHeight > rightHeight)
                  dir2 = 'L';
               else if (leftHeight < rightHeight)
                  dir2 = 'R';
               else
                  dir2 = dir1;
               if (dir1 == 'L')
                  if (dir2 == 'L')
                     LLrotation(current);
                  else
                     LRrotation(current);
               else if (dir1 == 'R')
                  if (dir2 == 'L')
                     RLrotation(current);
                  else
                     RRrotation(current);
            }
            else
            {
               parent = current.parent;
               current = parent;
            }
         }
         if (parent == null)
            updateLevels(root, 0);
         else
            updateLevels(parent, parent.level);
         errorCode = NO_ERROR;
      }
      else
         errorCode = ELEMENT_NOT_FOUND;
   }

   public Node alreadyIncludes(Node p)
   {
      return findNode(p.state);
   }

   public int getErrorCode()
   {
      return errorCode;
   }

}