Splay Tree Zig-Zag & amp; ЗАГ-ЗИГ ВРАЩЕНИЕ ВЫПУСК

Итак, вот алгоритм splay, если вы хотите проверить.

Вот моя функция отображения:

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);
}
}
////--------------------------------------------------------------------//-------////
}
}

Ниже приведены методы Zig (Single Rotate Left) & Zag (одиночный поворот вправо).

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)
}
//==============================//==============================//

& Вот моя чертова проблема.
Для начала Im Splaying только в функции поиска. то есть отображать, если узел с определенным ключ найден.

Моя функция поиска:

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
}
//==============================//==============================//

Следующее работает нормально в случае, если узел является дочерним от root.
— Zig Single
— Zag Single
Но как только мы переходим на один узел, проблема начинается. Я не могу выполнить ни одну из этих вещей успешно.
Зиг зиг
— зигзаг
— Заг Заг
— Заг Зиг

Вот образец дерева.
(Zig Zig Case)

        20
/  \
10   25
/  \
5   15

При поиске 5 ответ должен быть.

 5
\
10
\
20
/  \
15  25

Но мой вывод становится:

   20
/  \
15   25

Не могу понять, в чем проблема. Сухой прогонял эту вещь 100 раз, но. 🙁
любой & вся помощь приветствуется. Заранее спасибо