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)适用于最坏的情况。