Árvores
Estruturas de DadosProf. Vilson Heck Junior
INTRODUÇÃOÁrvores
Introdução
• Árvores são estruturas de dadosutilizadas para armazenar e recuperardados de forma rápida e eficiente;
• Árvores não são lineares, ou seja, oselementos não são dispostos em formasequencial;
Introdução
• Árvores são amplamente utilizadas epossuem diversas estratégias deimplementação;
• Cada estratégia tem um conjuntoespecífico de algoritmos paraarmazenamento e recuperação dosdados;
– Árvores genealógicas são análogas àsestruturas de dados árvores.
COMPOSIÇÃOÁrvores
Composição
• As árvores são compostas por:
– Nodos/Nós: são os elementos inseridos emuma á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 seusdescendentes;
• Nodos que não tenham filhos serãochamados de folhas, ou terminais;
• Os demais nodos são ditosintermediários, ou às vezes: galhos.
Composição
• As principais propriedades de cada nodosão:
– Ordem/Grau: Indica o número de filhos queo nodo possui;
– Nível/Altura/Profundidade: Indica adistância do nodo em relação à raiz;
• A árvore também possuí valores de ordem e denível.
– Ambos os valores serão assumidos com base nomaior valor encontrado em qualquer nodo.
A
CB
D FE
G IH J
Nível 0Nó A = Raiz – Ordem 2
Nível 1Nó B = Galho – Ordem 3Nó C = Folha – Ordem 0
Nível 2Nó D = Folha – Ordem 0Nó E = Galho – Ordem 4Nó F = Folha – Ordem 0
Nível 3Nó G = Folha – Ordem 0Nó H = Folha – Ordem 0Nó I = Folha – Ordem 0Nó 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 serchamado de raiz para uma sub-árvore;
• Um Nodo Pai é um nodo conectadodiretamente acima de outro nodo;
• Um Nodo Filho é um nodo conectadodiretamente abaixo de outro nodo;
• Nodos Irmãos compartilham o mesmonodo pai;
Propriedades
• Nodos Ancestrais são todos os nodosque estão acima de um nodo, comligação direta ou indireta;
• Nodos Descendentes são todos os nodosque estão abaixo de um nodo, comligaçã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 aspropriedades vistas anteriormente, porémcom 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áriasde pesquisa”;
Árvores Binárias
– O número máximo de nodos para cada nívelde uma árvore binária é determinada pelaequação:
níveltotal 2
A
CB
D FE G
IH
J
Nível 0Nó A = Raiz – Ordem 2
Nível 1Nó B = Galho – Ordem 2Nó C = Galho – Ordem 2
Nível 2Nó D = Folha – Ordem 0Nó E = Galho – Ordem 2Nó F = Folha – Ordem 0Nó G = Folha – Ordem 0
Nível 3Nó H = Galho – Ordem 1Nó I = Folha – Ordem 0
Árvore Binária: Nível 4 e Ordem 2
Nós / Nodos
Arestas
Níve
l
Ordem
Nível 4Nó J = Folha – Ordem 0
EXEMPLO:
ÁRVORE BINÁRIA EM MDA
Árvores
IMPLEMENTADO ÁRVORES BINÁRIAS
Árvores
Implementando
• Árvores são implementadas comelementos dinâmicos, assim como naslistas encadeadas;
• Nas listas, tínhamos apenas um próximoelemento. Nas árvores, cada elementoterá “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 nodosdela;
– Para inserir um novo elemento, é necessáriodescer a árvore nível por nível até encontrara posição adequada ao novo elemento;
– Para remover um elemento, é necessáriodescer a árvore até encontrar o elemento aser removido;
Implementando
• Vale lembrar das regras maisimportantes de navegação nas árvoresbiná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 osvalores dos nodos visitados;– Se Menor – Esquerda; e
– Se Maior – Direita;
• Quando encontrar um nodo sem filho para olado por onde deveria seguir, insere o novoelemento 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 valoresdos nodos visitados:– Igual – Encontrado!– Menor – Desloca à Esquerda;– Maior – Desloca à Direita;
– Se percorrer toda a árvore sem encontrar:• Não encontrado!
Implementandopublic 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– Sem filhos– 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);
Implementandoprivate 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áriade pesquisa é quando uma sequência denú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ívelaplicar 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 em1962 por Adelson-Velsky e Landis;
• É uma árvore binária de pesquisabalanceada;
• O primeiro diferencial:– cada nodo possuí um campo numérico
indicando a diferença de altura para cadasubá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 0Nó A = Raiz – Ordem 2
Nível 1Nó B = Galho – Ordem 2Nó C = Galho – Ordem 2
Nível 2Nó D = Galho – Ordem 2Nó E = Galho – Ordem 1
Nível 3Nó H = Folha – Ordem 0Nó 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 0Nó A: Dif = -2
Nível 1Nó B: Dif = -1Nó C: Dif = 0
Nível 2Nó D: Dif = 0Nó E: Dif = 0
Nível 3Nó H: Dif = 0Nó I: Dif = 0
Diferenças
Árvores AVL
• Principal Regra:
– Nenhum nodo pode permanecer comdiferença maior de nível em qualquersubárvore maior do que 1:
• 2
• – 2
– Sempre que esta condição não for satisfeita,devem ocorrer rotações na árvore, até queela esteja balanceada, ou seja, comqualquer subárvore
A
CB
D E
IH
Nível 0Nó A: Dif = -2
Nível 1Nó B: Dif = -1Nó C: Dif = 0
Nível 2Nó D: Dif = 0Nó E: Dif = 0
Nível 3Nó H: Dif = 0Nó 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 0Nó A: Dif = -2
Nível 1Nó B: Dif = -1Nó C: Dif = 0
Nível 2Nó D: Dif = 0Nó E: Dif = 0
Nível 3Nó H: Dif = 0Nó 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
EIH
Rotação à Direita
A
C
B
D
EIH
Rotação à Direita
A
C
B
D
EIH
Rotação à Direita
A
C
B
D
EIH
Rotação à Direita
A
C
B
D
EIH
Árvore Binária AVL: Nível 2 e Ordem 2
Nível 0Nó B: Dif = 0
Nível 1Nó D: Dif = 0Nó A: Dif = 0
Nível 2Nó H: Dif = 0Nó I: Dif = 0Nó E: Dif = 0Nó C: Dif = 0
Nível 3
Níve
lOrdem
ROTAÇÕESÁrvores AVL
Rotação Simples à Esquerdaprivate 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 paisaux.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 filhosNodo troca = aux.Esquerda;aux.Esquerda = centro;centro.Direita = troca;return true;
}
Rotação Simples à Direitaprivate 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 paisaux.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 filhosNodo 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 à Direitaprivate 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 Difpublic int AlturaSubArvore(Nodo atual){
if (raiz == null)return 0;
if (atual == null)atual = raiz;
if (atual.Esquerda == null)atual.AltEsq = 0;
elseatual.AltEsq = AlturaSubArvore(atual.Esquerda) + 1;
if (atual.Direita == null)atual.AltDir = 0;
elseatual.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);
elseRotacaoEsquerda(atual);
return;}
Balanceamento da Árvore (2/2)
if (atual.Dif < -1){
if (atual.Esquerda.Dif == 1)RotacaoDuplaDireita(atual);
elseRotacaoDireita(atual);
return;}if (atual.Esquerda != null)
BalancearArvore(atual.Esquerda);if (atual.Direita != null)
BalancearArvore(atual.Direita);}