Click here to Skip to main content
15,867,330 members
Please Sign up or sign in to vote.
4.00/5 (1 vote)
See more:
I am trying to perform insertion in one function and then balance the tree if required in another.

Here is my code...
C++
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.
C++
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. :)
Posted
Updated 12-Mar-19 4:55am

1 solution

I think the problem is that you are missing the final statement in the balance function:

C++
    ...
    return tree;
}


The statements that assign to tree have no effect that are visible from the caller:
(The comments are referring to your example of inserting (2,0,-1) and balance() is called after inserting the final -1 node.)
C++
            // This changes the variable tree visible INSIDE the function, 
            // the callers pointer to tree remains unchanged to the 2 node as you
            // mentioned.
            tree=RL_rotation(c,b,a);  
        }   
    }
    // This now returns the pointer to the 0 node that has become the new root of the
    // balanced  tree.
    return tree;
}
 
Share this answer
 
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900