12,554,442 members (80,105 online)
Rate this:
Please Sign up or sign in to vote.
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
}
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
Posted 26-Dec-12 4:17am
Comments
Sergey Alexandrovich Kryukov 26-Dec-12 16:43pm

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

## 2 solutions

Rate this:
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
Comments
Mika Wendelius 28-Dec-12 10:57am

Good answer, 5
Sergey Alexandrovich Kryukov 28-Dec-12 12:33pm

Thank you, Mika.
—SA
Rate this:
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
v2
Comments
Mika Wendelius 28-Dec-12 10:57am

Nice link!
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

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

Top Experts
Last 24hrsThis month
 OriginalGriff 267 Jochen Arndt 115 manu_dhobale 115 John Simmons / outlaw programmer 103 Suvendu Shekhar Giri 85
 OriginalGriff 4,229 Suvendu Shekhar Giri 1,918 John Simmons / outlaw programmer 1,790 ppolymorphe 1,625 Karthik Bangalore 1,210

Advertise | Privacy | Mobile
Web01 | 2.8.161021.1 | Last Updated 29 Dec 2012
Copyright © CodeProject, 1999-2016
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