Худший случай числа оборотов для алгоритма 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) для наихудшего случая.