Módulo_-_Árvores

Prévia do material em texto

Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvores
Escola de Ciência e Tecnologia
Capítulo 7 – Estruturas de 
Disciplina: ESTRUTURA DE DADOS II
Árvores
1
Capítulo 7 – Estruturas de 
dados do tipo árvore
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
Introdução:
– Árvores são estruturas de dados extremamente 
úteis em muitas aplicações computacionais, 
principalmente por:
Disciplina: ESTRUTURA DE DADOS II
principalmente por:
• Suportar relações hierárquicas.
• Permitir diversos métodos de busca.
• Ter seus algoritmos de manipulação facilmente 
construídos de forma recursiva.
2
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
Definição básica:
– Uma árvore é formada por um conjunto finito T
de elementos denominados vértices ou nós 
interligados por arestas
Disciplina: ESTRUTURA DE DADOS II
interligados por arestas
• Se T = 0, a árvore é vazia
• Se T ≥ 1, temos um nó especial chamado raiz da 
árvore, representado pela notação r.
3
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
Representação gráfica:
• A forma convencional de representar uma árvore está 
indicado na figura abaixo:
Nó da árvore, em especial raiz.
Disciplina: ESTRUTURA DE DADOS II 4
Nó da árvore, em especial raiz.
Aresta da árvore
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
• Os elementos restantes da raiz r, são
particionados em m ≥ 1 conjuntos distintos não
vazios, as subárvores de r, sendo cada um destes
conjuntos por sua vez uma árvore.
Disciplina: ESTRUTURA DE DADOS II
conjuntos por sua vez uma árvore.
5
r Raiz
1 2 3 m. . .
Sub-Árvores
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
• Se n é um nó da árvore T então T
n
indica 
uma subárvore de T com raiz no nó n.
Disciplina: ESTRUTURA DE DADOS II
TE está representado ao lado 
com seus nós em verde.
6
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
• Os conjuntos das subárvores tem de ser disjuntos, 
isto é, uma sub-árvore não pode possuir 
ramificação para outra sub-árvore.
Disciplina: ESTRUTURA DE DADOS II
A estrutura ao lado não é uma 
árvore, pois não tem todas 
os conjuntos de sub-árvores 
disjuntos. 
7
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
• A subárvore da esquerda do nó A tem raiz em B e a 
subárvore da direita tem raiz em C, isto está 
indicado pelos dois ramos saindo de A. 
Disciplina: ESTRUTURA DE DADOS II 8
A ausência de um ramo na árvore 
indica uma subárvore vazia, como 
a subárvore da direita do nó B.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
• Os nós n1, n2, ..., nk das subárvores de Tn são
chamados de filhos de n e n é o pai destes nós, que
são nós irmãos.
Disciplina: ESTRUTURA DE DADOS II
Considerando TE
� H e I são filhos de E
� H e I são irmão entre si
� E é pai de H e I
9
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
• Nós sem filhos como os nós D, H, I, F e G são 
chamados de folhas.
Nó raiz
Disciplina: ESTRUTURA DE DADOS II 10
Nó raiz
Nó simples
Nó folha
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
• O número de filhos de um nó é chamado de grau 
de saída deste nó. 
Disciplina: ESTRUTURA DE DADOS II
Por exemplo:
� O nó C tem grau de saída 3
� O nó E tem grau de saída 2
11
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
• Se o nó n é a raiz de uma subárvore Tn e n1
pertence a Tn então n1 é descendente de n e n
ancestral de n1.
Disciplina: ESTRUTURA DE DADOS II
Por exemplo:
Considerando TC, temos que H 
pertence a TC. 
Então H é descendente de C e C 
ancestral de H
Portanto nós sem descendentes próprios é uma folha
12
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
• Um caminho da árvore é composto por uma
sequência de nós consecutivos (n1, n2, ..., nk-1, nk)
tal que existe sempre a relação ni é pai de ni+1.
Disciplina: ESTRUTURA DE DADOS II 13
Exemplo:
Caminho A, B e D
� A é pai de B
� B é pai de D
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
• Os k vértices formam k-1 pares e um caminho de 
comprimento igual a k-1.
Disciplina: ESTRUTURA DE DADOS II 14
O comprimento do 
caminho entre o nó A e o 
nó D é 2. 
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
• O nível de um nó n pode ser definido do 
seguinte modo:
– o nó raiz tem nível 0, 
Disciplina: ESTRUTURA DE DADOS II
– os outros nós tem um nível que é maior uma 
unidade que o nível de seu pai. 
15
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
Na árvore da figura ao lado temos nós nos 
seguintes níveis: 
Nível 0 = A
Disciplina: ESTRUTURA DE DADOS II 16
Nível 0 = A
Nível 1 = B, C
Nível 2 = D, E, F, G
Nível 3 = H, I
0
1
2
3
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
Representação gráfica alternativa:
– Existem diversas maneiras de representar 
árvores.
Disciplina: ESTRUTURA DE DADOS II 17
� Conceito de conjuntos � Diagrama de barras
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
• Uma outra forma interessante de representar uma
árvore é a representação por parênteses
aninhados.
• representa uma árvore no plano, em uma linha
Disciplina: ESTRUTURA DE DADOS II
• representa uma árvore no plano, em uma linha
• O rótulo do nó é inserido à esquerda do abre 
parênteses correspondente.
18
(A (B(D))(C(E(H)(I))(F)(G)))Representação da árvore exemplo :
Pode representar uma expressão aritmética.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
• Para colocarmos uma expressão em forma de 
árvore devemos considerar
– cada operador como um nó da árvore
– e os seus operandos como as duas subárvores.
Disciplina: ESTRUTURA DE DADOS II
– e os seus operandos como as duas subárvores.
Exemplo:
A + (B-C)*D%(E*F) , adicionando todos os parênteses
(A + ((B-C)*(D%(E*F))))
19
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
• (A + ((B-C)*(D%(E*F))))
Representação em 
Disciplina: ESTRUTURA DE DADOS II 20
Representação em 
árvore da expressão 
aritmética.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Disciplina: ESTRUTURA DE DADOS II
TIPOS DE ÁRVORES
21
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore
Tipos de árvores:
• Com objetivo de fazer uso de determinas
características específicas, foram criadas vários
tipos de árvores, veremos alguns desses tipos.
Disciplina: ESTRUTURA DE DADOS II
tipos de árvores, veremos alguns desses tipos.
– Árvore binária
– Árvore rubro negra
– Árvore b-tree
22
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Disciplina: ESTRUTURA DE DADOS II
ÁRVORE BINÁRIA
23
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Formalmente uma árvore binária pode ser definida como
um conjunto finito de nós, que é vazio, ou consiste de um
nó raiz e dois conjuntos disjuntos de nós, a subárvore
esquerda e a subárvore direita.
Disciplina: ESTRUTURA DE DADOS II 24
n
E D
n
D
n
E
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
Em uma árvore binária:
• cada nó tem no máximo duas subárvores,
• quando há somente uma presente é necessário
distinguir entre subárvore esquerda e direita.
Disciplina: ESTRUTURA DE DADOS II
distinguir entre subárvore esquerda e direita.
• Árvores binárias podem ser vistas em diversas
situações do cotidiano
• Copa do Brasil
25
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• É importante observar que uma árvore binária não
é um caso especial de árvore e sim um conceito
completamente diferente, devido a relevância da
posição dos nós – direito e esquerdo.
Disciplina: ESTRUTURA DE DADOS II
posição dos nós – direito e esquerdo.
26
As duas árvores ao lados são 
idênticas no conceito de árvores, 
mas são árvores binárias distintas. 
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
Toda árvore binária possui:
• Todos os nós de uma sub-árvore direita são 
maiores que o nó raiz. 
• Todos os nós de uma sub-árvore esquerda são 
Disciplina: ESTRUTURA DE DADOS II
• Todos os nós deuma sub-árvore esquerda são 
menores que o nó raiz.
• Cada sub-árvore é também uma árvore binária
– Todo nó tem grau menor ou igual 2
27
Número de filhos de um nó
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
– Na árvore binária, o grau máximo de um nó é 2.
– O grau de uma árvore é igual ao máximo dos 
graus de todos os seus nós.
• Uma árvore binária tem grau máximo igual a 2.
Disciplina: ESTRUTURA DE DADOS II
• Uma árvore binária tem grau máximo igual a 2.
28
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Uma árvore binária pode ser classificada
segundo a quantidade a disposição dos
filhos de seus nós em três tipos:
Disciplina: ESTRUTURA DE DADOS II
– Árvore Estritamente Binária
– Árvore binária Completa
– Árvore binária Cheia
29
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
Estritamente binária:
• Uma árvore estritamente binária 
é uma árvore binária em que cada
Disciplina: ESTRUTURA DE DADOS II
é uma árvore binária em que cada
nó tem 0 ou 2 filhos. 
– Número de nós = 2n−1, onde
n é o número de nós folha.
30
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Uma árvore completa é aquela em
se n é um nó com algumas de
subárvores vazias, então n se
Disciplina: ESTRUTURA DE DADOS II
subárvores vazias, então n se
localiza no penúltimo ou no último
nível.
31
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Uma árvore binária cheia é uma árvore em que se 
um nó tem alguma subárvore vazia então ele está 
no último nível.
Disciplina: ESTRUTURA DE DADOS II 32
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Disciplina: ESTRUTURA DE DADOS II
HIERARQUIA DOS NÓS EM ÁRVORE 
BINÁRIA
33
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
Nós ancestrais:
• Estão acima de um
nó e têm ligação
Disciplina: ESTRUTURA DE DADOS II
nó e têm ligação
direta ou indireta
com ele.
34
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
Nós descendentes:
• Estão abaixo de um nó e
possuem ligação direta
Disciplina: ESTRUTURA DE DADOS II
possuem ligação direta
ou indireta.
35
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
Descendentes esquerdo:
• Estão abaixo de um nó,
possuem ligação direta ou
Disciplina: ESTRUTURA DE DADOS II
possuem ligação direta ou
indireta e fazem parte da
sub-árvore esquerda.
36
São todos MENORES que no que descendem
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
Nós descendentes direito:
• Estão abaixo de um nó,
Disciplina: ESTRUTURA DE DADOS II
• Estão abaixo de um nó,
possuem ligação direta ou
indireta e fazem parte da
sub-árvore direita.
37
São todos MAIORES que no que descendem
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Altura ou profundidade da árvore:
– nível mais distante da raiz.
Disciplina: ESTRUTURA DE DADOS II 38
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Expressão que representa o número máximo de nós em
um nível da árvore binária = 2n, onde n é o nível em
questão.
Disciplina: ESTRUTURA DE DADOS II 39
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Disciplina: ESTRUTURA DE DADOS II
OPERAÇÕES EM ÁRVORE BINÁRIAS
40
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
Operações em árvore binária:
• Busca
• Inserção
Disciplina: ESTRUTURA DE DADOS II
• Inserção
• Remoção
Operações em uma árvore binária requerem comparações 
entre nós, com chamadas a um comparador
41
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
Operação de busca:
• Busca: A busca em uma árvore binária por um valor
específico pode ser um processo recursivo ou iterativo.
Disciplina: ESTRUTURA DE DADOS II
específico pode ser um processo recursivo ou iterativo.
42
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
Algoritmo de Busca:
• Começa examinando o nó raiz.
– Se a árvore está vazia, o valor procurado não pode existir na árvore.
Disciplina: ESTRUTURA DE DADOS II
– Caso contrário, se o valor é igual a raiz, a busca foi bem sucedida.
– Se o valor é menor do que a raiz, a busca segue pela sub-árvore
esquerda.
– Similarmente, se o valor é maior do que a raiz, a busca segue pela sub-
árvore direita.
43
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
Inserção:
• A inserção começa com uma busca, procurando pelo valor, mas
se não for encontrado, procuram-se as subárvores da esquerda
Disciplina: ESTRUTURA DE DADOS II
se não for encontrado, procuram-se as subárvores da esquerda
ou direita, como na busca.
• Eventualmente, alcança-se a folha, inserindo-se então o valor
nesta posição.
44
Ou seja, a raiz é examinada e introduz-se um nó novo na subárvore da esquerda 
se o valor novo for menor do que a raiz, ou na subárvore da direita se o valor novo 
for maior do que a raiz
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• A localização do “ponto de inserção” é semelhante à 
busca por um valor na árvore, este valor é o do nó que 
se deseja inserir. 
Disciplina: ESTRUTURA DE DADOS II
se deseja inserir. 
• Após a inserção do novo elemento, a árvore deve 
manter as suas propriedades características.
45
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
Exemplo de Inserção de nó em árvore binária
Disciplina: ESTRUTURA DE DADOS II 46
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
Exemplo de Inserção de nó em árvore binária
Disciplina: ESTRUTURA DE DADOS II 47
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
Exemplo de Inserção de nó em árvore binária
Disciplina: ESTRUTURA DE DADOS II 48
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Inserção
Disciplina: ESTRUTURA DE DADOS II 49
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Remoção
– Para remover um nó de uma árvore binária devemos 
considerar três casos:
Disciplina: ESTRUTURA DE DADOS II
considerar três casos:
1. Nó sem filhos, ou seja, uma folha.
2. Nó com um único filho.
3. Nó com dois filhos.
50
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Remoção
Nó sem filhos, ou seja, uma folha.
Disciplina: ESTRUTURA DE DADOS II 51
O caso de um nó sem filhos é o mais 
simples e significa apenas ajustar o 
ponteiro de seu pai.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Remoção: Nó sem filhos, ou seja, uma folha.
Disciplina: ESTRUTURA DE DADOS II 52
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Remoção
Nó com um único filho.
Disciplina: ESTRUTURA DE DADOS II 53
No caso do nó ter um único filho a mudança na 
árvore também é simples. Significa mover o nó 
filho para a posição do nó removido
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Remoção: Nó com um único filho.
Disciplina: ESTRUTURA DE DADOS II 54
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Remoção
Nó com dois filho.
Disciplina: ESTRUTURA DE DADOS II 55
1. Mover o nó mais a direita da subárvore esquerda
OU
2. Mover o nó mais a esquerda da subárvore a direita
Recursividade para arrumar a continuidade da árvore
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Remoção: Nó com dois filho.
Disciplina: ESTRUTURA DE DADOS II 56
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Remoção: Nó com dois filho.
Disciplina: ESTRUTURA DE DADOS II 57
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvore binária
• Remoção: Nó com dois filho.
Disciplina: ESTRUTURA DE DADOS II 58
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Disciplina: ESTRUTURA DE DADOS II
PERCORRER ÁRVORE BINÁRIA
59
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Percorrer árvore binária
• Uma operação muito comum é percorrer 
uma árvore binária
– significa passar por todos os nós, pelo menos 
uma vez. 
Disciplina:ESTRUTURA DE DADOS II
uma vez. 
– Na operação de percorrer a árvore pode-se 
passar por alguns nós mais de uma vez, sem 
porém visitá-los. 
60
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Percorrer árvore binária
• Não existe ordem natural para percorrer 
árvores e portanto podemos escolher 
diferentes maneiras de percorrê-las. 
Disciplina: ESTRUTURA DE DADOS II
– Nós iremos estudar três métodos para percorrer 
árvores.
• Pré-ordem
• Ordem simétrica
• Pós-ordem
61
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Percorrer árvore binária
• Pré-ordem
Disciplina: ESTRUTURA DE DADOS II 62
Resultados: F B A D C E H G I.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Percorrer árvore binária
• Ordem simétrica
Disciplina: ESTRUTURA DE DADOS II 63
Resultados: A B C D E F G H I.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Percorrer árvore binária
• Pós-ordem
Disciplina: ESTRUTURA DE DADOS II 64
Resultados: A C E D B G I H F.
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Disciplina: ESTRUTURA DE DADOS II
ÁRVORES AVL
65
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvores AVL
Árvores Binárias Balanceadas
• Árvores Binárias Balanceadas(AVL)
– é uma árvore binária na qual as alturas das duas 
subárvores de cada um dos nós nunca diferem 
em mais de 1.
Disciplina: ESTRUTURA DE DADOS II
em mais de 1.
– O balanceamento de um nó é igual a diferença 
entre as suas altura esquerda e direita.
• cada nó de uma árvore balanceada tem 
balanceamento igual a -1, 0 ou 1.
66
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvores AVL
Árvores Binárias Balanceadas
• Árvores Binárias Balanceadas(AVL)
Os valores dentro do nó são altura 
Disciplina: ESTRUTURA DE DADOS II 67
Os valores dentro do nó são altura 
do nó e seu balanceamento. 
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvores AVL
Árvores Binárias Balanceadas
• Qual a vantagem em balancear uma árvore?
– A busca por um elemento se torna na média 
mais rápido
Disciplina: ESTRUTURA DE DADOS II 68
Infelizmente o método de inserção em árvores binárias 
apresentado anteriormente não garante que a árvore 
permanecerá balanceada. Como já vimos a estrutura da 
árvore depende da ordem em que as chaves são inseridas 
na árvore. 
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvores AVL
Árvores Binárias Balanceadas
– Observemos uma subárvore que ser tornará 
desbalanceada quando ocorrer uma inserção.
Disciplina: ESTRUTURA DE DADOS II 69
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvores AVL
Árvores Binárias Balanceadas
• Para manter a árvore balanceada é 
necessário que a transformação na árvore 
de tal modo que:
Disciplina: ESTRUTURA DE DADOS II
– A árvore permaneça uma árvore de busca 
binária;
– A árvore continue a ser uma árvore balanceada.
70
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvores AVL
Árvores Binárias Balanceadas
• Para balancearmos uma árvore
– Precisaremos da da operação de rotação em 
uma árvore
• Uma rotação pode ser à direita 
Disciplina: ESTRUTURA DE DADOS II
• Uma rotação pode ser à direita 
• ou esquerda
71
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Árvores AVL
Árvores Binárias Balanceadas
• Operação de rotação
Disciplina: ESTRUTURA DE DADOS II 72
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Disciplina: ESTRUTURA DE DADOS II
EXERCÍCIOS
73
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Miniprob.:quebra-cabeças 8 peças
Disciplina: ESTRUTURA DE DADOS II
• Estados: posição das 8 peças e do vazio
• Estado inicial: qqr estado
• Função sucessor: esq., dir., acima, abaixo
• Teste: verifica se o estado corrente é o objetivo
• Custo:cada passo=1; caminho=num. d passos
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Problema: jarros
• Dados uma bica d`agua, um jarro de 
capacidade 3 litros e um jarro de capacidade 
4 litros (ambos vazios). Como obter 2 litros 
no jarro de 4? 
Disciplina: ESTRUTURA DE DADOS II
no jarro de 4? 
Escola de Ciência e Tecnologia
Curso: INFORMÁTICA
Exemplo da primeira aula (jarros)
Disciplina: ESTRUTURA DE DADOS II