algorithm - 递归伸展树(Splay Tree)

Question

我正在尝试自下而上地实现递归伸展树(Splay Tree)。我向下递归到需要展开的节点，然后找到该节点的父节点和祖父节点。然后，我可以根据情况进行之字形或之字形。问题是完成后，我将已经张开一次的节点返回到之前的递归调用。先前的递归调用引用了节点的父节点，现在是该节点的子节点。如何递归向上展开节点？

Answer 1

如果我没记错的话，您在向下递归到目标节点时构建了左右树。当您找到目标时，您使用目标的(原始)子节点构建最终的左树和右树，将生成的树附加为目标的新子节点，并以尾递归方式返回结果(即，所有无需进一步修改即可备份堆栈)。