Capítulo 7 –
Estruturas de
dados do tipo
árvore
slide
slide
slide
slide
1111
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
As estruturas de dados do tipo árvore são não
lineares, ou seja, os elementos que as
compõem não estão armazenados de forma
sequencial e também não estão todos
encadeados.
slide
slide
slide
slide
2222
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
Árvores
slide
slide
slide
slide
3333
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
Árvore binária
Conjunto finito de elementos, em que
cada um é denominado nó e o primeiro é
conhecido como raiz. Pode estar vazio ou
ser particionado em três subconjuntos:
1º subconjunto (nó raiz), 2º subconjunto
(sub-árvore direita) e 3º subconjunto
(sub-árvore esquerda).
slide
slide
slide
slide
4444
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
slide
slide
slide
slide
5555
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
As árvores binárias podem ser ilustradas de
três formas:
slide
slide
slide
slide
6666
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
Propriedades da árvore binária:
a) Todos os nós de uma sub-árvore direita são
maiores que o nó raiz.
b) Todos os nós de uma sub-árvore esquerda
são menores que o nó raiz.
c) Cada sub-árvore é também uma árvore
binária.
d) O grau de um nó representa o seu número
de sub-árvores.
slide
slide
slide
slide
7777
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
e) Na árvore binária, o grau máximo de um nó é 2.
f) O grau de uma árvore é igual ao máximo dos
graus de todos os seus nós.
g) Uma árvore binária tem grau máximo igual a 2.
h) Nó pai: nó acima e com ligação direta a outro nó.
i) Nó filho: nó abaixo e com ligação direta a outro
nó. São os nós raízes das sub-árvores.
j) Nós irmãos: são que possuem o mesmo nó pai.
k) Nó folha ou terminal: nó que não possui filhos.
slide
slide
slide
slide
8888
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
Graus dos nós de uma árvore binária
slide
slide
slide
slide
9999
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
l) Nós ancestrais: estão acima de um nó e têm
ligação direta ou indireta.
slide
slide
10
10
slide
10
slide
10
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
m) Nós descendentes: estão abaixo de um nó e
possuem ligação direta ou indireta.
slide
slide
11
11
slide
11
slide
11
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
n) Nós descendentes direito: estão abaixo de um
nó, possuem ligação direta ou indireta e fazem
parte da sub-árvore direita.
slide
slide
12
12
slide
12
slide
12
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
o) Nós descendentes esquerdo: estão abaixo de um
nó, possuem ligação direta ou indireta e fazem
parte da sub-árvore esquerda.
slide
slide
13
13
slide
13
slide
13
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
p) Nível de um nó: distância do nó raiz.
q) Altura ou profundidade da árvore: nível mais
distante da raiz.
slide
slide
14
14
slide
14
slide
14
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
r) 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.
slide
slide
15
15
slide
15
slide
15
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
s) Árvore estritamente binária: árvore em que todos
os nós têm 0 ou 2 filhos.
t) Expressão que representa o número de nós de
uma árvore estritamente binária = 2n−1, onde n é o
número de nós folha.
slide
slide
16
16
slide
16
slide
16
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
u) Árvore completa: todos os nós com menos de
dois filhos ficam no último e no penúltimo nível.
slide
slide
17
17
slide
17
slide
17
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
v) Árvore cheia: árvore estritamente binária e
completa.
slide
slide
18
18
slide
18
slide
18
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
Na inserção, as propriedades da árvore
devem ser obedecidas e todo novo nó é
sempre uma folha.
Na remoção, o filho da direita, que é o mais
velho, assume o lugar do nó pai.
Na consulta (em ordem, pré-ordem e pósordem), todos os nós são listados, alterandose apenas a ordem.
slide
slide
19
19
slide
19
slide
19
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
- Consulta em ordem: cada árvore é mostrada
com o ramo da esquerda, a raiz e
posteriormente o ramo da direita.
- Consulta pré-ordem: cada árvore é mostrada
com a raiz, o ramo da esquerda e
posteriormente o ramo da direita.
- Consulta pós-ordem: cada árvore é mostrada
com o ramo da esquerda, o ramo da direita e
posteriormente a raiz.
slide
slide
20
20
slide
20
slide
20
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
Consultas em um árvore binária
slide
slide
21
21
slide
21
slide
21
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
Análise da complexidade
As árvores em que cada nó possui um único
filho têm altura máxima (igual a n).
Segundo Markenzon (1994), uma árvore binária
completa com n > 0 nós possui altura mínima h
= 1 + log n .
slide
slide
22
22
slide
22
slide
22
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
slide
slide
23
23
slide
23
slide
23
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
Na inserção, o nó sempre é inserido em uma folha,
e deve percorrer todos os nós desde a raiz, até
chegar a uma folha e acrescentar um filho, gastando
nisso a altura da árvore, ou seja, O(log n).
Na remoção, o pior caso é quando o nó está em
uma folha no nível mais baixo. Gasta-se a altura da
árvore para encontrá-lo, em uma árvore de altura
mínima, e algumas operações de atualização de
ponteiros, gerando complexidade O(log n).
slide
slide
24
24
slide
24
slide
24
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
Árvore AVL
Criada em 1962 por Adelson-Velsky e
Landis, é uma árvore binária balanceada
que obedece a todas as propriedades da
árvore binária e em que cada nó apresenta
diferença de altura entre as sub-árvores
direita e esquerda de 1, 0 ou –1.
slide
slide
25
25
slide
25
slide
25
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
Árvore AVL
slide
slide
26
26
slide
26
slide
26
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
Se a diferença de altura entre as sub-árvores de um nó é
maior que 1 ou menor que –1, a árvore está
desbalanceada e haverá uma rotação.
slide
slide
27
27
slide
27
slide
27
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
Análise da complexidade
O custo das operações é semelhante ao das árvores
binárias.
Ao se inserir um novo nó u, o pai desse nó (chamado v)
terá a altura de uma de suas sub-árvores alterada. É
necessário checar se a sub-árvore de raiz v está
desbalanceada. Isso se faz subtraindo-se as alturas das
duas sub-árvores de v, cujos valores estão armazenados
no próprio nó v. Em caso de desbalanceamento, deve-se
realizar uma rotação simples ou dupla.
slide
slide
28
28
slide
28
slide
28
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.
Outros nós (além do v) no caminho de v até a raiz
podem também ficar desbalanceados e a verificação
deverá ser feita. O percurso do nó até a raiz é feito
em O(log n) passos.
A exclusão de algum nó também pode ser feita em
O(log n) passos. Depois, deve-se verificar se a árvore
ficou desbalanceada e examinar os nós no caminho
da raiz até alguma folha. O número de rotações
necessárias pode alcançar a ordem O(log n).
slide
slide
29
29
slide
29
slide
29
2011
2011
Pearson
Pearson
Prentice
Prentice
Hall.
Hall.
Todos
Todos
direitos
direitos
reservados.
reservados.
©
2011
Pearson
Prentice
Hall.
Todos
os
direitos
reservados.
©©©
2011
Pearson
Prentice
Hall.
Todos
ososos
direitos
reservados.