Возможны различные формы АВЛ на высоте h

Дерево AVL : это самобалансирующееся двоичное дерево поиска, в котором коэффициент баланса не может быть больше одного для всех узлов. Фактор баланса можно определить как разницу между высотами левого и правого поддерева.

Пример:

Задача состоит в том, чтобы найти возможное количество различных форм минимального AVL-дерева высоты h, которое может быть сформировано. Это можно понять, создав деревья, а затем сгенерировав обобщенную формулу для этого вычисления.

Решение :

Пусть N (h) обозначает количество возможных деревьев, а h обозначает высоту AVL-дерева . На рисунке ниже возможные деревья показаны по форме в соответствии с их высотой. В первом столбце показан анализ высоты, а во втором столбце показаны возможные деревья.

Давайте теперь обобщим приведенные выше наблюдения:

Формулу можно обобщить как:

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.