Métodos de Programação II
(Mestrado Integrado em Engenharia de Comunicações)
1º Ano, 2º Semestre
Estruturas Hierárquicas
(Árvores Binárias)
Métodos Programação II
1
Estruturas Hierárquicas
(Árvores)
• Esta estrutura de dados é das mais usadas e das mais
importantes em computação. É usada em múltiplas
aplicações como no representação dos movimentos de
um jogador num jogo (e.g. damas, xadrez, etc), na
pesquisa de informação (bases de dados, etc) e em
geral quando temos de representar qualquer tipo de
informação hierarquizada.
• Podemos representar árvores na forma sequencial
(através de arrays) e na forma dinâmica (através de
estruturas ligadas). Nestas aulas vamos adoptar a
última.
Métodos Programação II
2
Àrvores
• Uma árvore é uma estrutura que pode ser vazia ou
então tem um nó (célula) raiz. Esse nó tem associado
nós filhos. No caso especial das árvores binárias, cada
nó tem no máximo dois filhos. No caso geral, cada nó
pode ser representado pela seguinte célula:
Métodos Programação II
3
Àrvores (cont)
• A seguinte árvore:
pode ser representada pela seguinte estrutura:
Métodos Programação II
4
Árvores Binárias
• Em geral, podemos trabalhar com árvores mais simples
(árvores binárias). Estas são constituídas por nós que
têm no máximo dois sucessores. Podemos usar a
mesma célula que usamos nas listas duplamentes
ligadas para representar nós de uma árvore binária.
Neste caso, em vez de as ligações apontarem para os
nós antecessores e sucessores, ambas indicam os
sucessores na hierarquia.
Métodos Programação II
5
Árvores Binárias (cont)
• Este tipo de árvores tem um enorme potencial de
representação. As operações sobre estas árvores são
também mais simples e eficientes.
• Uma árvore binária tem sempre um nó raiz (que pode
ser vazio indicando que a árvore é vazia). Cada nó raiz
refere para duas sub-árvores (à sua esquerda e à
direita).
• Os nós que não são raiz são chamados nós internos. Os
nós terminais da árvore são chamados nós folhas. Uma
forma interessante de reconhecer que a nossa estrutura
de dados é uma árvore é que há sempre um caminho
único na árvore entre a raiz e as folhas!
• As árvores binárias são estruturas extremamente
eficientes para guardar informação que vai ser
intensamente pesquisada.
Métodos Programação II
6
Implementação & Operações
• Nó de uma árvore binária. A classe é a mesma que
Celula2 (mudando os nomes de ant e prox para esq e dir).
Chamamos No a esta class. Temos assim os métodos
getEsq() e setEsq(), etc.
• Estas estruturas oferecem um enorme potencial para
armazenar informação ordenada que se pretende
pesquisar intensamente e eficientemente. Uma
operação importante é a inserção ordenada de novos
elementos na árvore.
• O princípio é simples. Para um dado nó, os elementos à
sua esquerda são sempre menores e os elementos à
sua direita são sempre maiores.
Métodos Programação II
7
Inserção Ordenada
• Se pretendermos inserir um novo elemento, percorremos a árvore
desde o nó raiz até se encontrar um nó folha. A decisão de
prosseguir pela sub-árvore esquerda ou direita de um nó é
comandada pelo princípio anteriormente descrito (esquerda
menores, direita maiores).
Inserção é então um processo
recursivo simples de comparação
entre nó a inserir (novo) e o nó
onde estamos durante a travessia.
Quando um nó folha é
encontrado, o nó a inserir passa
a ser o filho à sua esquerda
(direita) se o novo nó for menor
(maior) que ele.
Métodos Programação II
8
Implementação da Inserção Ordenada
public void insord(E novo)
{ if(this.getInfo().less(novo))
Invocar este método da
seguinte forma (exemplo):
if(this.getDir() != null)
No Raiz = new No(5);
Raiz.insord(3),
this.getDir().insord(novo);
Raiz.insord(8);
Raiz.insord(1);
else
etc.
{
No n = new No(novo);
this.setDir(n);
}
else
if(!novo.equals(this.getInfo())) // não há repetidos!
if(this.getEsq() != null)
this.getEsq().insord(novo);
else
{
No n = new No(novo);
this.setEsq(n);
}
Métodos Programação II
9
Travessias em Árvores Binárias
• Pré-ordem (raiz, sub-árvore esquerda, sub-árvore direita)
– [* 3 / 5 7]
• In-ordem (sub-árvore esquerda, raiz, sub-árvore direita)
– [ 3 * 5 / 7]
• Pós-ordem (sub-árvore esquerda, sub-árvore direita, raiz)
– [ 3 5 7 / *]
• Numa árvore ordenada, para se obter a sequência ordenada, a
travessia tem de ser in-ordem!
• No caso de pesquisas de elementos numa árvore ordenada a
travessia é comandada pelo teste nos nós raiz de cada sub-árvore.
Métodos Programação II
10
Travessias (implementação)
•
Nestes métodos é fornecido um array, para conter a sequência com a
ordem que reflecte a travessia, e a próxima posição a utilizar.
public int pre-ordem(int index, E a[])
{ a[index++] = this.getInfo();
if(this.getEsq() != null)
index = this.getEsq().pre-ordem(index,a);
if(this.getDir() != null)
index = this.getDir().pre-ordem(index,a);
return(index);
}
public int in-ordem(int index, E a[])
{
if(this.getEsq() != null)
index = this.getEsq().in-ordem(index,a);
a[index++] = this.getInfo();
if(this.getDir() != null)
index = this.getDir().in-ordem(index,a);
return(index);
}
Métodos Programação II
Invocar o método da seguinte forma
(assumindo Raiz como raiz da árvore):
E a[] = new E[];
int nada = Raiz.pre-ordem(0,a);
public int pos-ordem(int index, E a[])
{
if(this.getEsq() != null)
index = this.getEsq().pos-ordem(index,a);
if(this.getDir() != null)
index = this.getDir().pos-ordem(index,a);
a[index++] = this.getInfo();
return(index);
}
11
Pesquisa numa Árvore Binária
• Procurar um elemento numa árvore binária ordenada.
Invocar o método da seguinte
public boolean find(E novo)
forma (assumindo Raiz como
{ if(!novo.equals(this.getInfo()))
raiz da árvore):
boolean flag = Raiz.find(5);
if(novo.less(this.getInfo()))
if(this.getEsq() != null)
return(this.getEsq().find(novo));
else
return(false);
else
if(this.getDir() != null)
return(this.getDir().find(novo));
else
return(false);
else
return(true);
}
Métodos Programação II
12
Eliminação em Árvores Binárias Ordenadas
• O problema que se coloca é que após a eliminação de
um elemento na árvore, queremos preservar a ordem da
sequência da árvore. Como estas são árvores de
pesquisa, temos primeiro de encontrar e eliminar o
elemento em questão e posteriormente reconstruir a
ordem.
• Três casos a ter em conta:
– Nó a eliminar é folha: caso simples de eliminação directa,
– Nó tem só um filho: o filho substitui o pai!
– Nó tem dois filhos: substituir nó a eliminar pelo nó com o valor
mais baixo da sua sub-árvore direita.
Métodos Programação II
13
Eliminação em Árvores Binárias (cont)
• Esquematicamente temos as seguintes situações:
Métodos Programação II
14
public No delete(E novo)
Apagar um elemento de
{
if(!novo.equals(this.getInfo()))
uma árvore binária ordenada
if(novo.less(this.getInfo()))
preservando a ordem.
{
if(this.getEsq() != null)
this.setesq(this.getEsq().delete(novo));
return(this);
}
else
{
if(this.getDir() != null)
this.setdir(this.getDir().delete(novo));
return(this);
}
else
// Sucesso…
{
if(this.getesq() == null && this.getdir() == null) // nó a fazer delete é folha
return(null);
// no tem um só filho!
if(this.getesq() != null && this.getdir() == null)
return(this.getesq());
if(this.getesq() == null && this.getdir() != null)
return(this.getdir());
if(this.getesq() != null && this.getdir() != null) // nó é raiz duma subárvore n. vazia!
{
E temp = this.delete_menor();
this.setinfo(temp);
return(this);
}
}
}
Métodos Programação II
15
Procura menor elemento da
subárvore direita do nó a
eliminar, eliminando-o.
// procura menor elemento da subárvore direita e elimina.
private E delete_menor()
{
No inicio = this;
No temp = this.getdir(); // vai para o lado direito procurar menor
while(temp != null && temp.getesq() != null)
{
inicio = temp;
temp = temp.getesq();
}
if(this != inicio)
// this só tem 1 filho??
inicio.setesq(null); // faz delete a nó temp
else
inicio.setdir(null); // faz delete a nó temp
return(temp.getinfo());
}
Métodos Programação II
16
Balanceamento de Árvores Binárias
• Pesquisar o elemento 10 requer 5 comparações na árvore esquerda
e 2 na direita (ambas representam a mesma sequência)
• O problema surge com o desequilíbrio da árvore esquerda. As
árvores AVL resolvem este problema balanceando os ramos da
árvore após cada inserção.
• A segunda árvore está balanceada: isto é, para cada nó, o ramo de
maior tamanho de cada uma das suas sub-árvores difere no
máximo de 1 unidade!
Métodos Programação II
17
Árvores na API do Java1.5
• As colecções do tipo Set<E> são implementações de conjuntos de
objectos, pelo que os seus elementos não são indexados ou acessíveis
por índice, nem podem ocorrer em duplicado (referem-se à noção
matemática de conjunto).
•As implementações Tree são organizações dos dados que implicam
uma ordem, contrastando com as Hash.
Métodos Programação II
18
Classe TreeSet<E> em Java1.5
• Vários construtores
– TreeSet()
– TreeSet(Collection<? extends E> c)
– TreeSet(Comparator<? super E> c)
– TreeSet(SortedSet<E> s)
•
•
•
•
•
•
•
•
•
•
•
•
Comparator é uma interface onde está
definida uma função de comparação
que impõe uma ordem total sobre os
elementos da colecção.
Gera um subconjunto com
os elementos entre os dois
parâmetros dados. SortedSet
é uma interface (ver API)
public boolean add(E o)
public boolean contains(Object o)
public boolean remove(Object o)
public SortedSet<E> subSet(E fromElement, E toElement)
public void clear()
Gera uma subconjunto com
public SortedSet<E> headSet(E toElement)
todos os elementos menores
(maiores) que elemento dado.
public SortedSet<E> tailSet(E fromElement)
public E first()
Obtém o primeiro (último) elemento da
public E last()
colecção, de acordo com a ordem imposta.
public Iterator<E> iterator()
public int size(),
Faz uma travessia (iterator) da colecção
seguindo a ordem imposta.
e tudo que herda de Set<E> …
Métodos Programação II
19
Exercícios
• Escreva um método que dada uma sequência de inteiros produz
uma heap. Uma heap é uma árvore binária de inteiros em que
nenhum nó filho tem valor superior ao valor contido no seu pai.
• Desenvolva um método que produz um array com os elementos de
um determinado nível de uma árvore binária.
• Escreva um programa que compile (traduza) uma expressão
aritmética (só com as operações básicas +, −, *, /) numa linguagem
máquina com as operações básicas (add, sub, mul, div) e com a
operação load, de carregamento de um valor para um registo
máquina. A expressão deve ser lida e inserida numa árvore binária.
Depois, através de uma travessia pós-ordem, a expressão é
traduzida para a respectiva linguagem máquina. Assuma que não
há limite de registos máquina disponíveis! A árvore usada nas
nossas travessias da página 10 é traduzida no seguinte código:
[load, 1, 3], [load, 2, 5], [load, 3, 7], [div, 2, 3], [mul, 1, 2]
Métodos Programação II
20
Métodos de Programação II
(Mestrado Integrado em Engenharia de Comunicações)
1º Ano, 2º Semestre
Correspondências chave  valor
(funções finitas usando maps)
Métodos Programação II
21
Maps
• Os mappings, que são correspondências unívocas um
para um entre objectos (representando funções
matemáticas finitas), em geral correspondências do tipo
chave  valor, em que as chaves são o domínio e são
um conjunto (logo, não havendo chaves em duplicado).
A correspondência é apenas unívoca, porque a chaves
diferentes pode ser feito corresponder o mesmo valor.
• São estruturas de dados ideais para representar
informação de intensiva inserção e pesquisa mas com
poucas eliminações.
• Introduz a noção de chave única, conceito fundamental
em informática: identificador de uma entidade e veículo
de acesso a ela. Exemplos: nº de BI, nº de contribuinte,
nº de aluno, são chaves únicas que estão associadas
univocamente a grupos de dados particulares.
Métodos Programação II
22
Maps
• Um mapping é a representação de uma função
matemática que estabelece uma qualquer
correspondência entre um conjunto de chaves (keys) e
um grupo de valores (values).
• A procura de informação num map (dado uma chave)
tem tempo de acesso constante, isto porque a chave
traduz-se na posição onde está armazenada e
consequentemente acesso directo ao valor.
Tipicamente, a posição é obtida por aplicação de uma
função de hash à própria chave.
Métodos Programação II
23
Maps (2)
• Qualquer map tem as seguintes propriedades:
– São a correspondência entre uma chave e um valor
–
–
–
–
(1 para 1);
As chaves são únicas e formam um conjunto;
os valores podem ser em duplicado, isto é, duas
chaves distintas podem ter o mesmo valor (ex.: duas
cidades distintas com a mesma população) mas o
valor não é partilhado, pelo que são duas
correspondências (designadas pares) distintas;
As remoções de um map removem sempre pares
chave  valor e não apenas as chaves (muitas
remoções podem provocar a necessidade de
operações de rehashing, que são
computacionalmente caras);
Não há qualquer ordem definida sobre chaves ou
pares.
Métodos Programação II
24
Classes map do Java1.5
• Existem actualmente quatro implementações
gerais de Map<K,V>, designadamente:
– HashMap<K,V> (baseada em tabela de hash);
– LinkedHashMap<K,V> (tabela de hash e lista ligada);
– TreeMap<K,V> (árvore balanceada para ordenação
das chaves);
– EnumMap<K,V> (representação bit-based para tipos
enumerados)
– Hashtable<K,V> (baseada em tabela de hash, para
concorrência).
• Vamos ver em mais detalhe as classes
HashMap<K,V> e TreeMap<K,V>
Métodos Programação II
25
HashMap<K,V>
• A classe HashMap<K,V> corresponde a uma implementação de
maps numa tabela de hash, com optimizações automáticas de
espaço e carga, e algoritmos sofisticados para associar de forma
eficaz chaves a valores.
• Numa tabela de hash implementa-se uma função de hash para
traduzir a chave numa posição de memória na lista de chaves. Esta
depende do tipo de dado representativo das chaves.
• Na HashMap a função de hash é implementada no método hasCode()
da classe representativa da chave e.g. String, Integer, etc.
• Construtores: HashMap(); e HashMap(map<K,V> m);
• O método que permite inserir pares chavevalor num hashmap é o
método put(k,v). Dada uma chave k de tipo K e um valor v de tipo
V, insere o par no map receptor.
• O método V get(Object key) devolve o valor associado à chave
dada como parâmetro, ou null se a chave não existir.
Métodos Programação II
26
HashMap<K,V> (cont)
• O método containsKey(Object k) devolve true se o map
receptor tem o objecto k como chave e se tal chave esta
associada a algum valor.
• O método containsValue(Object v) devolve o valor true se
esse valor esta associado a alguma chave.
• Temos disponíveis os seguintes iteradores:
– keySet() que devolve uma “visão” sob a forma ou tipo de um
Set<K> das chaves do map receptor, permitindo que, através de
um foreach estas possam ser de imediato iteradas(enumeradas);
– o método values() devolve uma “visão” Collection<V> sobre os
valores (pois estes podem estar em duplicado), que também
pode ser iterada de imediato.
• O método remove(Object k) remove a associação que
tem k por chave deste map, devolvendo o valor
associado a k, caso k exista, ou null, no caso contrário.
Métodos Programação II
27
Funções de hash via hashCode()
• O método hashCode() é herdade do Object e deve ser
redefinido nas classes das nossas chaves.
• Propriedade de unicidade dos códigos:
Se x.equals(y) == true então x.hashCode() == y.hashCode()
• Exemplo de hashCode() da classe String:
– s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
• Onde s[i] é o caracter da posição i na String, n é o
tamanho da String, e ^ indica exponenciação. (O valor
da função de hash para uma String vazia é zero.)
• O valor retornado é o endereço da chave.
Métodos Programação II
28
hashCode() de Integer, Double, etc
• Exemplo de hashCode() da classe:
– Integer: valor inteiro correspondente.
Conclusão: Devemos usar chaves
que são objectos de classes com
hashCode() bem definidos ou
composição destes objectos.
– Double: (int) (v >>>32)
sendo v = Double.doubleToLongBits(this.doubleValue());
• Modificação de chaves:
– Não se devem alterar valores de chaves mantendo-as na sua
localização original, pois esta localização pode não
corresponder à localização que lhes seria atribuída pela função
de hash. A solução correcta será, nestes casos, obter a chave,
fazer o seu clone(), fazer get() do respectivo valor, alterar de
seguida a copia da chave, remover a chave antiga e inserir a
nova associação, tal como se mostra no código seguinte:
Ponto ponto = pontoChave.clone(); // copia a chave
Integer val = planoEsp.get(ponto); // busca valor
ponto.desloca(x, y); // altera chave
planoEsp.remove(pontoChave); // remove antiga
planoEsp.put(ponto, val); // insere novo par
Métodos Programação II
29
TreeMap<K,V>
• A classe TreeMap<K,V> é usada exactamente da
mesma forma que um hashmap mas possui a vantagem
de manter os pares chavevalor guardados pela ordem
crescente das suas chaves, ordem essa predefinida ou
não em função do tipo das chaves.
• As chaves de tipos mais comuns, como String e Integer,
são ordenadas segundo a sua “ordem natural”. Para
outros tipos mais complexos, em especial classes
definidas pelo utilizador, este deverá fornecer o método
de comparação de chaves como parâmetro do
construtor TreeMap<K,V>(Comparator<? super K> c).
Métodos Programação II
30
Uso do interface Comparator<K>
• Exemplo de um ponto que implementa Comparator<K>:
import java.util.Comparator;
import java.io.Serializable;
public class PontoComp implements Comparator<Ponto>, Serializable
{
public int compare(Ponto p1, Ponto p2)
Criação de um treemap de
{
usando Comparator:
if( p1.getX() < p2.getX() ) return -1; PontoComp
TreeMap<Ponto, Integer> planoEsp =
if( p1.getX() > p2.getX() ) return 1; new TreeMap<Ponto, Integer>(new PontoComp());
if( p1.getY() < p2.getY() ) return -1;
else
if(p1.getY() > p2.getY()) return 1;
else return 0;
}
}
Métodos Programação II
31
Exercícios
• Alterar a classe GereEstufas por forma a guardar as estufas na
forma de um map (correspondência código  info de Estufa).
• Cada e-mail recebido numa dada conta de mail é guardado
contendo o endereço de quem o enviou, a data de envio, a data de
recepção, o assunto e o texto do mail (não se consideram anexos,
etc.). Crie uma classe MailMap que associe a cada endereço de
envio todos os mails recebidos (cf. classe Mail) e implemente as
seguintes operações:
–
–
–
–
–
–
–
–
–
–
Determinar o total de endereços a partir dos quais se recebeu mail;
Guardar um novo mail recebido;
Determinar quantos mails têm por origem um dado endereço;
Criar uma lista com todos os endereços que enviaram mails contendo no seu
assunto uma lista de palavras dada como parâmetro;
O mesmo que a questão anterior, mas criando um conjunto contendo os mails;
Eliminar todos os e-mails recebidos antes de uma data que é dada como
parâmetro;
Criar uma lista dos endereços que hoje enviaram mails;
Dada uma lista de palavras, eliminar todos os mails de um dado endereço que
no seu assunto contenham uma qualquer destas (anti-spam);
Eliminar todos os mails de um dado endereço anteriores a uma data dada;
Criar uma listagem com todos os endereços de mail oriundos de Portugal;
Métodos Programação II
32