AVLTree(loading and balancing a binary tree)
<pre><code>// rotate the node that is unbalanced,its parent and grandparent
template &lt;class V&gt;
void AVLTree&lt;V&gt;::rotate(Node&lt;V&gt; *node)
{
 if (Root==NULL)
 {
    return;
 }
 if (Root-&gt;Left==NULL &amp;&amp; Root-&gt;Right==NULL)
 {
    return;   
 }
 Node&lt;V&gt; *parent,*grandparent;
 parent=node-&gt;Parent;
 grandparent=parent-&gt;Parent;
 if (grandparent==NULL)
    return;

 V min=node-&gt;key;
 Node&lt;V&gt; *A,*B,*C;
 A=node;

 if (parent-&gt;key&lt;min)
 {
     min=parent-&gt;key;
     A=parent;
 }        
 if (grandparent-&gt;key&lt;min)
 {
      min=grandparent-&gt;key;
      A=grandparent;
 }

 if (parent==A)
 {
     if (grandparent-&gt;key&lt;node-&gt;key)
     {
         B=grandparent;
         C=node;
     }
     else
     {
         B=node;
         C=grandparent;
     }
 }

 if (grandparent==A)
 {
     if (parent-&gt;key&lt;node-&gt;key)
     {
         B=parent;
         C=node;
     }
     else
     {
         B=node;
         C=parent;
     }
 }

 if (node==A)
 {
     if (grandparent-&gt;key&lt;parent-&gt;key)
     {
             B=grandparent;
             C=parent;
     }
     else
     {
             B=parent;
             C=grandparent;
     }
 }

 if (grandparent-&gt;Parent!=NULL)
 {
    B-&gt;Parent=grandparent-&gt;Parent;
    B-&gt;Left=A;
    B-&gt;Right=C;
    A-&gt;Parent=B;
    C-&gt;Parent=B;
 } 
 else
 {
    B-&gt;Left=A;
    B-&gt;Right=C;
    A-&gt;Parent=B;
    C-&gt;Parent=B;
 }       
}     
//balance the node if it is not balanced
template &lt;class V&gt;
void AVLTree&lt;V&gt;::balance(Node&lt;V&gt; *node)
{
  Node&lt;V&gt; *temp=node;

  while (temp!=Root || temp-&gt;Parent!=NULL || (temp-&gt;Parent)-&gt;Parent!=NULL)
  {
       temp=temp-&gt;Parent;
       temp=temp-&gt;Parent;     
       if (isBalanced(temp)==0)
       {
           Node&lt;V&gt; *temp1=tallGrandChild(temp);
           rotate(temp1);
       }      
   }
} 
//insert a new key and value
template &lt;class V&gt;
void AVLTree&lt;V&gt;::insert(V key,string value)
{
   Node&lt;V&gt; *temp,*temp1;
   if (Root==NULL)
   {
      Root=new Node&lt;V&gt;(key,value);
      return;
   }          
 temp=Root;

 if (Root!=NULL)
 {
    while (temp!=NULL)
    {
       balance(temp);   
       temp1=temp;
       if (key&gt;temp-&gt;key)
       {
            temp=temp-&gt;Right;
       }
       else if (key&lt;temp-&gt;key)
       {
            temp=temp-&gt;Left;
       }

    }

    if (temp1!=NULL)
    {
        temp=new Node&lt;V&gt;(key,value);
        temp-&gt;Parent=temp1;
        if (temp1-&gt;key&gt;key)
        {
            temp1-&gt;Left=temp;
        }
        else if (temp1-&gt;key&lt;key)
        {
            temp1-&gt;Right=temp;
        }
    }
 }               
}                                  

//reading data from a file and storing it in AVLTree using insert function
template &lt;class V&gt;               
void AVLTree&lt;V&gt;::loadTree(const char *file)
{
 ifstream fin;
 fin.open(file);

 if(fin.fail())
 cout&lt;&lt;"Error in opening file!"&lt;&lt;endl;

 while (!fin.eof())
 {
       string buffer;
       V buff;
       getline(fin,buffer,'~');
       fin&gt;&gt;buff;
       if (!buff)
          continue;
       insert(buff,buffer);

 }


 fin.close();
}
</code></pre>

<p>I am making an AVL Tree as an assignment.I am having problems when balancing a tree.I am thinking that i might have to balance the tree recursively otherwise every subtree will not be balanced.Thanks in advance for any help.</p>
