08_Arvores

Prévia do material em texto

Árvores
Estruturas de Dados
Prof. Vilson Heck Junior
INTRODUÇÃO
Árvores
Introdução
• Árvores são estruturas de dados
utilizadas para armazenar e recuperar
dados de forma rápida e eficiente;
• Árvores não são lineares, ou seja, os
elementos não são dispostos em forma
sequencial;
Introdução
• Árvores são amplamente utilizadas e
possuem diversas estratégias de
implementação;
• Cada estratégia tem um conjunto
específico de algoritmos para
armazenamento e recuperação dos
dados;
– Árvores genealógicas são análogas às
estruturas de dados árvores.
COMPOSIÇÃO
Árvores
Composição
• As árvores são compostas por:
– Nodos/Nós: são os elementos inseridos em
uma árvore;
– Arestas: fazem a ligação entre 2 nodos;
Composição
• O primeiro Nodo de uma árvore é
chamado de Raiz;
– Todos os demais nodos da árvore serão seus
descendentes;
• Nodos que não tenham filhos serão
chamados de folhas, ou terminais;
• Os demais nodos são ditos
intermediários, ou às vezes: galhos.
Composição
• As principais propriedades de cada nodo
são:
– Ordem/Grau: Indica o número de filhos que
o nodo possui;
– Nível/Altura/Profundidade: Indica a
distância do nodo em relação à raiz;
• A árvore também possuí valores de ordem e de
nível.
– Ambos os valores serão assumidos com base no
maior valor encontrado em qualquer nodo.
A
CB
D FE
G IH J
Nível 0
Nó A = Raiz – Ordem 2
Nível 1
Nó B = Galho – Ordem 3
Nó C = Folha – Ordem 0
Nível 2
Nó D = Folha – Ordem 0
Nó E = Galho – Ordem 4
Nó F = Folha – Ordem 0
Nível 3
Nó G = Folha – Ordem 0
Nó H = Folha – Ordem 0
Nó I = Folha – Ordem 0
Nó J = Folha – Ordem 0
Árvore: Nível 3 e Ordem 4
Nós / Nodos
Arestas
N
íve
l
Ordem
OUTRAS PROPRIEDADES
Árvores
Propriedades
• Qualquer nodo de uma árvore pode ser
chamado de raiz para uma sub-árvore;
• Um Nodo Pai é um nodo conectado
diretamente acima de outro nodo;
• Um Nodo Filho é um nodo conectado
diretamente abaixo de outro nodo;
• Nodos Irmãos compartilham o mesmo
nodo pai;
Propriedades
• Nodos Ancestrais são todos os nodos
que estão acima de um nodo, com
ligação direta ou indireta;
• Nodos Descendentes são todos os nodos
que estão abaixo de um nodo, com
ligação direta ou indireta;
EXERCÍCIOS
Árvores
A
CB D
F
E
G IH MK N
O P TSR U X
765
#
4
&
3WY Z
8 9
ÁRVORES BINÁRIAS
Árvores
Árvores Binárias
• Árvores Binárias são árvores com todas as
propriedades vistas anteriormente, porém
com algumas regras:
– A Ordem máxima da árvore é 2;
– Todos os nodos de uma sub-árvore, do filho à
direita, serão maiores do que o nodo pai;
– Todos os nodos de uma sub-árvore, do filho à
esquerda, serão menores do que o nodo pai;
• Geralmente chamadas de “Árvores binárias
de pesquisa”;
Árvores Binárias
– O número máximo de nodos para cada nível
de uma árvore binária é determinada pela
equação:
níveltotal 2
A
CB
D FE G
IH
J
Nível 0
Nó A = Raiz – Ordem 2
Nível 1
Nó B = Galho – Ordem 2
Nó C = Galho – Ordem 2
Nível 2
Nó D = Folha – Ordem 0
Nó E = Galho – Ordem 2
Nó F = Folha – Ordem 0
Nó G = Folha – Ordem 0
Nível 3
Nó H = Galho – Ordem 1
Nó I = Folha – Ordem 0
Árvore Binária: Nível 4 e Ordem 2
Nós / Nodos
Arestas
N
íve
l
Ordem
Nível 4
Nó J = Folha – Ordem 0
EXEMPLO:
ÁRVORE BINÁRIA EM MDA
Árvores
IMPLEMENTADO ÁRVORES BINÁRIAS
Árvores
Implementando
• Árvores são implementadas com
elementos dinâmicos, assim como nas
listas encadeadas;
• Nas listas, tínhamos apenas um próximo
elemento. Nas árvores, cada elemento
terá “dois próximos”:
– Filho da Esquerda; e
– Filho da Direita.
Implementando
public class Nodo
{
public int numero;
//outros atributos
//...
public Nodo esquerda;
public Nodo direita;
public Nodo pai; //Opcional
}
Implementando
• Para implementar operações em árvores,
é necessário percorrer diversos nodos
dela;
– Para inserir um novo elemento, é necessário
descer a árvore nível por nível até encontrar
a posição adequada ao novo elemento;
– Para remover um elemento, é necessário
descer a árvore até encontrar o elemento a
ser removido;
Implementando
• Vale lembrar das regras mais
importantes de navegação nas árvores
binárias de pesquisa:
– Elementos menores estarão à esquerda;
– Elementos maiores estarão à direita.
Implementando
• Inserção:
– Se a raiz estiver vazia:
• Insere na raiz.
– Senão:
• Navega pela árvore (subindo de nível)
comparando o valor a ser inserido com os
valores dos nodos visitados;
– Se Menor – Esquerda; e
– Se Maior – Direita;
• Quando encontrar um nodo sem filho para o
lado por onde deveria seguir, insere o novo
elemento nesta posição.
public static void inserir(Nodo novo) {
novo.direita = null;
novo.esquerda = null;
novo.pai = null;
if (raiz == null) {
raiz = novo;
} else {
Nodo aux = raiz;
while (aux != null) {
if (novo.numero < aux.numero) {
if (aux.esquerda == null) {
aux.esquerda = novo;
break;
}
aux = aux.esquerda;
}
else {
if (aux.direita == null) {
aux.direita = novo;
break;
}
aux = aux.direita;
}
}
novo.pai = aux;
}
}
Implementando
• Pesquisa:
– Se a raiz estiver vazia:
• Não encontrado!
– Senão:
• Navega pela árvore (subindo de nível)
comparando o valor pesquisado com os valores
dos nodos visitados:
– Igual – Encontrado!
– Menor – Desloca à Esquerda;
– Maior – Desloca à Direita;
– Se percorrer toda a árvore sem encontrar:
• Não encontrado!
Implementando
public Nodo pesquisar(int nro) {
Nodo aux = raiz;
while (aux != null) {
if (aux.numero == nro) {
return aux;
} else if (nro < aux.numero) {
aux = aux.esquerda;
} else {
aux = aux.direita;
}
}
return null;
}
Implementando
• Navegar por todos os Nodos:
6
82
1 4
3
Implementando
• Listar Conteúdo da Árvore:
– A listagem da árvore pode ser feitas de três 
formas básicas:
• Em ordem:
– 1, 2, 3, 4, 6, 8
• Pré-ordem:
– 6, 2, 1, 4, 3, 8
• Pós-ordem:
– 1, 3, 4, 2, 8, 6
6
82
1 4
3
Implementando
• Listar Conteúdo da Árvore:
– Pode ser implementado com diversas 
estratégias:
• Recursividade;
• Pilha;
• Busca do subsequente.
6
82
1 4
3
Listar com Recursividade
public static void listar(Nodo inicio) {
if (inicio == null) {
return;
}
listar(inicio.esquerda);
System.out.println(inicio.numero);
listar(inicio.direita);
}
Implementando
• Remoção de Nodos:
– Aux = Pesquisar(Nodo)
– Se Aux == NULL
• não encontrado!
– Senão:
• Se Aux for raiz:
– Sem filhos
– Com um filho
– Com dois filhos
• Senão
– Sem filhos
– Com um filho
– Com dois filhos
Implementando
• Remoção de Nodos:
– Aux = Pesquisar(Nodo)
– Se Aux == NULL
• não encontrado!
– Senão:
• Se Aux for raiz:
– Sem filhos
– Com um filho
– Com dois filhos
• Senão
– Sem filhos
– Com um filho
– Com dois filhos
Implementando
• Remoção de Nodos – Raiz sem filhos:
– Raiz = null;
Implementando
• Remoção de Nodos:
– Aux = Pesquisar(Nodo)
– Se Aux == NULL
• não encontrado!
– Senão:
• Se Aux for raiz:
– Sem filhos
– Com um filho
– Com dois filhos
• Senão
– Sem filhos
– Com um filho
– Com dois filhos
Implementando
• Remoção de Nodos – Raiz com um filho:
– Raiz = Filho Único da Raiz;
Implementando
• Remoção de Nodos:
– Aux = Pesquisar(Nodo)
– Se Aux == NULL
• não encontrado!
– Senão:
• Se Aux for raiz:
– Sem filhos
– Com um filho
– Com dois filhos
• Senão
– Sem filhos
– Com um filho
– Com dois filhos
Implementando
• Remoção de Nodos – Raiz com dois filhos:
– Substituto = Subsequente(Raiz); //Aux
– Substitui (Raiz pelo Substituto);
Implementando
• Remoção de Nodos:
– Aux = Pesquisar(Nodo)
– Se Aux == NULL
• não encontrado!
– Senão:
• Se Aux for raiz:
– Sem filhos
– Com um filho
– Com dois filhos
• Senão
– Sem filhos
– Com um filho
– Com dois filhos
Implementando
• Remoção de Nodos – Não Raiz sem filhos:
– PaiAux = Aux.Pai;
– Se (PaiAux.Esquerda == Aux) então
• PaiAux.Esquerda = null;
– Senão
• PaiAux.Direita = null;
Implementando
• Remoção de Nodos:
– Aux = Pesquisar(Nodo)
– Se Aux == NULL
• não encontrado!
– Senão:
• Se Aux for raiz:
– Sem filhos
– Com um filho
– Com dois filhos
• Senão
– Semfilhos
– Com um filho
– Com dois filhos
Implementando
• Remoção de Nodos – Não Raiz / 1 filho:
– PaiAux = Aux.Pai;
– FilhoAux = Aux.Filho; (esquerda, ou direita)
– Se (PaiAux.Esquerda == Aux) então
• PaiAux.Esquerda = FilhoAux;
– Senão
• PaiAux.Direita = FilhoAux;
Implementando
• Remoção de Nodos:
– Aux = Pesquisar(Nodo)
– Se Aux == NULL
• não encontrado!
– Senão:
• Se Aux for raiz:
– Sem filhos
– Com um filho
– Com dois filhos
• Senão
– Sem filhos
– Com um filho
– Com dois filhos
Implementando
• Remoção de Nodos – Não Raiz / 2 filhos:
– Substituto = Subsequente(Aux);
– Substitui (Aux pelo Substituto);
Implementando
private static boolean substituirNodo(Nodo original, Nodo novo) {
if (original == null || novo == null) {
return false;
}
Nodo pai = original.pai;
if (pai != null) {
if (pai.esquerda == original) {
pai.esquerda = novo;
} else {
pai.direita = novo;
}
}
novo.pai = pai;
Nodo filho = original.esquerda;
if (filho != null) {
filho.pai = novo;
}
novo.esquerda = filho;
filho = original.direita;
if (filho != null) {
filho.pai = novo;
}
novo.direita = filho;
return true;
}
Continuação...
Implementando (1/3)
public static boolean remover(Nodo rem) {
if (rem == null) {
return false;
}
//Informação paterna
Nodo pai = rem.pai;
//Existe um substituto único ou nenhum?
Nodo subst;
if (rem.esquerda == null || rem.direita == null) {
//Ambos são null? sem substituto
if (rem.esquerda == rem.direita) {
subst = null;
} else { //Se direita vazia, substituto esta na esquerda e vice versa
if (rem.direita == null) {
subst = rem.esquerda;
} else {
subst = rem.direita;
}
} 
Implementando (2/3)
//Se tiver um pai, atualiza vinculo dos filhos, senão atualiza a raiz.
if (pai != null) {
if (pai.esquerda == rem) {
pai.esquerda = subst;
} else {
pai.direita = subst;
}
} else {
raiz = subst;
}
//Se tiver um filho substituto, atualiza seu vinculo paterno
if (subst != null) {
subst.pai = pai;
}
return true;
}
Implementando (3/3)
//Se chegarmos aqui é por que o nodo excluído tem dois filhos. (Subsequente)
//Procuramos o elemento imediatamente maior e que não tenha filho a esquerda
Nodo proximo = rem.direita;
while (proximo.esquerda != null) {
proximo = proximo.esquerda;
} 
//Removemos o nodo que tem apenas um filho
remover(proximo); //Recursividade
//Inserimos o nodo "próximo removido" no lugar do "removido"
substituirNodo(rem, proximo);
//Se estivermos excluindo a raiz, atualiza ela
if (pai == null) {
raiz = proximo;
}
return true;
}
Trabalho
• Implemente um Árvore Binária de Pesquisa para realizar a 
inserção, pesquisa, remoção e listagem de um cadastro de alunos. 
Os alunos serão cadastrados por:
– Nome (chave, String)
– Matricula (long)
– Nome do curso (String)
Como nome é o campo chave, a separação esquerda/direita dos 
elementos deverá ser feita com base nos nomes dos alunos. 
Exemplo de função para comparar strings de forma “alfabética”:
ÁRVORES BALANCEADAS
Árvores
Imagem: Natalie Jeremijenko
Árvores
• O pior cenário para uma árvore binária
de pesquisa é quando uma sequência de
números é inserida já em ordem:
– Crescente; ou
– Decrescente.
Árvore não Balanceada
• Entrada: 2, 5, 8, 10, 15
2
5
8
10
15
Árvores
• Para melhorar o tempo de busca em
árvores binárias de pesquisa, é possível
aplicar técnicas de balanceamento,
conforme ilustração a seguir:
Balanceando a Árvore
2
5
8
10
15
Balanceando a Árvore
2
5
8
10
15
Balanceando a Árvore
2
5
8
10
15
Árvores AVL
• O conceito de Árvore AVL foi criado em
1962 por Adelson-Velsky e Landis;
• É uma árvore binária de pesquisa
balanceada;
• O primeiro diferencial:
– cada nodo possuí um campo numérico
indicando a diferença de altura para cada
subárvore filha:
• 0 : subárvores com mesma altura;
• 1 : subárvore direita é 1 nível maior;
• -1 : subárvore esquerda é 1 nível maior;
A
CB
D E
IH
Nível 0
Nó A = Raiz – Ordem 2
Nível 1
Nó B = Galho – Ordem 2
Nó C = Galho – Ordem 2
Nível 2
Nó D = Galho – Ordem 2
Nó E = Galho – Ordem 1
Nível 3
Nó H = Folha – Ordem 0
Nó I = Folha – Ordem 0
Árvore Binária NÃO AVL: Nível 3 e Ordem 2
Nós / Nodos
Arestas
N
íve
lOrdem
Nível 4
A
CB
D E
IH
Nível 0
Nó A: Dif = -2
Nível 1
Nó B: Dif = -1
Nó C: Dif = 0
Nível 2
Nó D: Dif = 0
Nó E: Dif = 0
Nível 3
Nó H: Dif = 0
Nó I: Dif = 0
Diferenças
Árvores AVL
• Principal Regra:
– Nenhum nodo pode permanecer com
diferença maior de nível em qualquer
subárvore maior do que 1:
• 2
• – 2
– Sempre que esta condição não for satisfeita,
devem ocorrer rotações na árvore, até que
ela esteja balanceada, ou seja, com
qualquer subárvore
A
CB
D E
IH
Nível 0
Nó A: Dif = -2
Nível 1
Nó B: Dif = -1
Nó C: Dif = 0
Nível 2
Nó D: Dif = 0
Nó E: Dif = 0
Nível 3
Nó H: Dif = 0
Nó I: Dif = 0
Alguma |diferença| > 1 ?
Árvores AVL
• Rotações:
Diferença Diferença do filho Tipo de Rotação
2
1 Simples: à esquerda
0 Simples: à esquerda
-1 Dupla: filho para a direita e pai para a esquerda
-2
1 Dupla: filho para a esquerda e pai para a direita
0 Simples: à direita
-1 Simples: à direita
A
CB
D E
IH
Nível 0
Nó A: Dif = -2
Nível 1
Nó B: Dif = -1
Nó C: Dif = 0
Nível 2
Nó D: Dif = 0
Nó E: Dif = 0
Nível 3
Nó H: Dif = 0
Nó I: Dif = 0
Diferença do Filho Maior
Árvores AVL
• Rotações:
Diferença Diferença do filho Tipo de Rotação
2
1 Simples: à esquerda
0 Simples: à esquerda
-1 Dupla: filho para a direita e pai para a esquerda
-2
1 Dupla: filho para a esquerda e pai para a direita
0 Simples: à direita
-1 Simples: à direita
A
CB
D E
IH
Rotação à Direita
A
CB
D E
IH
Rotação à Direita
A
C
B
D
E
IH
Rotação à Direita
A
C
B
D
E
IH
Rotação à Direita
A
C
B
D
E
IH
Rotação à Direita
A
C
B
D
E
IH
Rotação à Direita
A
C
B
D
EIH
Árvore Binária AVL: Nível 2 e Ordem 2
Nível 0
Nó B: Dif = 0
Nível 1
Nó D: Dif = 0
Nó A: Dif = 0
Nível 2
Nó H: Dif = 0
Nó I: Dif = 0
Nó E: Dif = 0
Nó C: Dif = 0
Nível 3
N
íve
l
Ordem
ROTAÇÕES
Árvores AVL
Rotação Simples à Esquerda
private boolean RotacaoEsquerda(Nodo centro)
{
if (centro == null)
return false;
Nodo aux = centro.Direita;
if (aux == null)
return false;
//Atualizar a raiz?
if (centro == raiz)
raiz = aux;
//Troca os pais
aux.Pai = centro.Pai;
centro.Pai = aux;
if (aux.Pai != null)
{
Nodo pai = aux.Pai;
if (pai.Esquerda == centro)
pai.Esquerda = aux;
else
pai.Direita = aux;
}
//Troca os filhos
Nodo troca = aux.Esquerda;
aux.Esquerda = centro;
centro.Direita = troca;
return true;
}
Rotação Simples à Direita
private boolean RotacaoDireita(Nodo centro)
{
if (centro == null)
return false;
Nodo aux = centro.Esquerda;
if (aux == null)
return false;
//Atualizar a raiz?
if (centro == raiz)
raiz = aux;
//Troca os pais
aux.Pai = centro.Pai;
centro.Pai = aux;
if (aux.Pai != null)
{
Nodo pai = aux.Pai;
if (pai.Esquerda == centro)
pai.Esquerda = aux;
else
pai.Direita = aux;
}
//Troca os filhos
Nodo troca = aux.Direita;
aux.Direita = centro;
centro.Esquerda = troca;
return true;
}
Rotação Dupla à Esquerda
private boolean RotacaoDuplaEsquerda(Nodo centro)
{
if (centro == null)
return false;
Nodo aux = centro.Direita;
if (aux == null)
return false;
boolean retorno = RotacaoDireita(aux);
if (retorno == false)
return false;
return RotacaoEsquerda(centro);
}
Rotação Dupla à Direita
private boolean RotacaoDuplaDireita(Nodo centro)
{
if (centro == null)
return false;
Nodo aux = centro.Esquerda;
if (aux == null)
return false;
boolean retorno = RotacaoEsquerda(aux);
if (retorno == false)
return false;
return RotacaoDireita(centro);
}
OUTRAS ALTERAÇÕES
Árvores AVL
Alterações Classe Nodo
• Novos atributos:
public int AltEsq;
public int AltDir;
public int Dif;
• Construtor:
this.Dif = 0;
this.AltDir = 0;
this.AltEsq = 0;
AlturaSubArvore – Calculo Dif
public int AlturaSubArvore(Nodo atual)
{
if (raiz == null)
return 0;
if (atual == null)
atual = raiz;
if (atual.Esquerda ==null)
atual.AltEsq = 0;
else
atual.AltEsq = AlturaSubArvore(atual.Esquerda) + 1;
if (atual.Direita == null)
atual.AltDir = 0;
else
atual.AltDir = AlturaSubArvore(atual.Direita) + 1;
atual.Dif = atual.AltDir - atual.AltEsq;
if (atual.AltDir > atual.AltEsq)
return atual.AltDir;
else
return atual.AltEsq;
}
Balanceamento da Árvore (1/2)
public void BalancearArvore(Nodo atual) {
if (raiz == null)
return;
if (atual == null)
atual = raiz;
if (atual.Dif > 1)
{
if (atual.Direita.Dif == -1)
RotacaoDuplaEsquerda(atual);
else
RotacaoEsquerda(atual);
return;
}
Balanceamento da Árvore (2/2)
if (atual.Dif < -1)
{
if (atual.Esquerda.Dif == 1)
RotacaoDuplaDireita(atual);
else
RotacaoDireita(atual);
return;
}
if (atual.Esquerda != null)
BalancearArvore(atual.Esquerda);
if (atual.Direita != null)
BalancearArvore(atual.Direita);
}