11,503,750 members (72,545 online)

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
Tags: C++

## Preview

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