Revisão Sobre Algoritmos Recursivos e Busca em Árvores Binárias

Objetivo 4 Revisão Sobre Algoritmos Recursivos Dizse que um subprograma é recursivo quando ele faz chamadas a ele mesmo Algumas linguagens permitem recursões como única estrutura de repetição ou seja não podem usar laços tais como os produzidos por comandos como for while ou repeat Em geral uma definição recursiva é definida por casos um número limitado de casos base e um caso recursivo Os casos base são geralmente situações triviais e não envolvem recursão Um exemplo comum usando recursão é a função para calcular o fatorial de um natural N 4 4 3 2 1 4 4 3 3 3 2 2 2 1 1 1 0 0 1 n n n 1 n n n 1 n n n 1 n n n 1 0 1 Ou seja Fatorial 4 4 Fatorial 4 1 Fatorial 3 3 Fatorial 3 1 Fatorial 2 2 Fatorial 2 1 Fatorial 1 1 Fatorial 1 1 Fatorial 0 1 Ou seja Fatorial 4 4 Fatorial 4 1 Fatorial 3 3 Fatorial 3 1 Fatorial 2 2 Fatorial 2 1 Fatorial 1 1 Fatorial 1 1 Fatorial 0 1 Fatorial 0 1 1 1 1 2 2 6 6 24 function fatorial x integer integer begin if x 0 then fatorial 1 else fatorial x fatorial x 1 end Objetivo 5 Algoritmo de Busca de um elemento em uma Árvore Binárias de Busca Quero saber se a chave X está na árvore R Lembrando que se trata de uma Árvore Binária de Busca ou seja todas as chaves a esquerda da Raiz são menores e todas as da direita são maiores isso nos dá uma boa ajuda para a busca O problema Considere por exemplo que X 39 e R é a raiz de uma ABB Podemos ter 4 situações para X e R No caso 1 estamos querendo saber se a chave X está em uma árvore vazia Essa situação conseguimos resolver X não está em uma árvore vazia No caso 2 estamos procurando X na árvore R e sabemos que InfoRX Ou seja achamos X na árvore Essa situação também sabemos resolver de imediato No caso 3 estamos procurando X na árvore R e sabemos que InfoRX Ou seja X pode estar na árvore Mas se ela está na árvore então ela deve estar no lado esquerdo da árvore No caso 4 estamos procurando X na árvore R e sabemos que InfoRX Ou seja X pode estar na árvore Mas se ela está na árvore então ela estará no lado direito da árvore RESUMINDO 1 Árvore Vazia X não está na árvore e acaba o algoritmo 2 X InfoR X está na árvore e acaba o algoritmo 3 InfoR X X PODE ESTAR na subárvore esquerda de R O algoritmo não acaba ainda Fazemos uma pesquisa do lado esquerdo da árvore 4 InfoR X X PODE ESTAR na subárvore direita de R O algoritmo não acaba ainda Fazemos uma pesquisa do lado direito da árvore Resumo dos Casos para Busca de X em uma ABB