title: C++ AVL Tree Implementation
body: <p>I'm trying to implement AVL. Here's my insert, balance_tree, check_bf (balance factor), and single left rotate functions in order:</p>
  
  <pre><code>BinaryNode *BinarySearchTree::insert(int x,BinaryNode *t, int dpt) throw(DuplicateItem)
  {
      if (t == NULL) t = new BinaryNode(x,NULL,NULL,dpt+1);
      else if (x &lt; t-&gt;element) t-&gt;left = insert(x, t-&gt;left, dpt+1);
      else if (x &gt; t-&gt;element) t-&gt;right = insert(x, t-&gt;right, dpt+1);
      else
          throw DuplicateItem();
      balance_tree(t);
      return t;
  }
  BinaryNode* BinarySearchTree::balance_tree(BinaryNode *t)
  {
      double debug = check_BF(t);
      while(check_BF(t)&gt;1 || check_BF(t)&lt;-1)
      {
          if(check_BF(t)&gt;1)
          {
              if(check_BF(t-&gt;right)&lt;-1) return doubleLeft(t);
              else return singleLeft(t);
          }
          else if(check_BF(t)&lt;-1)
          {
              if(check_BF(t-&gt;left)&gt;1) return doubleRight(t);
              else return singleRight(t);
          }
      }
  }
  double BinarySearchTree::check_BF(BinaryNode *t)
  {
      double l, r;
      if(t-&gt;left!=NULL) l = t-&gt;height(t-&gt;left)+1;
      else l=0;
  
      if(t-&gt;right!=NULL) r = t-&gt;height(t-&gt;right)+1;
      else r=0;
  
      return r-l;
  }
  BinaryNode* BinarySearchTree::singleLeft(BinaryNode *t)
  {
      BinaryNode* Y = t;
      if(Y!=NULL)
      {
          t = t-&gt;right;
          Y-&gt;right = t-&gt;left;
          t-&gt;left=Y;
      }
      return t;
  }
  </code></pre>
  
  <p>I tried it out with a small tree that requires a single left rotation:</p>
  
  <pre><code>1 &lt;----t
   \
    2
     \
      3
  </code></pre>
  
  <p>At the end of the single left rotation function, t points to 2 with 1 as the left node and 3 as the right node, so the function works. The tree looks like this:</p>
  
  <pre><code>  2&lt;----t
   / \
  1   3
  </code></pre>
  
  <p>However, when it exits the function, t points to 1 with no left or right node. I don't understand what happens between that return t and the right bracket } that ends the function that changes t. Can anyone help?</p>