Сколько максимальных высот AVL деревьев с учетом высоты?

Question

У меня возникли проблемы с поиском рекурсивной формулы для определения количества деревьев AVL максимальной высоты с высотой h.Высота 0 имеет 1, высота 1 имеет 2, высота 2 имеет 4, высота 3 имеет 8 и т. Д. Это правильно?

Answer 1

Давайте посмотрим на эту проблему с другой точки зрения.

Вместо максимальной высоты для данного количества узлов, давайте найдем минимальное количество узлов для данной высоты.Для этой проблемы у нас есть эта рекурсивная функция: n(h) = n(h-1) + n(h-2) + 1, потому что вам нужно как минимум n(h-1) узлов в правом поддереве и n(h-2) узлов в левом поддереве и один узел для корня.

(изображение и более полное объяснение здесь ).

Имея это в виду, вы должны найти h такойчто n(h) < n < n(h+1), где n - это ваше заданное количество узлов.

Кстати, короткий ответ h < 2log(n) + 2

Answer 2

Максимальное количество узлов n в дереве высоты AVL h равно n = 2^0 + 2^1 + ... + 2^(h-1) = 2^h - 1 (каждый узел, кроме корня, имеет обоих дочерних элементов, что означает, что каждый уровень имеет в два раза больше узлов, чем предыдущий).Это дает формулу высоты h с точки зрения количества узлов n как: h = log(n + 1).