algorithm - 递归展开树

Question

我正在尝试实现递归展开树，自下而上。我递归到需要展开的节点，然后找到该节点的父节点和祖父节点。然后我可以根据情况进行曲折或曲折。问题是完成此操作后，我将已展开一次的节点返回到上一个递归调用。之前的递归调用引用了节点的父节点，现在是该节点的子节点。我如何在上升时递归展开节点？

Answer 1

如果我没记错的话，当你递归到目标节点时，你会构建一个左右树。找到目标后，使用目标的（原始）子节点构造最终的左右树，将生成的树附加为目标的新子节点，并以尾递归方式返回结果（即，所有方式备份堆栈而无需进一步修改）。

Answer 2

当树完全“不平衡”并且非常大（例如 100000 个 int 键）时，递归算法可能会抛出 stackoverflow 异常。最好在每个节点中使用父指针来获取父或祖父。这是一种方法。对我来说很好。

运行时的结果在这里很明显splay tree runtime profiling