Como calcular a altura da árvore binária Part2: usando recursão

Ryan Vergara Blocked Unblock Seguir Seguindo 7 de janeiro

Anteriormente escrevi sobre um algoritmo para descobrir a altura de uma árvore binária usando iteração . Embora esse método faça o trabalho (em não menos de 7 etapas), o mesmo pode ser realizado de uma maneira muito mais simples.

Imagem da cidade Hyde Park em Chicago por Steve Hall. Imagem encontrada em http://studiogang.com/project/city-hyde-park

Na minha opinião, uma das técnicas de programação mais poderosas é a recursão. Para leitores novatos em programação – é simplesmente uma função ou método chamando a si mesmo. Para tornar a introdução mais simples, temos um método abaixo que chama outro método:

 def outer_method (nome) (R1) 
inner_method + name
fim
 def inner_method (R2) 
"Olá "
fim
 print outer_method ("Steve") -> # "Olá, Steve" 

No método acima, outer_method , que recebe uma string como argumento, chama inner_method , que simplesmente retorna a string “Hello “ dentro dela. A recursão é semelhante, digamos, nesse caso, o outer_method simplesmente chama a si mesmo:

 def outer_method (nome) (R3) 
outer_method ("olá") + nome
fim (R3)

Uma ressalva, porém, com o código R3 acima – ele será executado até que o computador afirme que os recursos não são suficientes para continuar processando o método. É como executar um loop infinito, exceto que loops infinitos não necessariamente geram exceções. A razão para isso é que o código R3 não tem um 'estado terminal' ou um ponto em que não 'recurse' mais.

Podemos resolver isso incluindo um estado terminal:

 def outer_method (nome) (R4) 
return name if name == "olá"
outer_method ("olá") + nome
fim

A primeira linha dentro da definição do método simplesmente declara que se o name do argumento for igual a 'hello' , simplesmente retorne o name . Isso então irá ignorar qualquer linha depois dela. Portanto, na segunda linha, o código outer_method(“hello “) simplesmente fornecerá a string "hello" para ser adicionada a qualquer nome que esteja no argumento principal. Portanto, a mesma print outer_method(“Steve”) resultará na saída “hello Steve” também.

OK, então, esse pode não ser o melhor exemplo para descrever a recursão (já que a versão recursiva, neste caso, não tem muita vantagem sobre a não-recursiva). Mas trabalhando no problema da altura da árvore binária, veremos que a recursão é muito mais simples de entender e mais rápida de executar.

Para esta discussão, deixe-me colocar novamente o mesmo exemplo que mostrei no artigo anterior:

Figura 1: Árvore binária simples

que podemos representar como o seguinte array:

 árvore = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0] (T0) 

Os índices dos filhos da esquerda e da direita de qualquer sub-árvore podem ser determinados da seguinte maneira:

 criança esquerda da árvore [i] está no índice 2 * i + 1 (T1) 
filho certo da árvore [i] está no índice 2 * i + 2 (T2)

Se você está intrigado sobre como a figura acima se tornou a matriz seguinte, vou orientá-lo para ler o artigo anterior sobre o método iterativo de esclarecimento.

E novamente a fórmula para calcular a altura de uma árvore binária, assim como as alturas de qualquer uma de suas sub-árvores, é:

 height = 1 + max de (left_child_height, right_child_height) (T3) 

Agora, com estes, podemos delinear os passos para desenvolver um programa recursivo.

Passo 0: Definir valores padrão – Para tornar a chamada do método inicial simples, sempre gosto de definir valores padrão para os argumentos que serão alterados durante cada chamada recursiva. Como vamos calcular repetidamente alturas, nossos índices sempre mudam.

Por exemplo, para encontrar a altura do filho à esquerda da raiz ( tree[0] ), precisaremos chamar o método naquele filho da esquerda (cujo índice é 2*(0) + 1 ). Portanto, nossa definição de método será:

 def tree_height_recursive (tree_array, i = 0) (S0.1) 

para indicar que, para a chamada inicial, estamos chamando-a no elemento-raiz. Isso simplesmente nos permitirá chamar tree_height_recursive , inserindo apenas o tree_array. No entanto, isso também significa, como veremos na simulação depois, podemos encontrar a altura de qualquer sub-árvore simplesmente incluindo seu índice como o segundo argumento na chamada do método.

Etapa 1: Encontrar o estado do terminal – Em que ponto simplesmente retornamos um valor e não fazemos mais chamadas recursivas? Em nosso problema de árvore binária, o estado do terminal está em:

 retornar 0 se árvore [i] .nil ou árvore [i] == 0 (S1.1) 

Ele simplesmente diz que se o elemento no índice i não existir ou se seu valor for 0, simplesmente retorne 0. Logicamente, uma subárvore não existente não terá nenhuma altura.

Passo 2: Encontre a altura da criança esquerda – é aí que a magia da recursão começa a nos beneficiar. Nós não precisamos de nenhum código de fantasia. Não mais declarar outro array para manter a altura de cada elemento. Não há mais várias definições de variáveis para os índices de altura e as alturas em si, apenas:

 left_child_height = tree_height_recursive (tree_array, 2 * i + 1) (S2.1) 

Nós simplesmente passamos o índice da criança esquerda como segundo argumento. Você pode ver por quê?

Nós fazemos o mesmo para encontrar a altura da criança certa em seguida.

Passo 3: Encontre a altura do filho certo – Da mesma forma, simplesmente fazemos uma chamada recursiva para o nosso método, mas passando o índice do filho certo como segundo argumento:

 right_child_height = tree_height_recursive (tree_array, 2 * i + 2) 

Agora que temos as alturas dos filhos da esquerda e da direita, agora podemos calcular a altura total.

Etapa 4: Calcular e retornar a altura total – Como o código T3 declara, apenas adicionamos 1 e a altura do que for mais alto entre os filhos da esquerda e da direita.

 total_height = 1 + [left_child_height, right_child_height] .max (S4.1) 

Como o S.4 será a última declaração em nosso método, o total_height avaliado será retornado. Lembre-se de que, se as condições em S1.1 verdadeiras (nosso estado terminal), nenhuma das etapas 2 a 4 será executada e o método retornará 0.

O método completo abaixo:

Comparando isso com o método iterativo , a versão recursiva levou 3 passos a menos e 4 menos definições de variáveis. O código também (excluindo espaços vazios e comentários) tem menos 7 linhas. Além disso, o código recursivo será executado duas vezes mais rápido (usando o módulo Ruby embutido no benchmark ). Esta é uma grande vantagem se estivermos executando o método em árvores binárias com centenas de níveis de altura.

Agora vamos fazer a mesma simulação que fizemos antes. Para a árvore em T0 nós executamos o método recursivo:

 tree = [1, 7, 5, 2, 6, 0, 9, 3, 7, 5, 11, 0, 0, 4, 0] 
 puts tree_height_recursive (tree_array) -> #deve nos dar 4 

Observe que, como temos um i=0 padrão em nossa definição de método, não precisamos especificar o índice aqui porque estamos descobrindo a altura da árvore inteira. Para tornar essa simulação mais intuitiva, criaremos um array imaginário chamado call_stack onde cada chamada será tree_height_recursive para tree_height_recursive .

Então, quando chamamos o método pela primeira vez (a chamada principal), armazenamos em uma variável temporária ht_0 e a call_stack para call_stack :

 ht_0 = altura da árvore [0] = tree_height_recursive (tree_array, i = 0) 
 call_stack = [ht_0] 

Em seguida, executamos o Passo 1:

 árvore [0] .nil? -> #false 
árvore [0] == 0 -> #false, é 2

Como isso resulta em false , seguimos para a Etapa 2:

 desde i = 0, então 2 * i + 1 = 2 * 0 + 1 = 1: 
 left_child_height = tree_height_recursive (tree_array, 1) 

Já que não podemos determinar prontamente essa altura, então nós a pressionamos novamente para call_stack :

 ht_1 = left_child_height = tree_height_recursive (tree_array, 1) 
 call_stack = [ht_0, ht_1] 

Então, ao fazer o passo 3:

 ht_2 = right_child_height = left_child_height = tree_height_recursive (tree_array,) 
 call_stack = [ht0, ht1, ht2] 

Não podemos prosseguir para o Passo 4 até que todos os itens em call_stack tenham sido avaliados pelo nosso programa e retirados de call_stack (o que deve acontecer sempre que cada altura for avaliada).

Então, nós também faremos o mesmo para cada uma das alturas seguintes. Por exemplo, para calcular o ht1 , sabemos que também temos de calcular para as alturas das suas próprias crianças da esquerda e da direita. Isso significa que o método também será chamado para eles. Para não prolongar este artigo, o leitor é convidado a experimentar isso no papel.

Por fim, o método será chamado recursivamente com i = 14 como segundo argumento. Assim, neste momento, call_stack será:

 call_stack = [ht0, ht1, ht2, ht3, ht4, ht5, ht6, ht7, ht8, ht9, ht10, ht11, ht12, ht13, ht14] 

Agora vamos avaliar cada um. Note que de tree[7] até tree[14] os elementos não possuem filhos. Assim, podemos simplesmente avaliar suas alturas como 1 ou 0 (dependendo se a tree[i] é 0 ou não (onde i ? 7 ):

 ht14 = 0 
 ht13 = 1 
 ht12 = 0 
 ht11 = 0 
 ht10 = 1 
 ht9 = 1 
 ht8 = 1 
 ht7 = 1 

Mais uma vez, quando essas alturas são avaliadas, simplesmente as call_stack. sucessivamente de call_stack. Depois disso, call_stack aparecerá da seguinte forma:

 call_stack = [ht0, ht1, ht2, ht3, ht4, ht5, ht6] 

Agora, para avaliar o ht6 , devemos lembrar que é a chamada para tree_height_recursive(tree_array, 6) . Dentro desta chamada nós também chamamos o método para computar as alturas dos filhos da tree[6] . Estes nós já avaliamos anteriormente como ht13 e ht14 . Então:

 ht6 = 1 + [ht13, ht14] .max = 1 + [1,0] = 1 + 1 = 2 

Então nós agora avaliamos ht5 , que é a altura da tree[5] . Nós sabemos que as alturas de seus filhos são ht11 e ht12

 ht5 = 1 + [ht11, ht12] .max = 1 + [0,0] .max = 1 + 0 = 1 

Fazendo o mesmo para ht4 a h1 (novamente o leitor é convidado a fazer a confirmação no papel):

 ht4 = 1 + [ht9, ht10] .max = 1 + [1,1] .max = 1 + 1 = 2 
 ht3 = 1 + [ht7, ht8] .max = 1 + [1, 1] .max = 1 + 1 = 2 
 ht2 = 1 + [ht5, ht6] .max = 1 + [1,2] .max = 1 + 2 = 3 
 ht1 = 1 + [ht3, ht4] .max = 1 + [2,2] .max = 1 + 3 = 3 

Mais uma vez, call_stack cada altura de call_stack medida que avaliamos, então, após avaliar ht1 o call_stack aparece da seguinte maneira:

 call_stack = [ht0] 

Agora, a avaliação de ht0 está retornando para a chamada principal para tree_height_recursive , portanto, esta é a etapa restante 4:

 ht0 = 1 + [ht1, ht2] .max = 1 + [3, 3] .max = 1 + 3 = 4 
ou
total_height = 1 + [left_child_height, right_child_height] .max

Que retornará 4 como resultado da chamada do método principal.

Como eu continuo mencionando, fazer isso no papel, seja durante a formulação do algoritmo ou durante a simulação, ajudará muito a compreendê-lo. Esse mesmo método também pode ser usado para determinar a altura de qualquer uma das subárvores dentro do tree_array , por exemplo, para determinar apenas a altura do filho à esquerda da árvore:

 puts tree_height_recursive(tree_array, 1) -> #will print out 3 

Ou qualquer uma das sub-árvores inferiores:

 puts tree_height_recursive(tree_array, 3) -> #will print out 2 

Empacotando

O principal argumento para criar um algoritmo recursivo, na minha perspectiva, é definir o estado do terminal. Novamente, este é o cenário em que o método principal não terá que fazer nenhuma chamada recursiva para si mesmo. Sem isso, o método continuará se chamando até o computador explodir (falando hiperbolicamente …). Quando temos o estado terminal, podemos facilmente configurar os argumentos para as chamadas recursivas e saber que nosso método retornará com segurança o valor que esperamos.

Finalmente, trabalhar em algoritmos desafia nossas mentes a pensar. Como engenheiros de software, ou mesmo engenheiros em geral, nossa principal tarefa é resolver problemas. Nós, portanto, precisamos desenvolver nossas habilidades de pensamento crítico.

Se por um problema, nossa primeira opção é sempre 'google it' e copiar / colar o código de outras pessoas sem entender completamente o problema e a solução copiada, então estamos nos derrotando.

Então, minha sugestão é sempre ter caneta e papel prontos e não digitar imediatamente código quando confrontados com um desafio de algoritmo. Simule o problema para entradas simples e, em seguida, crie o código depois de determinar as etapas (como descrevi acima).

Siga-me no Twitter | Github

Microverse é uma das melhores escolas de engenharia de software do planeta!