1

我不太明白为什么 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
}

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

4

1 回答 1

5

您在树上提出的算法称为“移动到根”启发式算法，并在 Sleator 和 Tarjan 关于展开树的原始论文的第四页进行了讨论。他们引用了 Allen 和 Munro 的一篇较早的论文，该论文表明，如果您尝试使用移至根作为重塑树的方法，则每次查找的摊销成本可能为 O(n)，即很慢。展开是一种非常精心设计的用于重塑树的算法，无论执行何种访问顺序，它都能保证平均 O(log n) 查找。

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

希望这可以帮助！

于 2012-12-27T19:26:06.377 回答