递归Splay树

我想实现一个递归的splay树，自下而上。我递归到我需要展开的节点，并找到该节点的父节点和祖父节点。然后，我可以根据情况做出曲折或曲折的曲折。问题是在完成之后，我将返回已经展开一次的节点返回到先前的递归调用。先前的递归调用被引用到该节点的父节点，该节点现在是该节点的子节点。随着我上升，我该如何递增节点？递归Splay树

来源

2010-03-03 Andrew

是什么递归伸展树和正常之间的区别？ – Svante 2010-03-03 20:29:25

递归意味着节点从下向上递归展开。正常的意味着从顶部向上播放节点 – Andrew 2010-03-03 22:10:03

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

来源

2010-03-04 08:07:13 comingstorm

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

上运行的效果显着位置splay tree runtime profiling

来源

2012-01-18 03:49:03

回答

相关问题