Количество деревьев поиска AVL с n узлами и x листьями? - PullRequest
Новая
       74

Количество деревьев поиска AVL с n узлами и x листьями?

0 голосов
/ 11 февраля 2019

Этот вопрос был задан несколько лет назад здесь , но не было дано правильного ответа.

Я знаю, что дерево сбалансировано по AVL, если для какого-либо узла высота его слева иПравое поддерево отличается не более чем на один.

Учитывая определенное количество (назовем это n) узлов, с определенным числом (скажем, x) листьев, сколько различных AVL-сбалансированных форм дерева имеют n узлов и x листьев?

Например, есть две формы дерева для 5 узлов и 3 листьев .

Я попытался реализовать принятый ответ на этот вопрос в python в моемфункция num_trees_w_height, которая затем используется для вычисления общего количества деревьев любой высоты в num_trees.Вот мой код: 

def num_trees_w_height(height, nodes, leaves):
    if nodes == 0 or leaves == 0:
        return 0
    if height > math.log(nodes,2) or leaves > nodes//2+1:
        return 0
    if height == 0:
        return 1
    for h in range(0,height+1):
        for n in range(0,nodes+1):
                return num_trees_w_height(h-1,n,l)\
                    *num_trees_w_height(h-1,nodes-n,leaves-l)\
                    +num_trees_w_height(h-1,n,l)\
                    *num_trees_w_height(h-2,nodes-n,leaves-l)\
                    +num_trees_w_height(h-2,n,l)\
                    *num_trees_w_height(h-1,nodes-n,leaves-l)

def num_trees(nodes, leaves):
    num=0
    for height in range(0,nodes):
        num += num_trees_w_height(height,nodes,leaves)
    return num

Однако, когда я звоню num_trees(5,3), я получаю TypeError, говорящую, что мой рекурсивный оператор возврата пытается умножить int и NoneType, и когда яcall num_trees_w_height(3,5,3) Я получаю 0. Оба эти вызова должны возвращать 2, как показано в моем примере выше.

...