递归Splay树

Question

递归Splay树

algorithmdata-structuresrecursionsplay-tree

3

我正在尝试实现一颗自底向上的递归splay树。我会递归到我需要旋转节点的位置，找到该节点的父节点和祖父节点。然后，根据情况，我可以轻松进行zig zag或者zig zig操作。问题在于，在完成这些操作之后，我将已经旋转过一次的节点返回给了前一个递归调用。前一个递归调用引用的是该节点的父节点，而该节点现在是其子节点。如何在沿着递归路径向上移动时进行旋转呢？

- Andrew

递归伸展树和普通伸展树有什么区别？ - Svante

递归意味着节点从底部向上展开。正常的意思是从顶部向下展开一个节点。 - Andrew

2个回答

0

当树变得完全“不平衡”且非常庞大（例如100000个整数键）时，递归算法可能会引发堆栈溢出异常。最好在每个节点中使用一个父指针来获取父节点或祖父节点。这是一种解决方法，对我来说效果很好。

运行时的结果在这里是显而易见的伸展树运行时分析。

- Harisankar Krishna Swamy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- comingstorm · Accepted Answer

如果我记得正确，你在递归到目标节点时构建左右树。当找到目标时，使用目标的(原始)子节点构造最终的左右树，将结果树作为新的子节点附加到目标，并以尾递归方式返回结果(即，在没有进一步修改的情况下全部返回到堆栈顶部)。