I am trying to perform insertion in one function and then balance the tree if required in another.
Here is my code...
node* create_bst(node* tree,node* curr)
{
if (tree==NULL)
{
return curr;
}
if(tree!=curr)
{
if(tree->key>=curr->key)
{
tree->left=create_bst(tree->left,curr);
}
else
{
tree->right=create_bst(tree->right,curr);
}
}
tree->bal_f=height(tree->left)-height(tree->right);
}
create_bst(tree,curr) adds curr node (that contains key) to the tree- simple binary tree insertion followed by updating of balance factor of each node of the constructed tree. Then i call the balance function that balances the tree.
node* balance(node* tree,node* curr)
{
if(tree->bal_f==2 or tree->bal_f==-2)
{
if(tree->key>=curr->key)
{
balance(tree->left,curr);
node* a=tree;
node* b=new node;
b=a->left;
if(curr->key<b->key)
{
tree=LL_rotation(b,a);
}
if(curr->key>b->key)
{
node* c=new node;
c=b->right;
tree=LR_rotation(c,b,a);
}
}
else
{
balance(tree->right,curr);
node* a=tree;
node* b=new node;
b=a->right;
if(curr->key>b->key)
{
tree=RR_rotation(b,a);
}
if(curr->key<b->key)
{
node* c=new node;
c=b->left;
tree=RL_rotation(c,b,a);
}
}
}
curr is the same node that was added in the create_bst function.
LL_rotation= performs left rotation and returns the modified root node. LL means that curr node was added to the left side of the left child of the node with balance factor 2 or -2. rotations are performed accordingly. Same is the case with the rest. LR_rotation= perform left rotation followed by right rotation and returns the modified root node.
RR_rotation= performs right rotation and returns the modified root node.
RL_rotation= performs right rotation followed by left rotation and returns the modified root node.
The problem that i am facing is that with rotation that though the root node changes on rotation in my case its remaining the same. For example: if my input is -- (2,0,-1) on LL rotation it becomes 0,2,-1 (Preorder) but i am getting only 2 which was my initial root. Any help is highly appreciated. :)