Click here to Skip to main content
11,503,750 members (72,545 online)

deepecstasy40 asked:

Open original thread
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. Frown | :(
Any & all help is appreciated. Thanks in Advance
Tags: C++

Preview



When answering a question please:
  1. Read the question carefully.
  2. Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
  3. If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Let's work to help developers, not make them feel stupid.
Please note that all posts will be submitted under the The Code Project Open License (CPOL).



Advertise | Privacy | Mobile
Web03 | 2.8.150520.1 | Last Updated 26 Mar 2009
Copyright © CodeProject, 1999-2015
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100