Максимально сбалансированное двоичное дерево

#algorithm #data-structures #tree #dynamic-programming

#алгоритм #структуры данных #дерево #динамическое программирование

Вопрос:

Я задаю один вопрос по динамическому программированию, где для заданной высоты h я должен вычислить максимальное количество сбалансированных двоичных деревьев. У меня небольшая путаница с базовыми случаями.

Если высота равна 0, то количество сбалансированных двоичных деревьев равно 1, поскольку для h = 0 существует только корневой узел. Но для h = 1 я не могу вычислить максимальное количество сбалансированных двоичных деревьев. Может кто-нибудь мне помочь, пожалуйста?

1. что вы подразумеваете под количеством сбалансированных двоичных деревьев ? вы имеете в виду количество узлов в двоичном дереве или номер поддерева?

2. Не могли бы вы напомнить нам ваше определение сбалансированного двоичного дерева?

3. Общее количество сбалансированных двоичных деревьев, имеющих высоту h.

4. Сбалансированное двоичное дерево — это когда у каждого узла разница между высотами его левого и правого поддерева меньше, чем равна 1.

5. не могли бы вы ответить на мой первый вопрос: что вы подразумеваете под количеством сбалансированных двоичных деревьев?

Ответ №1:

Решение с хорошим объяснением и рисунками можно найти в:

учебная точка с кодом C plus plus
geeksforgeeks с другой реализацией.

Для особых случаев 0 и 1 :
h = 0 => nb = 1, в корне высота равна 0, и у нас есть только один узел, следовательно, 1 дерево.
h = 1 => nb = 3, это означает, что у нас есть эти возможности:

1. Корневой узел только левый дочерний элемент
1. Корневой узел единственный правильный дочерний элемент
1. Корневой узел левый и правый дочерние элементы

Следовательно, при h = 1 у нас есть 3 возможных двоичных дерева.

h = 2 => nb = 15 … и т.д.

1. Объяснение, которое они дали, неверно, потому что, если высота дерева равна 1, это не означает, что у него один узел, потому что для h = 0 существует один узел. Там объяснение немного искажено.

2. @AkhilSharma, их объяснение и код работают нормально. разница только в корне, они рассматривают корень при h = 1, поэтому в своем коде они проверяют, возвращает ли h = 0 или h = 1 1. В вашем случае вы рассматриваете корень на высоте h = 0; поэтому вы проверяете только для h = 0 return 1, иначе выполните ту же рекурсию. И да, высота в корне должна быть равна 0, потому что в определении говорится ** Высота узла в корневом дереве равна числу ребер в максимальном пути **. Но это не имеет большого значения, очень небольшое изменение (учитывайте только 0), и оно работает так же. удачи.