AVL конкретная балансировка случая

Question

Я пересматриваю старые базовые алгоритмы для класса I онлайн-курс, который я собираюсь посмотреть после christmass. Это было в целом легкое чтение, пока я не достиг AVL. Когда я изучал их, я не помню, чтобы у меня возникли проблемы, но спустя чуть более 10 лет я уже не так хорош. В то время как я решаю в большинстве случаев легко, я застрял в течение более 5 часов на этом примере:

51 
/\ 
    19 55 
/\ \ 
10 37 61 
    /\ 
    28 46 

Вставка 40 в дерево, слева ребенок 46, требуется один левый поворот, чтобы исправить баланс ... почему ? Не вставлено ли 40 в левую часть правого ребенка 19 лет, который становится неуравновешенным? Почему это не двойное вращение? Что я не вижу?

Answer 1

Вот как это происходит:
1. После вставки:

51 
/\ 
    19 55 
/\ \ 
10 37 61 
    /\ 
    28 46 
    /
    40 

Очевидно, что 19 узел становится несбалансированным.
2. Вот почему он поворачивается влево один раз. Так оно и делается:

 51 
    /\ 
    37 55 
/\ \ 
    19 46 61 
/\ / 
10 28 40 

Теперь дерево снова сбалансировано.

Answer 2

И, как ни странно, попытка объяснить мою проблему показала, что я делаю неправильно. Дерево оставлено тяжелым, а левое поддерево дерева НЕ прав тяжелое, так что это одно вращение.