Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++
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
Posted 26-Dec-12 4:17am
Comments
Sergey Alexandrovich Kryukov at 26-Dec-12 16:43pm
   
Well, did you execute it under the debugger?
—SA
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

There is one problem with this question. It looks almost like a question, as you actually clearly formulated the problem.
 
Nevertheless, this is not really a question we expect on this forum. Rather, this is a request for making your job for you, albeit not the worst we see here. The debugging of the code is just another part of programming job, similar to elaboration of the design, writing code and the like. In your code, I cannot see anything specifically silly, any distinct misconception which we could help to identify, no "professional secret" you could miss and we could share with you, no missing bright idea we could bring in, no "secret API" which could do the trick. This is pure algorithm and… some more work to be done.
 
So, all you need is to take a fresh look at the problem, stop repeating of doing what you have already done, planning of some testing scenario and extensive use of the debugger. In other words, more patience, planning and more of your work.
 
Sorry that I'm not doing it for you.
 
Thank you for your understanding,
—SA
  Permalink  
Comments
Mika Wendelius at 28-Dec-12 10:57am
   
Good answer, 5
Sergey Alexandrovich Kryukov at 28-Dec-12 12:33pm
   
Thank you, Mika.
—SA
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

Here is a decent implementation in C: Splay tree[^], you can check this against your own implementation and see where they differ.
 
Best regards
Espen Harlinn
  Permalink  
v2
Comments
Mika Wendelius at 28-Dec-12 10:57am
   
Nice link!
Espen Harlinn at 29-Dec-12 7:22am
   
Thank you, Mika :-D
Sergey Alexandrovich Kryukov at 29-Dec-12 20:46pm
   
I think you meant "check this against...", was a typo; I modified it. My 5 for the answer.
—SA
Espen Harlinn at 30-Dec-12 5:33am
   
Thank you, Sergey :-D

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



Advertise | Privacy | Mobile
Web04 | 2.8.140709.1 | Last Updated 29 Dec 2012
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid