c - splay tree 中的 ZigZag 和 ZigZag 操作？

Question

考虑一下我的树是这样的

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

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

在同样的情况下，考虑我们正在搜索 4 ，此时将执行 zigzag 操作。首先我们旋转 4 和它的父节点，然后旋转 4 和它的祖先。

为什么我们这样做，在之字形中，为什么我们不旋转父级和祖先而不是搜索节点和父级。

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

Answer 1

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

您在这里描述的是不同的东西。您希望始终先旋转父项，然后再旋转子项。如果您认为这种启发式算法是好的，您需要正式证明它是好的，但要回答这个问题:splay 树中的旋转顺序保证 O(m lg n) 绑定(bind)在一系列 m 操作上。