algorithm - BST から AVL アルゴリズムへの最悪の場合のローテーション数は?

Question

以下に基本的なアルゴリズムを示します。最悪の場合の入力 BST は、片側のみへの挿入からリンク リストに縮退したものであることがわかっています。

この BST から AVL への変換アルゴリズムの回転数に関して最悪の場合の複雑さを計算するにはどうすればよいですか?

IF tree is right heavy
{
  IF tree's right subtree is left heavy
  {
     Perform Double Left rotation 
  }
  ELSE
  {
     Perform Single Left rotation
  }
}
ELSE IF tree is left heavy
{
  IF tree's left subtree is right heavy
  {
     Perform Double Right rotation
  }
  ELSE
  {
     Perform Single Right rotation
  }
}

Answer 1

シングルとダブルのローテーションに一定の時間がかかるO(1)場合、最悪の場合のサイズの入力でnは、すべてのノードでシングル (入力リンク リストが左側か右側かによってはダブル) が実行されます。したがって、次のようになります。

O(1) + O(1) + ... + O(1) # n times for worst case

これにより、アルゴリズムO(n)が最悪のケースになります。