algorithm - 展開されている x の下のサブツリーは、展開操作の後に必然的にバランスが取れますか?

Question

問題は次のとおりです。

T を n ノード上のスプレイ ツリーとし、x を T のノードとする。x でのスプレイ操作を考える。x の下のサブツリーは必然的にバランスが取れますか (つまり、スプレイ ツリーの x をルートとするサブツリーの高さは、スプレイ操作後に O(logn) になりますか?

私はそれに多くの時間を費やしましたが、それでもイライラしています....あなたの答えに感謝します。

Answer 1

いいえ。 T が次のような絶対的な最悪のケースを考えてみてください。

y
 \
  y
   \
   ...
     \
      x

ここで、ys は任意のノードです。スプレーxすると、ツリーは次のようになります。

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

(ここでも、ys を任意のノードとして)。その場合、深さはまだO(n)この場合です。

編集:「後」ツリーを台無しにしたことに気付いたので、より正しい例で回答を更新しました。

Answer 2

いいえ。これらの注を参照してください。トラバースされたノードの平均的な深さは半分になりますが、バランスの取れたツリーが得られるとは限りません。