Бинарное дерево T является полусбалансированным, если для каждого узла m в T:
R(m)/2 <= L(m) <= 2*R(m),
где L (m) - количество узлов в левом поддереве m, а R (m) - количество узлов в правом поддереве m.
(a) Напишите рекуррентное соотношение для подсчета количества полусбалансированных двоичных деревьев с N узлами.
(b) Предоставьте алгоритм динамического программирования для вычисления повторения в (a).
Как мне сделать для этого отношение повторения?
Подходит ли следующее?
if(node==NULL)
return;
if(given relation is true)
count++
else find for right tree;
find for left tree;
Я предполагаю, что он спрашивает больше о рекуррентном отношении, таком как функция или что-то в этом роде.?
Также как мне решить задачу с помощью динамического программирования? Думаю, мне не нужно ничего хранить, если я применю предложенный выше фрагмент кода.
Пожалуйста, помогите.
