c - 展开树中的 ZigZag 和 ZigZig 操作？

Question

考虑我的树是这样的

                 5
                / \
               3   7
              / \ / \
             2  4 6  8

在那里，当我们搜索一个元素2时，将执行 zigzig 操作，所以首先旋转parent and ancestor of 2，然后旋转 a parent and 2。

在同样的情况下，考虑到我们正在搜索4，那个时候会执行 zigzag 操作。在那个第一个我们旋转4 and its parent然后4 and its ancestor将被旋转。

为什么我们这样做，在锯齿形中，为什么我们不旋转parent and ancestor而不是searching node and parent.

请解释一下？？提前致谢。

Answer 1

旋转的顺序很重要。这就是使O(lg n)每个操作的分析产生时间在一系列 m 操作中摊销的原因。启发式将splay(x)节点 x 移动到树的根节点，但不是仅仅旋转 x 直到它成为根节点，zigzig 步骤首先旋转 x 的父节点，然后旋转 x。例如，如果我们只是旋转 x 直到它成为根，那么分析将不会产生有用的东西。

你在这里描述的是不同的东西。您希望始终先旋转父级，然后再旋转子级。如果您认为它是好的，您需要正式证明这种启发式是好的，但要回答这个问题：展开树中的旋转顺序保证了O(m lg n)m 操作序列的界限。