algorithm - x 下的子树在展开操作后是否一定会变得平衡？

Question

这是问题所在：

令 T 为 n 个节点上的伸展树，令 x 为 T 的一个节点。考虑在 x 处的伸展操作。x下的子树是否必然平衡（即splay树中以x为根的子树的高度在splay操作后变成O(logn)）？

我花了很多时间，但仍然感到沮丧....感谢您的回答。

Answer 1

不。考虑一下 T 看起来像这样的绝对最坏情况：

y
 \
  y
   \
   ...
     \
      x

其中ys 是任意节点。展开x后，树将如下所示：

  x
 /
y
 \
  y
 / \
y   y
   / \
  y   y
     / \
    y  ...
         \
          y

（同样，ys 作为任意节点）。那么深度，仍然是O(n)在这种情况下。

编辑：意识到我搞砸了“之后”树，所以用更正确的例子更新我的答案。

Answer 2

不，请参阅这些说明。遍历节点的平均深度减半，但这并不能保证产生平衡的树。