Upload
cristiano-pires-martins
View
757
Download
5
Embed Size (px)
DESCRIPTION
Aula 08 - árvores
Citation preview
ÁrvoresCristiano Pires Martins
O jardineiro é jizus e as árveres somos nozes
Introdução• As árvores são uma das estrutura de
dados mais importantes da área da computação;
• É utilizada em muitas aplicações do mundo real;
• Os relacionamentos lógicos entre os dados representam alguma dependência de hierarquia ou composição entre os nodos;
• Exite uma hierarquia de subordinação.
Conceitos Básicos
• As linhas que unem 2 nodos representam os relacionamentos lógicos e as dependências de subordinação existentes entre eles;
• A se relaciona somente com B, C e D e não com os demais;
• B se relaciona somente com A e E.
A
GFE
DCB
H
I J
Conceitos Básicos
• Relacionamentos de subordinação, formando hierarquias, podem apresentar diferentes significados:
• Hierarquias de especialização: representa classes e subclasses;
• Hierarquias de composição: o nodo é composto por partes;
• Hierarquias de dependência: representa um organograma.
Hierarquia de Especialização
Veículo
MotoCarroHelicópteroAvião
Aéreo Terrestre Aquático
Motor Vela Remo
Navio Iate Lancha
Hierarquia de Composição
Carro
Chassis Motor Rodas
Hierarquia de Dependência
DiretorSuperintendente
Diretor Administrativo
Diretor FábricaDiretor
Comercial
DepartamentoCont. Qualidade
Departamento Manutenção
Departamento Produção
A
GFE
DCB
H
I J
Representação Gráfica de uma Árvore
Terminologia
• A terminologia não é padronizada;
• Existem nomes diferentes para os mesmos conceitos em diferentes publicações.
Terminologia• Raiz:
• Todos os outros nós da árvore são subordinados a ele;
• O acesso a todos os nós é sempre a partir dele.
• Nós descendentes:
• Relação de dependência com o nó mais acima.
Raiz
Nós descendentes
Terminologia
• Subárvore:
• Conjunto de nós, sendo todos subordinados a um único nó, externo a esta subárvore.
Subárvores
Terminologia• Grau de Um Nó:
• Número de Subárvores que são subordinadas diretamente a esse nó.
• Grau de uma Árvore:
• É o maior valor dentre os graus de todos os seus nós.
Grau de um Nó
Terminologia• Folha ou Terminal (externo): são os nós de
grau zero.
• Nó de derivação (interno): nós de grau maior do que zero e que apresentam uma subárvore.
Folha
Nó de Derivação
Terminologia• Nível de um Nó:
número de ligações entre este nó e a raiz da árvore mais um.
• Caminho: sequência de nós consecutivos distintos entre dois nós.
• Comprimento do Caminho: Número de níveis entre os dois nós menos um.
Caminho
Nível 1
Nível 2
Nível 3
Nível 4
Comprimento = 3
Terminologia
• Altura ou Profundidade: é o número de nós do maior caminho deste nó até um de seus descendentes - folha;
• A altura de uma árvore é igual ao maior nível de seus nós;
• Todos os nós folha tem altura 1.
Terminologia
• Floresta: conjunto de zero ou mais árvores disjuntas.
• Árvore ordenada: quando a ordem de suas subárvores é relevante para a aplicação que está sendo representada através desta estrutura de dados.
Terminologia
Floresta Árvores Ordenadas
CB
A
BC
A≠
Terminologia
• Árvore binária: quando apresentar no máximo grau 2 em cada nó;
• Árvore n-ária: quando apresentar no máximo grau n em cada nó.
Terminologia
• Árvores isomorfas: quando é possível que se tornem coincidentes através de uma permutação na ordem das subárvores de seus nós.
• Árvores balanceadas: é aquela na qual existe uma distribuição equilibrada entre os nós da árvore, ou seja, existe uma diferença mínima entre todas as folhas e a raiz.
• Uma árvore cheia ou completamente balanceada é aquela em que todas as folhas estão a uma distância igual da raiz.
Terminologia
• Caso o número de nós seja diferente de zero, existe sempre uma raiz;
• Caso o número de nós seja zero, é denominada vazia.
Operações Básicas
• Criação de uma árvore;
• Alocação das variáveis necessárias para a definição da árvore;
• As demais operações são habilitadas depois disso.
• Inserção de um novo nó:
• Como raiz;
• Como folha;
• Como uma posição intermediária.
Operações Básicas
• Exclusão de um Nó:
• Quando não se realiza sobre uma folha, precisa reorganizar a árvore.
• Acesso a um Nó;
• Destruição de uma árvore.
Outras Operações
• Pai: dado um determinado nó, retorna o endereço do nó imediatamente superior;
• Tamanho: retorna o número total de nós de uma árvore;
• Altura: retorna a altura da árvore.
Árvores Usando Contiguidade Física
• Não é intuitiva como era no caso das Listas Lineares;
A
E
DCB
GF IH
A(3) B(1) C(0) D(4) E(0) F(0) G(0) H(0) I(0)
A(3) B(1) E(0) C(0) D(4) F(0) G(0) H(0) I(0)
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
ImplementaçõesA
E
DCB
GF IH
A(3) B(1) C(0) D(4) E(0) F(0) G(0) H(0) I(0)
A(3) B(1) E(0) C(0) D(4) F(0) G(0) H(0) I(0)
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
Por Níveis
Por Profundidade
Desvantagens Usando Contiguidade Física
• Implementação não constitui uma boa representação física de árvores;
• Dificuldade de seguir a hierarquia implícita nestas estruturas ao manipular a árvore;
• Inserção e Remoção demorada;
Vantagens Usando Contiguidade Física
• É eficiente em termos de espaço ocupado, principalmente quando o grau não varia muito;
• Implementação é mais simples se existir limitação do número de descendentes.
Árvore Ternária Usando Contiguidade Física
A
E
DCB
F G
A B C D λ E λ λ λ λ λ F G ...
1 2 3 4 5 6 7 8 9 10 11 12 13
Árvores Implementadas por Encadeamento
• O acesso se dá sempre pela raiz;
• Os demais nós são alcançados somente pelos endereços dos elos;
• A hierarquia de subordinação, implícita nas árvores, fica perfeitamente representada.
• Todos os nós da árvore deve apresentar a mesma estrutura.
Árvore Implementada Através de Encadeamento
A
E
DCB
F G
A
C / / /B / / D /
F / / /E / / / G / / /
Vantagens da Implementação por Encadeamento
• É bastante Intuitiva;
• Inserção e Remoção são simples, constituindo basicamente na atualização de endereços nos campos de elo de alguns nós.
Desvantagens da Implementação por Encadeamento
• Árvores cujos nós têm grau variado apresentam geralmente muitos campos de elo ociosos;
• O Acesso aos nós pode ser dificultado devido à necessidade de acessar qualquer nós sempre através da raiz.
Exercício• Considere a árvore com representação aninhada a
seguir:
( A ( B ) ( C ( F ( H ) ( I ) )) ( D) ( E ( G ) ) )
• Represente a mesma árvore através de:
• Diagrama de Inclusão;
• Diagrama de barras;
• Numeração por níveis;
• Monte a árvore na grafia convencional.
A
ECB
F G
D
IH
Exercício
• Represente a mesma árvore através de:
• Diagrama de Inclusão;
• Diagrama de barras;
• Numeração por níveis;
• Representação aninhada.
A
ECB
F G
D
IH
Exercício• Para a árvore ao lado, responda às
perguntas a seguir:
• Quantas subárvores esta árvore contém?
• Quais os nós-folha?
• Qual o grau de cada nó?
• Qual o grau da árvore?
• Liste os ancestrais dos nós B, G e I.
• Liste os nós de quem C é ancestral próprio.
• Liste os nós de quem D é descendente próprio.
• Dê o nível e a altura do nó F e A.
• Qual a altura da árvore?
A
ECB
F G
D
IH
Resposta• Quantas subárvores esta árvore contém? 4
• Quais os nós-folha? B, D, G, H e I
• Qual o grau de cada nó?
• A=4,B=0,C=1,D=0,E=1,F=2,G=0,H=0 e I=0
• Qual o grau da árvore? 4
• Liste os ancestrais dos nós B, G e I.
• B=A; G=A e E; I=A, C e F
• Liste os nós de quem F é ancestral próprio. H e I
• Liste o nó de quem D é descendente próprio. A
• Dê o nível e a altura do nó F e A.
• F: Nível 3 e Altura 2 A: Nível 1 e Altura 4
• Qual a altura da árvore? 4 (maior caminho)
A
ECB
F G
D
IH
A
ECB
G I
D
ML O
RQ
F
KJ
P
TS
H
N
Exercício
• Para a árvore ao lado, responda às perguntas a seguir:
• Quantas subárvores o nó G contém?
• Quais os nós-folha?
• Qual o grau de cada nó?
• Qual o grau da árvore?
• Liste os ancestrais dos nós L, Q e U.
• Liste os nós de quem P é ancestral próprio.
• Liste os nós de quem G é descendente próprio.
• Dê o nível e a altura do nó J, G, S, O e A.
• Qual a altura da árvore?
U