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

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

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


data-structures tree avl-tree binary-tree binary-search-tree
person NotSure    schedule 20.05.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

введите здесь описание изображения

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

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

введите здесь описание изображения

person MBo    schedule 21.05.2015
comment
Ну, я не уверен, ошибается ли наш профессор или что это за стандарт, но в нашем классе деревья, о которых вы упомянули, имеют высоту 3, мне нужно выяснить, может ли это произойти, если будет хотя бы еще один узел (высота 5 для тебя). Спасибо в отношении - person NotSure; 21.05.2015