x展開後的子樹在展開操作後是否必須平衡？

Question

問題出在這裏：

設T是n個節點上的一個splay樹，設x是T的一個節點。考慮x處的splay操作。在x下的子樹是否必須平衡（即，在splay操作之後，在splay樹中以x爲根的子樹的高度變爲O（logn）？

我花了很多時間，但仍然感到沮喪。 ..我欣賞你的答案

Answer 1

號考慮絕對的最壞情況，其中T看起來是這樣的：。

y 
\ 
    y 
    \ 
    ... 
    \ 
     x 

其中y s爲任意節點一旦張開x，樹會看像這樣：

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

（同樣，y s爲任意節點）。在這種情況下，深度仍然是O(n)。

編輯：意識到我搞砸了「後」樹，所以用更正確的例子更新我的答案。

Answer 2

否參見these notes。遍歷節點的平均深度減半，但不能保證產生平衡樹。