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

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

您在树上提出的算法称为“移至根”启发式算法，有关Sleator和Tarjan关于八角树的原始论文的第四页对此进行了讨论。他们引用了艾伦（Allen）和蒙罗（Munro）的较早论文，其中表明，如果您尝试使用“移至根”作为重塑树的方法，则每次查找的摊销成本可能为O（n），即相当慢。展开是一种非常精心设计的用于重塑树的算法，并且无论执行什么访问顺序，它都保证了摊销的O（log n）查找。

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

希望这可以帮助！