递归伸展树 [英] Recursive Splay Tree

问题描述

我想实现一个递归伸展树，自底向上。我递归到我需要张开了点，我觉得该节点的父母和祖父母。然后，我能要么曲折或根据情况就好了锯齿锯齿。现在的问题是在此之后完成时，我返回已被显示出来，一旦到previous递归调用的节点。在previous递归调用参考节点，这是目前该节点的孩子的父母。我如何递归了张开的节点，因为我去了？

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?

推荐答案

如果我没有记错，你建立一个左右的树，你递归下降到目标节点。当你发现了目标，你建立基于目标的（原来的）孩子最终左右的树木，附上所产生的树木为目标的新的孩子，在尾递归的方式返回的结果（即所有回来的路上堆栈没有进一步修改）。

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).

这篇关于递归伸展树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！