Baixe Estrutura de Dados - Arvores e outras Notas de estudo em PDF para Informática, somente na Docsity! ÁRVORES ÁRVORES BINÁRIAS ÁRVORES ALINHADAS ÁRVORES BINÁRIAS DE BUSCA HEAP BINÁRIO ÁRVORES AVL ESTRUTURAS DE DADOS Professor: Cláudio Carvalho Á R V O R E S Motivação Definição Representação Alocação Exemplos Principais Conceitos  Caminho  Altura, Nível e Grau de um nó  Árvore ordenada  Árvores isomorfas  Árvore cheia Exemplos árvore vazia (a) (b) (c) (d) (e) (f) (g) As figuras (a), (b), (c), (d), (e) e (f) são árvores. Já a figura (g) não é uma árvore, pois existe um nó com mais de um pai Árvores – Teoria geral Representação hierárquica a b e d gf h c (a (b (e)) (c) (d (f (h)) (g))) parênteses aninhados a d c f g h b e diagramas de inclusão alinhament o dos nós (barras) a b e c d f h g Árvores – Teoria geral Alocação ADJACÊNCIA (ALOCAÇÃO ESTÁTICA)  Nesta modalidade, os nós da árvore são representados de forma sequencial na memória.  Os números que aparecem à direita da informação de cada nó indicam o grau do nó correspondente.  Não é conveniente para representar árvores, na maioria dos casos, devido às dificuldades que oferece para a manipulação da estrutura (inserções, remoções, busca etc). Árvores – Teoria geral a b d fe c a 3 b 0 c 0 d 2 e 0 f 0 Alocação sequencial da árvore ao lado. Aplicações Tabela de jogos da copa do mundo de futebol de 2006 Árvores – Teoria geral Aplicações Generalização / EspecializaçãoÁrvore de diretórios C:\ Documentos Apostilas Exercícios Provas Fotos Pessoais Paisagens Musicas MPB Pop Rock Eletrônica Artista 01 Artista 02 Árvores – Teoria geral Aplicações * + ba - /c ed (a + b) * (c – d / e) a + b * (c – d) / e + a / e* -b dc Árvores de Expressões Árvores – Teoria geral Conceitos NÍVEL:  O nível, ou profundidade, de um nó vi é o comprimento do caminho da raiz até o nó em questão.  Se vi é a raiz da árvore, seu nível é 0.  Formalmente definindo, o nível de vi é 0, se vi é a raiz da árvore. Caso contrário, o nível de vi é 1 + n, onde n é o nível do pai de vi. EXEMPLO: Na árvore ao lado: • o nível do nó a é 0. • o nível dos nós b, c e d é 1. • o nível do nó h é 3. a b e d gf h c OBSERVAÇÕES: Para alguns autores, o nível é contado pela quantidade de nós visitados da raiz até o nó em questão. Neste caso, o nível da raiz é 1. nível 0 nível 1 nível 2 nível 3 Árvores – Teoria geral Conceitos GRAU:  O grau de saída, ou apenas grau, de um nó vi é a quantidade de filhos dele.  O grau de uma árvore é o maior valor de grau de seus vértices. EXEMPLO: Na árvore ao lado: • o grau do nó a é 3. • o grau do nó h é 0. • o grau da árvore é 3. a b e d gf h c OBSERVAÇÕES: Não convém falar em grau de entrada de um vértice em árvore, uma vez que este é sempre 1 para todos os vértices; com exceção do raiz, que tem grau de entrada 0. Portanto, quando se fala em grau de um vértice, deve-se considerar o grau de saída deste. Árvores – Teoria geral Conceitos Calcule o grau, nível e altura de cada um dos vértices da árvore a seguir: a b e d gf h c VÉRTICE GRAU NÍVEL ALTURA a 3 0 3 b 1 1 1 c 0 1 0 d 2 1 2 e 0 2 0 f 1 2 1 g 0 2 0 h 0 3 0 Árvores – Teoria geral Conceitos ÁRVORE CHEIA:  Uma árvore de grau g está cheia se todos os seus nós não terminais estão com o número máximo (g) de filhos, e se as folhas estão no mesmo nível.  Uma árvore de grau g está cheia se todos os seus níveis estão com a quantidade máxima de nós.  A quantidade máxima de nós de um nível n de uma árvore de grau g é gn.  Uma árvore de grau g e altura h tem no máximo (gh+1 – 1) / (g - 1) nós. Árvores – Teoria geral (b)(a) Conceitos SUBÁRVORE E SUBÁRVORE PARCIAL:  Seja T uma árvore, e v um nó de T. Seja Tv a subárvore de T de raiz v. Seja S um conjunto de elementos de Tv. T’ = Tv – S é uma subárvore parcial de T.  Observe que a diferença entre uma subárvore de raiz v e uma subárvore parcial de raiz v é que a primeira contém obrigatoriamente todos os descendentes de v; enquanto que a segunda, não necessariamente. Árvores – Teoria geral a b c (a) d f e g b (b) d f b d (c) EXEMPLO: •A árvore (b) é uma subárvore da árvore (a). •A árvore (c) é uma subárvore parcial da árvore (a). Á R V O R E S B IN Á R IA S Definição  Árvore binária  Árvore estritamente binária  Árvore completa  Altura máxima e mínima Representação Alocação Percurso  Largura  Profundidade Conversão para árvore binária Definição ALTURA MÁXIMA E MÍNIMA:  A altura h de uma árvore binária com n nós está entre o valor de log2n como inteiro, arredondado para menos, e o valor de n. Logo:  log2n ≤ h ≤ n - 1.  O pior caso acontece com as árvores degeneradas ou ziguezagues.  O melhor caso acontece com a árvore completa. Árvores Binárias (d)(a) (b) (c) OBSERVAÇÕES: •As árvores (a), (b) e (c) são chamadas de ziguezague. •As árvores (b) e (c) podem ser ainda chamadas de degeneradas à esquerda e à direita, respectivamente. •A altura de (a) é máxima 6 – 1 = 5. •A altura de (d) é mínima. log210 = 3.3219 = 3. Representação Árvores Binárias hierárquica a b d c fe g (a (b (d ()()) ()) (c (e (g () ()) ()) (f () ()))) parênteses aninhados OBSERVAÇÕES: •Não é comum representar árvores binárias utilizando parênteses aninhados; uma vez que devem ser indicadas todas as subárvores de todos os nós (ainda que vazias). Nesta representação, o primeiro par de parênteses que segue uma chave de nó representa a subárvore esquerda deste; e o par de parênteses seguinte representa a subárvore direita. Alocação Árvores Binárias DINÂMICA:  Cada nó possui um campo para guardar sua informação (chave) k, e campos de referência para suas subárvores direita e esquerda. ESTÁTICA:  Não indicada, pois requer alocação de espaço considerando uma árvore cheia (já que deve ser alocado espaço para todas as possíveis subárvores).  Os filhos de um nó i ficam nas posições 2i (esquerdo) e 2i + 1 (direito).  Se um nó é folha, ele deve estar no último nível, ou seus filhos estão vazios. k1 k2 k3 k4 k5 1 2 3 ... n k Percurso - Extensão Árvores Binárias  Consiste em visitar cada nó começando do nível mais baixo (ou mais alto) e movendo para baixo (ou para cima) nível a nível, visitando nós em cada nível da esquerda para a direita (ou da direita para esquerda).  Neste caso, já quatro situações distintas: I. De cima para baixo, da esquerda para a direita (mais utilizado). II. De cima para baixo, da direita para esquerda. III. De baixo para cima, da esquerda para a direita. IV. De baixo para cima, da direita para a esquerda.  Vejamos os percursos na árvore a seguir: I. a b c II. a c b III. b c a IV. c b a a b c Percurso - Extensão Árvores Binárias DE CIMA PARA BAIXO, DA DIREITA PARA A ESQUERDA:  Inicialmente, o nó raiz é colocado numa fila de nós.  Enquanto houver elementos na fila:  Retirar e listar o nó que está na cabeça da fila  Enfileirar os filhos do nó que foi retirado da fila. Fila Listagem a b c a c a b d e a b c e a b c d a b c d e a b c d e Percurso - Profundidade Árvores Binárias  Consiste basicamente em três tarefas:. I. V – Visitar um nó (e listar o seu valor). II. L – Percorrer a subárvore da esquerda (left). III. R – Percorrer a subárvore da direita (right).  Estas três tarefas podem estar organizadas de 6 formas distintas (3!): I. VLR  a b c II. RLV  c b a III. LVR  b a c IV. RVL  c a b V. LRV  b c a VI. VRL  a c b  Os percursos I, III e V são os mais conhecidos. São percursos em que os movimentos são sempre da esquerda para a direita. Seus nomes são, respectivamente, pre-order, in-order e pos-order. a b c Conversão para árvore binária Árvores Binárias  Uma árvore com grau maior que 2 pode ser transformada em binária, se ligarmos os nós irmãos e removermos a ligação entre um nó pai e os nós filhos, exceto as do primeiro filho.  Se um nó tem n filhos, para i de 2 até n, o nó i passa a ser visto como filho direito do seu irmão i-1.  Tomemos como exemplo a árvore a seguir: a b e d gf c a b e d gf c a b e d g f c OBSERVAÇÕES: Para se interpretar corretamente a hierarquia de uma árvore transformada, é preciso ter em mente a transformação havida. Assim, a subárvore esquerda de um nó é seu filho realmente, enquanto que a direita é seu irmão. Á R V O R E S A L IN H A D A S Motivação Definição Representação Alocação Custo de Manutenção Motivação  Examinando-se a representação de uma árvore binária, pode-se constatar a existência de muitas referências (para subárvores) nulas nos nós.  De fato, é fácil verificar que em uma árvore binária de n nós, ocorrem n+1 referências nulas. A árvore a seguir possui 5 nós e 6 referências nulas:  O principal motivo de se ter uma árvore binária alinhada (ou costurada) é a utilização das referências nulas, para facilitar o caminhamento sobre a árvore. Árvores Alinhadas a b c d e Alocação  São utilizados dois campos adicionais (do tipo booleano) ao da árvore binária convencional, indicando se as referencias esquerda e direita são filhos (1) ou “costuras” (0).  No exemplo a seguir temos a representação de uma árvore binária costurada em pre-order, e a representação da sua alocação. Árvores Alinhadas 4 2 6 1 53 41 1 21 1 61 0 10 0 30 0 50 0 T Custo de Manutenção  O custo de manutenção de tais árvores é alto, considerando que após cada operação de inserção ou remoção de nós as costuras devem ser ajustadas.  Considerando que o percurso em árvores é geralmente para listar os nós da esquerda para a direita, pode-se desconsiderar as amarras à esquerda. Neste caso, teríamos uma árvore costurada (no percurso adotado) à direita.  Neste caso, apenas os sucessores seriam interessantes para serem utilizados nas “amarras” ou “costuras”.  No exemplo, temos uma árvore binária alinhada em pre-order à direita. Árvores Alinhadas 4 2 6 1 53 Á R V O R E S B IN Á R IA S D E B U S C A Definição Busca Inserção Remoção  Por cópia  Por fusão Exercícios TAD Busca Fluxograma para localização de uma chave em uma árvore binária de busca: Considere: K = chave do nó atual X = chave procurada Árvores Binárias de Busca Ir para a raiz Vazia? Chave não encontrada X = K? Ir para a subárvore esquerda X < K? Ir para a subárvore direita Chave encontrada S S N N S N Inserção Para inserir uma chave X em uma árvore binária de busca, segue-se um processo semelhante ao de busca. Se a árvore estiver vazia, inserir a chave na raiz. Se a chave X for menor que a chave do nó corrente, inserir X na subárvore esquerda deste. Se a chave X for maior que a chave do nó corrente, inserir X na subárvore direita deste. Todo nó é inserido nas folhas da árvore. Árvores Binárias de Busca 4 2 7 1 5 83 EXEMPLO: Para inserir a chave 6 na árvore ao lado. O nó corrente é a raiz. •6 é maior que 4. Inserir na subárvore direita. •6 é menor que 7. Inserir na subárvore da esquerda. •6 é maior que 5. Inserir na subárvore da direita. •A subárvore está vazia. 6 deve ser a raiz desta. 6 Remoção A complexidade deste processo é proporcional à quantidade de filhos (subárvores) que o nó a ser removido tem. Desta forma, existem três casos. Se o nó não possui filhos, ele é removido e o ponteiro de seu ascendente imediato (pai) é atualizado para nulo. Se o nó possui apenas um filho, ele é removido e o ponteiro de seu ascendente imediato (pai) é atualizado para o seu filho. Se o nó possui os dois filhos, o processo de remoção pode se dar basicamente de duas formas:  Por fusão  Por cópia Árvores Binárias de Busca Remoção CASO III (FUSÃO): Na subárvore esquerda (direita) do nó V a ser deletado, localizar o nó X mais à direita (esquerda). X passa a ser pai da subárvore direita (esquerda) de V. A raiz da subárvore esquerda (direita) de V assume o lugar dele. Em seguida, o nó V é removido. EX.: Remover o nó que contém a chave 4 da árvore abaixo: Árvores Binárias de Busca 4 2 6 1 5 73 2 1 3 6 5 7 Remoção CASO III (CÓPIA): Na subárvore esquerda (direita) do nó V a ser deletado, localizar o nó X mais à direita (esquerda). A chave de X é copiada para V. O nó X é então removido da árvore seguindo um dos dois primeiros casos, dependendo do seu número de filhos (subárvores). EX.: Remover o nó que contém a chave 4 da árvore abaixo: Árvores Binárias de Busca 4 2 6 1 5 73 3 2 6 1 5 7 Exercícios a. Inserir em uma árvore binária de busca, na ordem em que aparecem, as seguintes chaves: 5 8 6 7 2 4 3 1 5 6 2 3. b. Listar os nós da árvore do item a em extensão (de cima para baixo e da esquerda para a direita). c. Listar os nós da árvore do item a em pre-order, pos-order e in-order. d. Apagar, da árvore do item a, a chave 5, por fusão. e. Apagar, da árvore do item a, a chave 5, por cópia. Árvores Binárias de Busca