Какое дерево AVL минимального размера, где удаление вызывает 2 поворота?
Хорошо известно, что удаление из дерева 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 мой реальный вопрос: учитывая некоторую константу k, каково дерево AVL минимального размера, которое имеет k вращений после 1 удаления?