13,505,090 members
See more:
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
}
}
//==============================//==============================//```

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
Posted 26-Dec-12 4:17am
Sergey Alexandrovich Kryukov 26-Dec-12 16:43pm

Well, did you execute it under the debugger?
—SA

## 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.

—SA
Mika Wendelius 28-Dec-12 10:57am

Sergey Alexandrovich Kryukov 28-Dec-12 12:33pm

Thank you, Mika.
—SA

## 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
v2
Mika Wendelius 28-Dec-12 10:57am

Espen Harlinn 29-Dec-12 7:22am

Thank you, Mika :-D
Sergey Alexandrovich Kryukov 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 30-Dec-12 5:33am

Thank you, Sergey :-D

Top Experts
Last 24hrsThis month
 Wendelius 285 OriginalGriff 228 Richard MacCutchan 90 ppolymorphe 40 Maciej Los 40
 OriginalGriff 4,181 Jochen Arndt 2,328 ppolymorphe 2,053 Wendelius 1,843 Maciej Los 1,694