递归展开树
我正在尝试实现一个自下而上的递归展开树。我递归到需要展开的节点，并找到该节点的父节点和祖父节点。然后我就可以根据情况选择之字形或之字形。问题是完成此操作后，我将已展开一次的节点返回到先前的递归调用。先前的递归调用引用了该节点的父节点，该节点现在是该节点的子节点。如何在向上递归时展开节点？
I am trying to implement a recursive splay tree, bottom up. I recurse down to the node I am need to splay up, and I find the parent and grandparent of that node. Then I am able to either zig zag or zig zig depending on the situation just fine. The problem is after this is done, I return the node which has been splayed once to the previous recursive call. The previous recursive call is referenced to the parent of the node, which is now the child of that node. How do I recurse up splaying the node as I go up?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果我没记错的话，当您递归到目标节点时，您会构建一棵左树和右树。当找到目标时，使用目标的（原始）子节点构造最终的左树和右树，将生成的树附加为目标的新子节点，并以尾递归方式返回结果（即，所有方式备份堆栈而无需进一步修改）。
If I recall correctly, you build a left and right tree as you recurse down to the target node. When you find the target, you construct the final left and right trees using the (original) children of the target, attach the resulting trees as the new children of the target, and return the result in tail-recursive fashion (i.e., all the way back up the stack without further modification).
当树完全“不平衡”并且非常大（例如 100000 个 int 键）时，递归算法可能会抛出 stackoverflow 异常。最好在每个节点中使用父指针来获取父节点或祖父节点。这是一种方法。对我来说效果很好。
运行时的结果在这里很明显展开树运行时分析
When the tree gets totally "unbalanced" and really large (say as example 100000 int keys) then recursive algorithms may throw stackoverflow exception. Better to use a parent pointer in each node to get the parent or grand parent. This is one way of doing it. worked fine for me.
The results on the runtime are obvious heresplay tree runtime profiling