title: AVL tree rotation in Java
body: <p>I want to implement the Java AVL tree and to rotate the tree left and right. I am not getting this.</p>
  
  <p>Can anybody by looking at the code below tell me how can I possibly rotate the tree left and right and then use fix up with those two functions to balance the AVL tree?</p>
  
  <p>I hope someone here can guide me through this.</p>
  
  <pre><code>import java.util.Random;
  import java.util.SortedSet;
  import java.util.TreeSet;
  
  public class AVLTree&lt;T&gt; extends 
  BinarySearchTree&lt;AVLTree.Node&lt;T&gt;, T&gt; implements SSet&lt;T&gt; {
  
      Random rand;
  
      public static class Node&lt;T&gt; extends BSTNode&lt;Node&lt;T&gt;,T&gt; {
          int h;  // the height of the node
      }
  
      public AVLTree() {
          sampleNode = new Node&lt;T&gt;();
          rand = new Random();
          c = new DefaultComparator&lt;T&gt;();
      }
  
      public int height(Node&lt;T&gt; u) {
          return (u == null) ? 0 : u.h;
      }
  
      public boolean add(T x) {
          Node&lt;T&gt; u = new Node&lt;T&gt;();
          u.x = x;
          if (super.add(u)) {
              for (Node&lt;T&gt; w = u; w != nil; w = w.parent) {
                  // walk back up to the root adjusting heights
                  w.h = Math.max(height(w.left), height(w.right)) + 1;
              }
          fixup(u);
          return true;
      }
      return false;
  }
  
  public void splice(Node&lt;T&gt; u) {
      Node&lt;T&gt; w = u.parent;
      super.splice(u);
      for (Node&lt;T&gt; z = u; z != nil; z = z.parent)
          z.h = Math.max(height(z.left), height(z.right)) + 1;            
      fixup(w);
  }
  
  public void checkHeights(Node&lt;T&gt; u) {
      if (u == nil) return;
      checkHeights(u.left);
      checkHeights(u.right);
      if (height(u) != 1 + Math.max(height(u.left), height(u.right))) 
          throw new RuntimeException("Check heights shows incorrect heights");
      int dif = height(u.left) - height(u.right);
      if (dif &lt; -1 || dif &gt; 1)
          throw new RuntimeException("Check heights found height difference of " + dif);
  }
  
  /**
   * TODO: finish writing this method
   * @param u
   */
  public void fixup(Node&lt;T&gt; u) {
      while (u != nil) {
          int dif = height(u.left) - height(u.right);
          if (dif &gt; 1) {
              // TODO: add code here to fix AVL condition 
              // on the path from u to the root, if  necessary
          } else if (dif &lt; -1) {
              // TODO: add code here to fix AVL condition
              // on the path from u to the root, if necessary                 
          }
          u = u.parent;
      }
  }
  
  public Node rotateLeft() {
      return rotateLeft(u.parent);
  }
  
  public void rotateLeft(Node&lt;T&gt; u) {
      // TODO: Recompute height values at u and u.parent
  }
  
  public void rotateRight(Node&lt;T&gt; u) {
      // TODO: Recompute height values at u and u.parent
  }
  
  public static &lt;T&gt; T find(SortedSet&lt;T&gt; ss, T x) {
      SortedSet&lt;T&gt; ts = ss.tailSet(x);
      if (!ts.isEmpty()) {
          return ts.first(); 
      }
      return null;
  }
  
  /**
   * This just does some very basic correctness testing
   * @param args
   */
  public static void main(String[] args) {
      AVLTree&lt;Integer&gt; t = new AVLTree&lt;Integer&gt;();
      Random r = new Random(0);
      System.out.print("Running AVL tests...");
      int n = 1000;
      for (int i = 0; i &lt; n; i++) {
          t.add(r.nextInt(2*n));
          t.checkHeights(t.r);
      }
      for (int i = 0; i &lt; n; i++) {
          t.remove(r.nextInt(2*n));
          t.checkHeights(t.r);
      }
      System.out.println("done");
  
      t.clear();
      System.out.print("Running correctness tests...");
      n = 100000;
      SortedSet&lt;Integer&gt; ss = new TreeSet&lt;Integer&gt;();
      Random rand = new Random();
      for (int i = 0; i &lt; n; i++) {
          Integer x = rand.nextInt(2*n);
          boolean b1 = t.add(x);
          boolean b2 = ss.add(x);
          if (b1 != b2) {
              throw new RuntimeException("Adding " + x + " gives " + b2 
                      + " in SortedSet and " + b1 + " in AVL Tree");
          }
      }
      for (int i = 0; i &lt; n; i++) {
          Integer x = rand.nextInt(2*n);
          Integer x1 = t.find(x);
          Integer x2 = find(ss, x);
          if (x1 != x2) {
              throw new RuntimeException("Searching " + x + " gives " + x2 
                      + " in SortedSet and " + x1 + " in AVL Tree");
          }
          ss.headSet(x);
      }
      for (int i = 0; i &lt; n; i++) {
          Integer x = rand.nextInt(2*n);
          boolean b1 = t.remove(x);
          boolean b2 = ss.remove(x);
          if (b1 != b2) {
              throw new RuntimeException("Error (2): Removing " + x + " gives " + b2 
                      + " in SortedSet and " + b1 + " in AVL Tree");
          }
      }
      for (int i = 0; i &lt; n; i++) {
          Integer x = rand.nextInt(2*n);
          Integer x1 = t.find(x);
          Integer x2 = find(ss, x);
          if (x1 != x2) {
              throw new RuntimeException("Error (3): Searching " + x + " gives " + x2 
                      + " in SortedSet and " + x1 + " in AVL Tree");
          }
          ss.headSet(x);
      }
      System.out.println("done");
   }
  }
  </code></pre>