Estrutura de Dados I
Robson Godoi / Sandra Siebra
Árvore
Árvore - Definição
 Representam um conjunto de elementos (nós) preservando
a relação hierárquica entre eles.
 Formalmente, uma árvore é um conjunto finito T de nós, tais
que:
 Existe um nó que não é subordinado a nenhum outro nó
denominado raiz da árvore.
 Os demais nós (ligados à raiz por arcos/arestas) formam
m >= 0 conjuntos disjuntos S1 , S2 , ... , Sm , onde cada um
destes conjuntos é uma sub-árvore.
Árvore - Utilidade
 Árvores são úteis na descrição de qualquer estrutura
que envolve hierarquia, como os exemplos:




Hierarquia de cargos numa empresa;
Precedência de operações em expressões;
Análise sintática de textos,
Ontologias, etc.
Árvore (Conceitos)
 Os nós subordinados a um nó e
ligados a ele por um arco são
denominados os filhos daquele
nó (pai).
 Os nós subordinados a um nó são
irmãos entre si.
 O número de filhos (sub-árvores)
de um nó é o grau daquele nó.
 Um nó de grau zero é chamado
folha ou nó terminal (nó sem
filhos).
 O nível de um nó é a distância
daquele nó até a raiz (número de
arcos que devem ser percorridos).
 O nível da raiz é ZERO.
 A altura ou profundidade de uma
arvore é definida pelo nível mais
alto da árvore acrescido de um ou
o número de nós do maior ramo.
 Os ancestrais de um nó são os
nós existentes entre a raiz e o
próprio nó.
RAIZ
FOLHAS
Árvore (Exemplo)
 Na árvore abaixo:
a
d
b
e
k





f
l
c
g
h
j
i
m
A: raiz da árvores;
B, C, D, E, H: raízes de sub-árvores
F, G, I, J, K, L, M: folhas
B, C, D: irmãos, filhos de A
E, F: irmãos, filhos de B
Árvore Binária (Conceitos)
 São estruturas do tipo Árvore, onde há um conceito de ordem e o
grau de cada nó é menor ou igual a dois, ou seja, cada nó tem, no
máximo, dois filhos.
 As sub-árvores são identificadas como a da Esquerda e a da
Direita.
 Árvore binária é um tipo de árvore.
A
A
B
B
A) Duas árvores iguais
A
B
A
B
B) Duas árvores binárias diferentes
Árvore Binária (Conceitos)
 As árvores binárias podem ser:
A. Árvore estritamente binária: é uma árvore binária em que
cada nó possui 0 ou 2 filhos.
B. Árvore binária completa: é uma árvore binária cujo o maior
nível é o d e onde cada folha da árvore deve estar neste nível
(d) ou no nível d-1.
C. Árvore binária cheia: é uma árvore estritamente binária com
profundidade d em que todas as folhas estão no nível d.
Árvore Binária (Conceitos)
Exemplos dos casos anteriores
(A)
(B)
(C)
Árvore Binária (Percurso ou Caminhamento)
 Uma operação comum é percorrer uma árvore binária, seja
simplesmente para imprimir o valor de seus elementos ou
para localizar um determinado elemento.
 No entanto não existe uma ordem natural de percurso em
uma árvore. Sendo assim, são definidos três métodos de
percurso:
• Pré-Ordem (pré-fixado)
• Em Ordem (central)
• Pós-Ordem (pós-fixado)
 Sendo esses métodos normalmente definidos
recursivamente.
Pré-ordem (Pré-fixada)
Percurso em Pré-Ordem
1. Se árvore estiver vazia então fim.
2. Visitar o nó raiz.
3. Percorrer a sub-árvore esquerda, em pré-ordem
4. Percorrer a sub-árvore direita, em pré-ordem.
Procedure PreOrdem(N:pont);
Begin
If (N <> nil) then
begin
Processa (N); {Ex:imprimir}
PreOrdem (N^.esq);
PreOrdem (N^.dir);
end;
end;
Em Ordem (Central)
Percurso Em Ordem
1. Se árvore estiver vazia então fim.
2. Percorrer a sub-árvore esquerda, em ordem simétrica
3. Visitar o nó raiz.
4. Percorrer a sub-árvore direita, em ordem simétrica.
Procedure EmOrdem(N:pont);
Begin
If (N <> nil) then
begin
EmOrdem (N^.esq);
Processa (N); {Ex:imprimir}
EmOrdem (N^.dir);
end;
end;
Pós-ordem (Pós-fixada)
Percurso em Pós-Ordem
1. Se árvore estiver vazia então fim.
2. Percorrer a sub-árvore esquerda, em pós-ordem.
3. Percorrer a sub-árvore direita, em pós-ordem.
4. Visitar o nó raiz.
Procedure PosOrdem (N:pont);
Begin
If (N <> nil) then
begin
PosOrdem (N^.esq);
PosOrdem (N^.dir);
Processa(N); {Ex:imprimir}
end;
end;
Árvore Binária - Exercício
 Qual o arranjo dos nó da árvore ao
lado, obtido ao percorrê-la em:
 Pré-ordem
 Ordem simétrica
 Pós-ordem
 Responda e justifique sua resposta:
 A árvore acima é uma árvore
estritamente binária?
 A árvore acima é uma árvore binária
completa?
 A árvore acima é uma árvore binária
cheia?




Quais os nós folhas?
Qual o nível de cada nó?
Qual a profundidade da árvore?
Liste os ancestrais dos nós B, H e F.
Árvore Binária de Busca (ABB)
 Árvore Binária de Busca (ABB)
 Árvores binárias organizadas para facilitar a busca de
elementos
 Característica: chaveEsq < chaveRaiz < chaveDir
D
B
A
F
C
E
G
Árvore Binária de Busca (ABB)
 Definição da Estrutura de Dados
type
ponteiro = ^no;
registro = record
nome
idade
salario
end;
no
= record
dado
dir, esq
end;
TArvore = record
raiz
end;
var
A : TArvore;
: string [40];
: integer;
: real;
: registro;
: ponteiro;
: ponteiro;
Árvore Binária de Busca (ABB)
 Operações sobre ABB
1.
2.
3.
4.
5.
6.
7.
8.
Criar arvore vazia
Destruir a arvore
Verificar se a arvore está vazia
Inserir
Pesquisar
Alterar
Excluir
Percurso ou Caminhamento
AAB - Criar / Destruir
procedure Criar (var a:TArvore);
begin
a.raiz :=NIL;
end;
procedure Destruir (var a:TArvore);
begin
if (a <> nil) then
begin
Destruir (a^.esq);
Destruir (a^.dir);
Dispose (a);
a := nil;
end;
end;
AAB - Vazia
function Vazia (a:TArvore):boolean;
begin
if (a.raiz=NIL) then
Vazia := TRUE
else
Vazia := FALSE;
end;
OU
function Vazia (a:TArvore):boolean;
begin
Vazia := (a.raiz = nil);
end;
AAB - Inserir
function Inserir
(var raiz: ponteiro;
dadoaux : registro): ponteiro;
begin
Inserir := nil;
if raiz = nil then
begin
new (raiz);
raiz^.dado := dadoaux;
raiz^.esq := nil;
raiz^.dir := nil;
Inserir
:= raiz;
end
else begin
if dadoaux.nome < raiz^.dado.nome
Inserir := Inserir (raiz^.esq,
if dadoaux.nome > raiz^.dado.nome
Inserir := Inserir (raiz^.dir,
end;
end;
then
dadoaux);
then
dadoaux)
AAB - Pesquisar
function Pesquisar (
raiz: ponteiro;
dadoaux : registro): ponteiro;
begin
if raiz = nil then
Pesquisar := nil
else
begin
if raiz^.dado.nome = dadoaux.nome then
Pesquisar := raiz
else
begin
if raiz^.dado.nome < dadoaux.nome then
Pesquisar := Pesquisar(raiz^.dir,dadoaux)
else
Pesquisar := Pesquisar(raiz^.esq,dadoaux);
end;
end;
end;
AAB - Alterar
function Alterar
(var raiz: ponteiro;
dadoaux : registro): ponteiro;
begin
if raiz = nil then
Alterar := nil
else
begin
if raiz^.dado.nome = dadoaux.nome then
begin
raiz^.dado := dadosaux;
Alterar
:= raiz;
end else begin
if raiz^.dado.nome < dadoaux.nome then
Alterar := Alterar(raiz^.dir,dadoaux)
else
Alterar := Alterar(raiz^.esq,dadoaux);
end;
end;
end;
AAB – Alterar (Alternativa)
function Alterar
(var raiz: ponteiro;
dadoaux : registro): ponteiro;
var
no : ponteiro;
begin
no := Pesquisar (raiz, dadoaux);
if no <> nil then
begin
no^.dado := dadosaux;
end;
Alterar := no;
end;
AAB – Excluir
 Para excluir um nó de uma árvore deve-se levar em consideração
que seus filhos devem continuar na árvore e esta deverá
continuar ordenada (menor a esquerda e maior a direita).
 Então temos três possibilidades que devem ser tratadas
separadamente, afim de manter intacta a estrutura da árvore
binária de busca. Excluir nó que:
 Não tenha filhos (folha):
 Exclui o nó.
 Tenha somente um dos filhos (esquerdo ou direito):
 Substitui o nó por seu filho.
 Exclui o nó.
 Tenha dois filhos:
 Substitui o nó por outro escolhido, seguindo um dos critérios:
o O menor dos maiores.
o O maior dos menores.
 Exclui o nó.
AAB – Excluir
procedure Remover
(var raiz : ponteiro;
dadoaux : integer);
var
ptr : ponteiro;
begin
if raiz <> nil then begin
if raiz^.dado = dadoaux
then
begin
if
raiz^.esq = nil then
begin
ptr
:= raiz;
raiz := raiz^.dir;
dispose(ptr);
end
else if raiz^.dir = nil then
begin
ptr := raiz;
raiz := raiz^.esq;
dispose(ptr);
end
else
Substituir(raiz,raiz^.dir);
end
else
if raiz^.dado < dadoaux then
RemoveRaiz(raiz^.dir,dado)
else
RemoveRaiz(raiz^.esq,dado);
end;
end;
end;
AAB – Excluir
 Substitui o nó a ser excluído por outro escolhido seguindo um
critérios do Menor dos Maiores.
procedure Substituir (
raiz : ponteiro;
var sucessor : ponteiro);
var
ptr : ponteiro;
begin
if sucessor^.esq = nil then
begin
raiz^.dado := sucessor^.dado;
ptr := sucessor;
sucessor := sucessor^.dir;
dispose(ptr);
end
else
Substituir(raiz,sucessor^.esq);
end;
Degeneração (ABB)
 Diferenças muito grande de alturas entre sub-àrvores de um nó
causando a perda de eficiência.
D
B
F
G
I
M
Árvore Balanceada
 É perfeitamente balanceada, quando para qualquer nó, as suas
sub-árvores tem a mesma altura.
 Nem sempre é possível esta precisão, permitindo um nível de
diferença.
D
D
B
A
F
C
E
B
G
A
F
C
E
G
H
Técnicas de Balanceamento
 Estático : Baseia-se na reorganização total dos elementos da
árvore em um momento apropriado.
 Dinâmico : À medida que os elementos são inseridos, a árvore
vai sendo balanceada, obrigando uma reorganização de seus
elementos.
Balanceamento Estático
 Construção de um array com todos os elementos da árvore
através de um percurso em ordem simétrica.
 Leitura do array de forma semelhante a pesquisa binária para a
construção de uma nova árvore balanceada.
D
B
F
B
G
I
M
D
F
G
I
M
Balanceamento Estático
procedure CarregaArray (raiz: ponteriro;
arr : ArrayNo;
ind : Integer);
begin
if (raiz <> nil) then
begin
CarregaArray (raiz^.esq, arr, ind);
Inc (ind);
arr [ind] := raiz^.dado;
CarregaArray (raiz^.dir, arr, ind);
end;
end;
Balanceamento Estático
procedure CarregaArvore (raiz
: ponteiro;
arr
: ArrayNo;
Ini, Fim : integer);
var
Med : integer;
No : ponteiro;
begin
if (Ini > Fim) then
begin
Exit;
end
else
begin
Med
:= ((Fim - Ini) div 2) + Ini;
No
:= Insere (raiz, arr [Med]);
No^.Esq := CarregaArvore (No, arr, Ini,(Med-1));
No^.Dir := CarregaArvore (No, arr, (Med+1), Fim);
end;
end;
Balanceamento Dinâmico (AVL)
 Conceito menos rigoroso sobre o balanceamento, introduzido em 1962 por dois
matemáticos russos (Adelson e Landis).
 Uma árvore é considerada balanceada se para qualquer nó da árvore, as
alturas das sub-árvores à esquerda e à direita diferem de no máximo de 1.
 Esta diferença é chamada de fator de balanceamento:
 FatBal(n) <= -1, significa que a altura da árvore à esquerda de n é maior
que à da direita
 FatBal(n) >= +1, significa que a altura da árvore à esquerda de n é menor
que à da direita
 FatBal(n) = 0, significa que a altura da árvore à esquerda de n é igual à da
direita
-1
+1
0
-1
0
+1
0
Balanceamento Dinâmico (AVL)
 Após a inserção de um novo nó deve-se recalcular os fatores de
balanceamento.
 Se houve para um dado nó |FatBal(n)| > 1 então deve-se rebalancear a
árvores através do roteamento dos nós.
 Neste processo temos dois nós muitos importantes:
 A: Nó ancestral mais próximo do nó inserido com FatBal (n) <> 0 antes da
inserção.
 B: Filho de A na sub-árvore onde ocorreu a inserção
 Exemplo : Inserindo 20 e 10.
20 -1
10 0
Balanceamento Dinâmico (AVL)
 Exemplo : Inserindo 5.
20 -1
20
10 0
-2 A
10
10 -1 B
5
0
5
0
 Exemplo : Inserindo 30.
10
5
0
0
20
10
5
0
0
+1
20
+1
30
0
200
Balanceamento Dinâmico (AVL)
 Exemplo : Inserindo 25.
+2
10
10
+1
0
5
5
0
20
20
+2 A
+1 A
30
30
0B
25
10
0
0
+2
10
5
-1 B
20
+1
+2 A
5
0
25
0
0
30
25 +1 B
20
30
0
0
Balanceamento Dinâmico (AVL)
 Exemplo : Inserindo 27.
10
10
+1
0
5
5
0
25
0
25
+1 B
0
30
0
20
20
+2 A
030
27
25
10
5
0
-1
0
20
+1
0
27
30
0
0
-1
Balanceamento Dinâmico (AVL)
 Exemplo : Inserindo 28.
25
25
+1
10
10
0
0
20
0
30
-2 A
30
-1
5
+1
0
27
5
0
20
0
27 +1 B
0
28 0
25
10
5
0
0
0
20
28
0
27
0
0
030