Splay树旋转算法：为什么使用锯齿形和锯齿形而不是简单的旋转？

我不明白为什么在splay tree数据结构中的旋转不仅考虑了评级节点的父级，还考虑了祖父级（Zig-zag和Zig-zig操作）。为什么下面不工作：Splay树旋转算法：为什么使用锯齿形和锯齿形而不是简单的旋转？

为我们插入，例如，一个新的节点树，我们检查是否插入左或右子树。如果我们插入左侧，我们旋转结果右，反之亦然右子树。递归地，它会是这样的

Tree insert(Tree root, Key k){ 
    if(k < root.key){ 
     root.setLeft(insert(root.getLeft(), key); 
     return rotateRight(root); 
    } 
    //vice versa for right subtree 
}

这应该避免整个“splay”程序，你不觉得吗？

来源

2012-04-10 Bober02

乡亲运行测试[计算机科学]（http://cs.stackexchange.com/）网站可能是真的很高兴帮你出了这个问题。 – Jan 2012-04-10 22:25:51

与这个网站无关？ – Bober02 2012-04-10 22:33:22

我想说它是相关的，但是因为最近CS网站开始的时候，像你这样的算法问题可能更接近CS的兴趣领域。此外，它们处于测试阶段，因此他们肯定会欣赏增加的流量和更多的主题问题。 – Jan 2012-04-10 22:43:20

你在树上提议的算法被称为“移动到根”的启发式，并且被讨论on page four of Sleator and Tarjan's original paper on splay trees.他们引用了Allen和Munro的一篇老论文，它显示如果你尝试使用move-to - 根作为重塑树木的手段，每次查找的摊销成本可能是O（n），这很慢。 Splaying是一种非常精心设计的算法，用于重塑树形结构，并且无论访问顺序如何，它都可以保证O（log n）查找的分期偿还。

直观地说，移动到根并不是一个很好的重塑树的方式，因为它会沿着从节点到根的路径上的所有节点向下移动，同时尝试使未来访问的节点更容易到达。因此，在执行此版本的树重组时，整个树会变得更糟。另一方面，斜展方法倾向于减小斜切节点和其访问路径上的所有节点的高度，这意味着总体上在倾斜期间树趋于变好。

希望这会有所帮助！

来源

2012-12-27 19:26:06 templatetypedef

Splay树旋转算法：为什么使用锯齿形和锯齿形而不是简单的旋转？

回答

相关问题