title: AVL tree not balancing correctly
body: <p>I have an assignment to write a self balancing binary search tree. I decided to use an AVL tree as it is what we have discussed in class. Then with the given input of { 3, 5, 61, 9, 32, 7, 1, 45, 26, 6} I'm expecting an output of:</p>
  
  <pre><code>               7
           6-----|-----32
      3----|      9----|----45
  1---|           |---26    |---61
  </code></pre>
  
  <p>That is, unless I have grossly misunderstood and thus miscalculated what an AVL tree is supposed to do when it balances itself. The output I'm getting is quite different:</p>
  
  <pre><code>              5
          3-----|-----61
     1----|      9----|
             7---|---32
          6--|    26--|--45
  </code></pre>
  
  <p>Again, unless I am completely wrong, that tree is not balanced. The function I'm using to set up the tree is defined as such:</p>
  
  <pre><code>node* insertKeyAVL(node* n, int e)
  {
      int cmpVal;
  
      if (n == NULL){
              n = create_node();
              n-&gt;data = e;
      } else if (e &lt; n-&gt;data) {
              if (n-&gt;left == NULL){
                      n-&gt;left = create_node();
                      n-&gt;left-&gt;data = e;
                      n-&gt;left-&gt;parent = n;
              } else {
                      n-&gt;left = insertKeyAVL(n-&gt;left, e);
              }
  
              cmpVal = height(n-&gt;left) - height(n-&gt;right);
  
  
      } else {
              if (n-&gt;right == NULL){
                      n-&gt;right = create_node();
                      n-&gt;right-&gt;data = e;
                      n-&gt;right-&gt;parent = n;
              } else {
                      n-&gt;right = insertKeyAVL(n-&gt;right, e);
              }
  
              cmpVal = height(n-&gt;right) - height(n-&gt;left);
      }
  
      if (cmpVal &gt; 2){
              if (n-&gt;left){
                      if (e &lt; n-&gt;left-&gt;data)
                              n = rotate_left(n);
                      else
                              n = rotate_right_left(n);
              } else if (n-&gt;right){
                      if (e &gt; n-&gt;right-&gt;data)
                              n = rotate_right(n);
                      else
                              n = rotate_left_right(n);
              }
      }
  
      n-&gt;height = max(height(n-&gt;left), height(n-&gt;right)) + 1;
  
      return n;
  }
  </code></pre>
  
  <p>The structure I'm using to store all the data is defined as such:</p>
  
  <pre><code>typedef struct node
  {
  
      struct node *parent;
      struct node*  left;
      struct node*  right;
  
      int data;
  
      int height;
  } node;
  </code></pre>
  
  <p>The functions rotate_left_right and rotate_right_left are basic functions that rotate the direction of the first post-fix then the second post-fix, and are both reliant on rotate_left and rotate_right for their respective direction. rotate left is defined as such:</p>
  
  <pre><code>node* rotate_left(node* n)
  {
      node* tmp = n-&gt;left;
      n-&gt;left = tmp-&gt;right;
      tmp-&gt;right = n;
  
      tmp-&gt;parent = n-&gt;parent;
      n-&gt;parent = tmp;
  
      n-&gt;height = max(height(n-&gt;left), height(n-&gt;right)) + 1;
      tmp-&gt;height = max(height(tmp-&gt;left), n-&gt;height) + 1;
  
      return tmp;
  }
  </code></pre>
  
  <p>rotate_right is similar but adjusted for a rotation right.</p>
  
  <p>I'm wondering where this code messes up so that it doesn't produce the desired output.</p>