Самое маленькое дерево AVL, такое, что последовательные вставки вызывают все четыре случая вращения

Question

Я должен построить дерево AVL, используя вставки целочисленных значений, начиная с нуля, так что все четыре случая поворотов дерева (простой слева, простой справа, двойной слева и двойной справа) происходят после последовательных вставок. Я полагаю, что не так много работы, чтобы продемонстрировать такой пример, но найти минимальный пример и доказать, что найденный пример самый маленький, кажется немного сложнее. Кто-нибудь знает, как поступить? То, что двойные повороты должны происходить, накладывает некоторые ограничения относительно минимальной высоты дерева, по крайней мере.

Answer 1

Независимо от того, с какого поворота вы начинаете, вам всегда понадобятся 3 узла, чтобы вызвать первое вращение, и в этой точке у вас всегда будет сбалансированное дерево. Как только дерево сбалансировано, вам нужно минимум 2 узла, чтобы вызвать другой дисбаланс.

---

Значения случайные.

Единственное право

50, 25, 10

Двойное право

5, 8

Один слева

75, 100

Двойной левый

63, 55

Можно визуализировать здесь https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

Маленькая деталь реализации, но двойной поворот - это просто комбинация двух противоположных вращений.