AVL Высота дерева как функция узлов

Question

Я пытаюсь найти способ узнать высоту дерева AVL как функцию его узлов.

Я хочу знать, можно ли создать дерево AVL на высоте 4 с ровно 11 узлами. Я знаю, что верхняя граница высоты дерева AVL составляет приблизительно 1,44 * logn. Поэтому, если у меня 11 узлов, это на самом деле 4.32. И все же, я пытаюсь построить один с высотой 4 в течение как минимум 2 часов и не делать этого каждый раз.

Answer 1

Построить полное двоичное дерево высотой 4 с 15 узлами.

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

Один вариант (из вики):