deepecstasy 0 Newbie Poster

Here is my splay function:

template <class WA>
    void SplayTree<WA>::Do_Splay(SplayNODE<WA> *temp) //temp is the node which is to be splayed
    {
        if (temp==root) //if temp is root then
        {   return;     }   //Do Nothing

        else if (root->left==temp || root->right==temp) //else if temp is a child of root
        {
            if (root->left==temp)   //if temp is left child of root then
            {
                Zig(root);  //perform ZIG
            }
            else if (root->right==temp) //else if temp is right child of root then
            {
                Zag(root);  //perform ZAG
            }
        }
        else    //if temp is some node lower in tree then
        {
            SplayNODE<WA> *father = findfather(temp, root);
            SplayNODE<WA> *grandfather = findfather(father, root);
            //cout<<"\n\tf = "<<father->key<<"\tgf = "<<grandfather->key;
            ////--------------------------------------------------------------------//-------////
            if ( grandfather->left == father)   //if father itself is left child
            {
                if(father->left == temp)    //if temp is left child of father then
                {       //CASE = ZIG ZIG
                    cout<<"\tZig(father)---Zag(grandfather)";
                    Zig(grandfather);   
                    Zig(father);        
                }

                else if ( father->right == temp )   //if temp is right child of father then
                {       //CASE = ZIG ZAG
                    cout<<"\tZig(father)---Zag(grandfather)";
                    Zig(father);    
                    Zag(grandfather);
                }
            }
            //--------------------------------------------------------------------//-------////
            if (grandfather->right == father)   //if father itself is right child
            {
                if(father->right == temp) 
                {       //CASE = ZAG ZAG
                    cout<<"\tZag(grandfather)---Zag(father)";
                    Zag(grandfather);
                    Zag(father);
                }
                else if (father->left == temp)
                {       //CASE = ZAG ZIG
                    cout<<"\tZag(father)---Zig(grandfather)";
                    Zag(father);
                    Zig(grandfather);
                }
            }
            ////--------------------------------------------------------------------//-------////
        }
    }

Following are methods of Zig (Single Rotate Left) & Zag (Single Rotate Right).

template <class WA>
    void SplayTree<WA>::Zig(SplayNODE<WA> * & k2) //k2 is temp node where imbalance is present & we have to rotate it
    {
        SplayNODE<WA> *k1 = k2->left;    //create copy of temp's left & store it in k1
        k2->left = k1->right;   //make k1's right child as temp's left child
        k1->right = k2; //make k1 as parent of temp node    
        k2 = k1;    //assign k1 as new temp node (this is done because temp was passed by reference)
    }
    //==============================//==============================//
    template <class WA>
    void SplayTree<WA>::Zag(SplayNODE<WA> * & k2)
    {
        SplayNODE<WA> *k1 = k2->right;   //create copy of temp's right child & store it in k1
        k2->right = k1->left;   //store k1's left child as temp's right child
        k1->left = k2;  //make k2 as left child of k1
        k2 = k1;    //assign k1 as temp node (due to reference of k2)
    }
    //==============================//==============================//

& Here is my f** problem.
For start, Im splaying in search function only. i.e. splay if a node with specific key is found.

My Search Function:

template <class WA>
    SplayNODE<WA>* SplayTree<WA>::search(SplayNODE<WA> *temp, WA value)    /////PVT DEFINITION
    {
        SplayNODE<WA> *to_searched = 0;  //created new node pointer in which address of required node will be saved
        if (temp!=0)    //if arg. given temp node is not empty, then
        {
            if (temp->key==value)   //if temp node has user-specified value then
            {   
                to_searched = temp;     //assign address of temp to to_searched node, which will be return @ the end
                Do_Splay(temp); //perform splay at node which is found
            }   
            if (to_searched==0) //if node is still empt then
            {   to_searched = search(temp->left, value);    }   //recursive call to search in left sub-tree of temps
            if (to_searched==0) //if node is still empt then
            {   to_searched = search(temp->right, value);   }   //recursive call to search in right sub-tree of temps
        }
        return to_searched; //Finally return the searched node
    }
    //==============================//==============================//

Following work fine in case if a node is a child of root.
- Zig Single
- Zag Single
But as soon as we go a single node down, the problem starts. I can't execute any of these things successfully.
- Zig Zig
- Zig Zag
- Zag Zag
- Zag Zig

Here is the Sample tree.
(Zig Zig Case)

            20
           /  \
         10   25
        /  \
       5   15

When 5 is searched, answer should be.

     5
      \
      10
        \
        20
       /  \
      15  25

But my output becomes:

       20
      /  \
    15   25

Can't figure out whats the problem. Dry run-ed this thing 100 times but.
Any & all help is appreciated. Thanks in Advance

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.