Recursividade, Árvores e Grafos: Conceitos

O que é Recursividade?

Uma rotina ou função é recursiva quando chama a si mesma, seja de forma direta ou indireta.

• Direta: Quando chama a si mesma, quando dada situação requer uma chamada da própria rotina em execução para si mesma. Exemplo: O exemplo de fatorial recursivo dado acima.
• Indireta: Funções podem invocar a si próprias indiretamente, fazendo isto através de outras funções. Assim, "P" pode chamar "Q" que chama "R" e assim por diante, até que "P" seja novamente invocada.

Resposta = Fat_Recursivo(5)------------|120

Fat_Recursivo(5) = 5*Fat_Recursivo(5-1)P(B)----|24

Fat_Recursivo(4) = 4*Fat_Recursivo(4-1)P(E)---|6

Fat_Recursivo(3) = 3*Fat_Recursivo(3-1)----|>

Fat_Recursivo(2) = 2*Fat_Recursivo(2-1) P(F)-->

Fat_Recursivo(1) = 1------------------------| P(C)

Qual a desvantagem da Recursão?

Cada chamada recursiva implica em maior tempo e espaço, pois, toda vez que uma rotina é chamada, todas as variáveis locais são recriadas.

Qual a vantagem da Recursão?

Se bem utilizada, pode tornar o algoritmo elegante, conciso e simples. Mas, é preciso antes decidir sobre o uso da Recursão ou da Iteração.

Árvores

Uma árvore é um tipo abstrato de dados que armazena elementos de maneira hierárquica.

Uma árvore T é um conjunto de nodos que armazenam elementos em relacionamentos pai-filho com as seguintes propriedades:

• T tem um nodo especial, r, chamado de raiz de T.
• Cada nodo v de T diferente de r tem um nodo pai u.
• Se um nodo u é pai de um nodo v, então dizemos que v é filho de u.
• Dois nodos que são filhos de um mesmo pai são irmãos.
• Um nodo é externo (ou folha) se não tem filhos.
• Um nodo é interno se tem um ou mais filhos.
• Uma subárvore de T enraizada no nodo v é a árvore formada por todos os descendentes de v em T (incluindo o próprio v).
• O ancestral de um nodo é tanto um ancestral direto como um ancestral do pai do nodo.
• Um nodo v é descendente de u se u é um ancestral de v. Ex: na figura acima, "Meus documentos" é ancestral de "2º Semestre" e "2º Semestre" é descendente de "Meus documentos".

Seja v um nodo de uma árvore T. A profundidade de v é o número de ancestrais de v, excluindo o próprio v. Observe que esta definição implica que a profundidade da raiz de T é 0 (zero). Como exemplo, na figura acima, a profundidade do nodo "Trabalhos" é 2, e a profundidade do nodo "2º semestre" é 3.

A altura de um nodo é o comprimento do caminho mais longo desde nodo até um nó folha ou externo. Sendo assim, a altura de uma árvore é a altura do nodo Raiz. No exemplo acima, a árvore tem altura 3. Também se diz que a altura de uma árvore T é igual à profundidade máxima de um nodo externo de T.

C:\            | Métodos de Uma Árvore

Meusdocs |Raiz, Pai(nodo), Filho(nodo), Nodo_eh_Interno(nodo),

Trabalhos         | Nodo_eh_externo(nodo)

2ºSemestre            |, Nodo_eh_raiz(nodo), Tamanho

O percurso de uma árvore é a maneira ordenada de percorrer todos os nodos da árvore (percorrer todos os seus nós, sem repetir nenhum e sem deixar de passar por nenhum). É utilizada, por exemplo, para consultar ou alterar as informações contidas nos nós.

Percurso Prefixo

Um nodo é visitado antes de seus descendentes.

Exemplo de aplicação: Imprimir um documento estruturado.

Percurso Pós-fixo

Um nodo é visitado após seus descendentes.

Aplicação: Calcular o espaço ocupado por arquivos em pastas e subpastas.

Métodos de Árvore Binária

Filho_da_esquerda(nodo), Filho_da_direita(nodo), Irmão(nodo):

Uma árvore binária é uma árvore ordenada na qual todo nodo tem, no máximo, dois filhos. Uma árvore binária imprópria possui apenas 1 filho.

Caminhamento Interfixado

Da esquerda para a direita.

Caminhamento de Euler

Um passeio ao redor de T.

Árvores Binárias de Busca

Árvore de pesquisa binária: todo nó interno contém um registro.

• Se a resposta da questão for "é menor", então a pesquisa continua na subárvore esquerda.
• Se a resposta for "é igual", então a pesquisa terminou com sucesso.
• Se a resposta for "é maior", então a pesquisa continua na subárvore direita.
• Se encontrarmos um nodo externo (que é vazio), então a pesquisa terminou sem sucesso.

Observe que o tempo de execução da pesquisa em uma árvore binária de pesquisa T é proporcional à altura de T.

Remoção de um nodo da árvore binária de pesquisa

Ordenação

Bubble Sort

No melhor caso (N), pior caso (n²). A complexidade desse algoritmo é de ordem quadrática. Não é recomendado para grandes volumes de dados.

(7 5 9 3 2 Início) 5 7 3 2 5 3 2 7 9 2i) 3 2 2 3 5 7 9 4i)

Quicksort

Médio e melhor caso (n Log₂ n) e no pior caso O(n²).

Pesquisa Binária

(Tem que estar ordenado antes) O(Log n) Ω(1) Θ(n)

1-3-7-9-15-17-21-65-80-99 Procure o 80.

Meio 15, 80 é maior então 17-21-65-80-99 meio 65, 80 é maior então 80-99 meio 80, achou o 80.

Arredonde Para Cima

Grafos

Um grafo é um conjunto de pontos. Se todas as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo dirigido, dígrafo ou grafo orientado. Se todas as arestas em um grafo forem não-dirigidas, então dizemos que o grafo é um grafo não-dirigido. Um grafo que tem arestas não-dirigidas e dirigidas é chamado de grafo misto.

• Grau: número de arestas ligadas a um vértice.
• Grau de entrada: número de setas que chegam em um vértice X, in(X).
• Grau de saída: número de setas que saem de um vértice X, out(X).
• Fonte: todo vértice, cujo grau de entrada é 0 (zero).
• Sumidouro (poço): todo vértice, cujo grau de saída é 0 (zero).

----------- > Aresta

O > Vértice