Arvore-Estrutura-de-Dados-Conceitos-e-Aplicacoes

ESTRUTURA DE DADOS II 60 HORAS PROF JULIANO RATUSZNEI EMAIL JULIANORATUSZNEIUNICIDEDUBR ESTRUTURA DE DADO ÁRVORE Introdução à Estrutura de Dado Árvore Definições e terminologias Aplicações Representação computacional 2 ÁRVORE Árvores são estruturas de dados hierárquicas Basicamente árvores são formadas por um conjunto de elementos os quais chamamos nodos ou vértices conectados de forma específica por um conjunto de arestas Nível 0 é a raiz da árvore e está no topo da hierarquia Outros nodos estão conectados ao nodo raiz e aos demais nodos 3 ÁRVORE ÁRVORE 5 As conexões entre os nodos de uma árvore seguem uma nomenclatura genealógica Um nodo em um dado nível está conectado a seus filhos no nível abaixo e a seu pai no nível acima A raiz da árvore que está no nível 0 possui filhos mas não possui pai ÁRVORE Relacionamento Lógico Hierarquia ou Subordinação Onde Um subconjunto dos componentes é subordinado a outro 6 ÁRVORE Utilização de Arvores ONDE Na Computação 7 ÁRVORE Pasta do Explorer Histórico da WEB Rotas de um trajeto Logístico Chaves de Jogos de times de futebol Entre outros 8 9 ÁRVORES Arvore de Grau N Decisão para jogar Tênis ÁRVORES Arvores de derivação de equações matemáticas e suas prioridades abcde 10 ÁRVORES ORDENAÇÃO DE VALORES 12 ÁRVORES Diagramação de inclusão A B D C 13 ÁRVORES Diagrama de barras A B C D ÁRVORES Níveis 1A 11B 111D 12C Aninhamento ABDC 15 ÁRVORE DEFINIÇÃO Conjunto finito T de zero ou mais nós nodos ou vértices tal que Se número de nós é maior do que zero existe um nó denominado raiz da árvore denotado por rT os demais nós formam m 0 conjuntos disjuntos S1 S2 Sm onde cada um destes é uma árvore Si são denominadas subárvores Se número de nós é igual a zero árvore vazia A é a raiz A B C D ÁRVORES RAÍZES Raiz Subárvores de A 17 ÁRVORES Pai X Irmão Filho Usando X como referência Antecessor Sucessor ÁRVORES Se x pertence à subárvore enraizada em v x é descendente de v v é ancestral de x Se x é diferente de v x é descendente próprio de v e v é ancestral próprio de x Um nó folha não possui descendentes próprios 18 19 ÁRVORES GRAU DE UM NÓ Grau ou grau de saída número de subárvores do nó ou número de filhos de um nó 20 ÁRVORE GRAU DA ÁRVORE Grau de uma árvore máximo entre os graus de seus nós ÁRVORE NÓ Nó interno ou nó de derivação nó com grau maior do que zero 21 ÁRVORE NÓ Nó folha nó terminal ou externo nó com grau igual a zero 22 23 ÁRVORE CAMINHO Um caminho é uma sequência de nós consecutivos distintos entre dois nós v1 alcança vk vk é alcançado por v1 24 ÁRVORE CAMINHO Comprimento do caminho Número de ligações entre os nós do caminho Comprimento do caminho 3 Número de arestas ÁRVORE NÍVEL NÍVEL NÚMERO DE LIGAÇÕES ENTRE A RAIZ E O NÓ ACRESCIDO DE UMA UNIDADE 25 ÁRVORES Altura profundidade de um nó número de ligações entre o nó e o nó folha descendente dele de maior nível acrescido de uma unidade Altura de nó folha é 1 26 ÁRVORES 27 Altura profundidade da árvore maior nível dentre seus nós ALTURA VS NÍVEL ÁRVORES Nível 1 Nível 2 Nível 3 Nível 4 Altura 4 Altura 3 Altura 2 Altura 1 29 ÁRVORES Árvore ordenada Ordem das subárvores é relevante Uma árvore ordenada é aquela na qual os filhos estão ordenados Assumese que essa ordenação se desenvolva da esquerda para a direita 30 ÁRVORES Duas árvores são isomorfas quando puderem se tornar coincidentes pela permutação da ordem das subárvores 31 ÁRVORES Floresta Conjunto de árvores SÃO TANTAS ÁRVORES QUE EU NÃO SEI SE ESTUDO COMPUTAÇÃO OU ENGENHARIA AMBIENTAL