Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Em uma árvore binária os nós podem ter zero, uma ou duas árvores filhas. Especifique uma função recursiva f(n) que determine o número de diferentes árvores binárias que podem ser construídas com n nós.

+1 voto
30 visitas
perguntada Mai 16 em Ciência da Computação por Pedro Henrique T (16 pontos)  

A imagem será apresentada aqui.

A título de exemplo, a figura mostra as cinco possibilidades de árvores binárias que podem ser formadas com n=3 nós.

Compartilhe

1 Resposta

0 votos
respondida Mai 16 por Pedro Henrique T (16 pontos)  

Dado o número de nós da árvore, o número de possíveis configurações possui uma solução explícita popularmente conhecida como número de Catalan. A expressão em questão é dada por
\begin{equation}
C_{n}=\frac{1}{n+1} {{2n}\choose {k}}\text{,}
\end{equation}
sendo n o número de nós da árvore.

Ao tentar implementar um algoritmo recursivo que forneça o número de possíveis configurações, fica mais fácil compreender a natureza combinatória do fenômeno.

Suponha que V={1,2,3,...,n} seja o conjunto de todos os nós da árvore. O primeiro procedimento para definir uma possível configuração é escolher um determinado nó Vi que irá representar a raiz da árvore. Uma vez escolhida a raiz, naturalmente tem-se uma divisão dos elementos em dois grupos (os nós que se encontram à esquerda de Vi e os nós que se encontram à direita). Para cada grupo existe mais uma determinada quantidade de possíveis configurações das árvores filhas.

É preciso pensar em uma fórmula recursiva que leve em consideração todas as possibilidades de escolha da raiz e todas as possibilidades de configuração das árvores filhas subsequentes. Assim, diferentemente da maioria dos algoritmos recursivos, para o problema em questão é preciso desenvolver uma expressão recursiva dentro da qual exista um somatório que irá abranger toas as raízes possíveis. A expressão é definida como
\begin{equation}
R(n)=\sum_{i=1}^{n}R(i-1)R(n-i)\text{,}
\end{equation}
em que i representa uma escolha de raiz e o produto dentro do somatório é tal que aborda todas as possíveis combinações das configurações das árvores filhas da esquerda com as configurações das árvores filhas da direita . A forma recursiva acima foi implementada em python:

def number_of_binary_trees(n):
if(n == 0):
    return 1
elif(n == 1):
    return 1
else:
    parcial_result =[ ]
    for i in range(1,n+1):
        parcial_result.append(number_of_binary_trees(i-1)*number_of_binary_trees(n-i))
    return sum(parcial_result)


#Utilizando a função para n=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15:
    y=[]
    for i in range(1,16):
        y.append(number_of_binary_trees(i)) 
    y
#[1,
 #2,
 #5,
 #14,
 #42,
 #132,
 #429,
 #1430,
 #4862,
 #16796,
 #58786,
 #208012,
 #742900,
 #2674440,
 #9694845]

Na maioria das vezes, para se verificar a complexidade computacional de algoritmos recursivos utiliza-se o Teorema Mestre, mas devido ao fato de termos um somatório dentro da recursão, a utilização do teorema torna-se impossível. A fim de se ter uma noção da complexidade, computou-se o tempo de processamento da função para cada n pertencente a uma sequência de 1 a 15.

import matplotlib.pyplot as plt
import time

tempo=[]
for i in range(1,16):
    inicio=time.clock()
    number_of_binary_trees(i)  
    fim=time.clock()
    tempo.append(fim-inicio)



plt.plot(range(1,16),tempo)
plt.xlabel('nos')
plt.ylabel('Tempo em segundos')
plt.title('Tempo de processamento vs quantidade de nos')
plt.grid(True)

A imagem será apresentada aqui.

Como esperado, o algoritmo possui uma complexidade exponencial (possui complexidade combinatória).

...