data-structures - Splay树旋转算法: Why use zig-zig and zig-zag instead of simpler rotations?

Question

我不太明白为什么 splay 树数据结构中的旋转不仅要考虑评级节点的父节点，还要考虑祖父节点(zig-zag 和 zig-zig 操作)。为什么以下内容不起作用:

例如，当我们向树中插入一个新节点时，我们会检查我们插入的是左子树还是右子树。如果我们向左插入，我们将结果向右旋转，右子树则相反。递归地它会是这样的

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

这应该避免整个“展开”过程，你不觉得吗？

Answer 1

您在树上提出的算法称为“移动到根”启发式算法，并进行了讨论 on page four of Sleator and Tarjan's original paper on splay trees.他们引用了 Allen 和 Munro 的一篇较旧的论文，其中显示如果您尝试使用移动到根作为 reshape 树的方法，则每次查找的摊销成本可能为 O(n)，即很慢。 Splaying 是一种经过精心设计的树 reshape 算法，无论执行何种访问顺序，它都能保证平摊 O(log n) 查找。

从直觉上讲，移动到根并不是 reshape 树的好方法，因为它会向下移动从节点到根的路径上的所有节点，同时试图使访问的节点在未来更容易到达。因此，在进行此版本的树重组时，整个树会变得更糟。另一方面，splay 方法倾向于降低展开节点及其访问路径上所有节点的高度，这意味着作为一个整体，树在展开过程中往往会变得更好。

希望这对您有所帮助!