Хорошо известно, что удаление из дерева AVL может привести к несбалансированности нескольких узлов. Мой вопрос, что такое дерево AVL минимального размера, так что требуется 2 поворота (ям при условии, что левый-правый или правый-левый поворот равен 1 обороту)? В настоящее время у меня есть дерево AVL с 12 узлами, удаление которых может вызвать 2 поворота. Мое дерево AVL вставляется в следующем порядке:

8, 5, 9, 3, 6, 11, 2, 4, 7, 10, 12, 1.

Если вы удалите 10, 9 станет несбалансированным, и произойдет вращение. При этом 8 становится неуравновешенным, и происходит другое вращение. Есть ли меньшее дерево, где после удаления необходимо 2 поворота?

После прочтения jpalecek 's комментарий, мой реальный вопрос: Учитывая некоторую константу k, каково дерево AVL минимального размера, у которого есть k вращений после 1 удаления?