Splay树轮换问题 [英] Splay Tree Rotations Problem
本文介绍了Splay树轮换问题的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
这是我的展开功能：
template < WA类>
void SplayTree< WA> :: Do_Splay（SplayNODE< WA> * temp） // temp是要展示的节点
{
if （temp = = root） // 如果temp是root，那么
{返回; } // 什么都不做
else if （root-> left == temp || root-> right == temp） // 否则如果temp是root的子级
{
if （root-> left == temp） // 如果temp是root的子项，那么
{
Zig（root）; // 执行ZIG
}
else if （root-> right == temp） // 如果temp是root的右子，则
{
Zag（root）; // 执行ZAG
}
}
else // 如果temp是树中的某个节点，那么
{
SplayNODE< WA> * father = findfather（temp，root）;
SplayNODE< WA> *祖父=寻父（父亲，根）;
// cout<<\ n\tf =<< father-> ; key<<\ tgf =<< grandfather-> key;
/// / ------------------------------------------- ------------------------- // ------- ////
if （grandfather-> left == father） // 如果父亲本身留给孩子
{
if （father-> left == temp） // 如果temp是父亲的孩子那么
{ // CASE = ZIG ZIG
cout<< \tZig（父亲）---字形（祖父）;
Zig（祖父）;
Zig（父亲）;
}
else if （father-> right = = temp） // 如果temp是父亲的孩子那么
{ // CASE = ZIG ZAG
cout<< \ tZig（父亲）--- Zag（祖父）;
Zig（父亲）;
Zag（祖父）;
}
}
// ---------- -------------------------------------------------- -------- // ------- ////
如果（祖父 - >右== father） // 如果父亲本身就是正确的孩子
{
< span class =code-keyword> if （father-> right == temp）
{ // CASE = ZAG ZAG
cout<< \ tZag（祖父）---字形（父亲）;
Zag（祖父）;
Zag（父亲）;
}
else if （father-> left == temp）
{ // CASE = ZAG ZIG
cout<< \ tZag（father）--- Zig（grandfather）;
Zag（父亲）;
Zig（祖父）;
}
}
/// / -------- -------------------------------------------------- ---------- // ------- ////
}
}
以下是Zig（单向左旋）和&的方法。 Zag（单向旋转右侧）。
模板 < class WA>
void SplayTree< WA> :: Zig（SplayNODE< WA> *& k2） // k2是存在不平衡的临时节点&我们必须旋转它
{
SplayNODE< WA> * k1 = k2-> left; // 创建临时左侧&的副本将其存储在k1
k2-> left = k1-> right; // 将k1的右孩作为临时左撇子
k1-> right = k2; // 使k1成为临时节点的父节点
k2 = k1; // 将k1指定为新的临时节点（这样做是因为temp是通过引用传递的）
}
// ================== ============ // // ==============================
模板< class WA>
void SplayTree< WA> :: Zag（SplayNODE< WA> *& k2）
{
SplayNODE< WA> * k1 = k2->右; // 创建临时正确子女的副本&将其存储在k1
k2-> right = k1-> left; // 将k1的左孩子存储为临时孩子
k1-> left = k2; // 将k2作为k1的左子项
k2 = k1; // 将k1指定为临时节点（由于参考k2）
}
// ======================= ======= // ============================== //
&这是我的问题。
首先，我只在搜索功能中使用。即如果找到具有特定*键*的节点，则显示。
我的搜索功能：
模板<类WA>
SplayNODE< WA> * SplayTree< WA> :: search（SplayNODE< WA> * temp，WA value ） /// // PVT DEFINITION
{
SplayNODE< WA> * to_searched = 0 ; // 创建新节点指针，其中将保存所需节点的地址
if （temp！= 0 ） // 如果是arg。给定的temp节点不为空，那么
{
如果（temp-> key == value ） // 如果临时节点具有用户指定的值，则
{
to_searched = temp; // 为to_searched节点分配临时地址，返回@结束
Do_Splay （温度）; // 在找到的节点处执行splay
}
if （to_searched == 0 ） // 如果节点仍为空，则
{to_searched = search（temp-> left， value ）; } // 递归调用临时左子树中的搜索
if （to_searched == 0 ） // 如果节点仍然没有，那么
{to_searched = search（temp-> right， value ）; } // 在临时子树中搜索递归调用
}
return to_searched; // 最后返回搜索到的节点
}
// ============================== // ============================== //
如果节点是root的子节点，以下工作正常。
- Zig Single
- Zag Single
但是，只要我们单个节点关闭，问题就会开始。我不能成功执行任何这些事情。
- Zig Zig
- Zig Zag
- Zag Zag
- Zag Zig
这是示例树。
（Zig Zig Case）
20
/ \
10 25
/ \
5 15
搜索5时，应该回答。
5
\
10
\
20
/ \
15 25
但我的输出变为：
20
/ \
15 25
无法弄清楚问题是什么。干这个东西100次但是。 :(
非常感谢所有帮助。感谢提前
解决方案
< blockquote>这个问题有一个问题。它看起来几乎就像一个问题，因为你实际上明确地提出了问题。
尽管如此，这不是一个问题我们期待在这个论坛上。相反，这是一个为你工作的请求，虽然不是我们在这里看到的最糟糕的。代码的调试只是编程工作的另一部分，类似于设计的详细说明，编写代码和在你的代码中，我看不到任何特别愚蠢的东西，我们可以帮助识别的任何明显的误解，没有你可能错过的专业秘密，我们可以与你分享，不会错过我们可以带来的好主意，没有秘密 API可以做到这一点。这是纯粹的算法......还有一些工作要做。
所以，你只需要重新审视一下问题，停止重复做什么你已经完成了，计划一些测试场景和广泛使用调试器。换句话说，更多的耐心，计划和更多的工作。
对不起，我不是为你做的。
感谢您的理解，
这是C中不错的实现： Splay树 [ ^ ]，您可以根据自己的实施情况进行检查，看看它们的区别。
祝你好运
Espen Harlinn
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
解决方案
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
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
这篇关于Splay树轮换问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
