Métodos de Programação II (Mestrado Integrado em Engenharia de Comunicações) 1º Ano, 2º Semestre

Métodos Programação II 1

Métodos de Programação II(Mestrado Integrado em Engenharia de Comunicações)

1º Ano, 2º Semestre

Estruturas Hierárquicas (Árvores Binárias)


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.


À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:


• A seguinte árvore:

pode ser representada pela seguinte estrutura:

Àrvores (cont)


Á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.


• 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.

Árvores Binárias (cont)


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.


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.


Implementação da Inserção Ordenadapublic void insord(E novo)

{ if(this.getInfo().less(novo))

if(this.getDir() != null)

this.getDir().insord(novo);

else

{ 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);

}

}

Invocar este método da seguinte forma (exemplo):No Raiz = new No(5);Raiz.insord(3),Raiz.insord(8);Raiz.insord(1);etc.


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.


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);

}

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);}

Invocar o método da seguinte forma (assumindo Raiz como raiz da árvore):E a[] = new E[];int nada = Raiz.pre-ordem(0,a);


Pesquisa numa Árvore Binária• Procurar um elemento numa árvore binária ordenada.

public boolean find(E novo){ if(!novo.equals(this.getInfo()))

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));

elsereturn(false);

elsereturn(true);

}

Invocar o método da seguinte forma (assumindo Raiz como

raiz da árvore):boolean flag = Raiz.find(5);


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.


Eliminação em Árvores Binárias (cont)• Esquematicamente temos as seguintes situações:


public No delete(E novo){ if(!novo.equals(this.getInfo()))

if(novo.less(this.getInfo())){ 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 é

folhareturn(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);

}}

}

Apagar um elemento deuma árvore binária ordenadapreservando a ordem.


// 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

elseinicio.setdir(null); // faz delete a nó temp

return(temp.getinfo());}

Procura menor elemento dasubárvore direita do nó a eliminar, eliminando-o.


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!


• 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.

Árvores na API do Java1.5


Classe TreeSet<E> em Java1.5• Vários construtores

– TreeSet() – TreeSet(Collection<? extends E> c)– TreeSet(Comparator<? super E> c) – TreeSet(SortedSet<E> s)

• 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()• public SortedSet<E> headSet(E toElement) • public SortedSet<E> tailSet(E fromElement) • public E first() • public E last()• public Iterator<E> iterator() • public int size(), • e tudo que herda de Set<E> …

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)

Gera uma subconjunto com todos os elementos menores (maiores) que elemento dado.

Obtém o primeiro (último) elemento da colecção, de acordo com a ordem imposta.

Faz uma travessia (iterator) da colecção seguindo a ordem imposta.

http://www.di.uminho.pt/~pja/mp2/docs/api/java/util/TreeSet.html#TreeSet()

http://www.di.uminho.pt/~pja/mp2/docs/api/java/util/TreeSet.html#TreeSet(java.util.Collection)

http://www.di.uminho.pt/~pja/mp2/docs/api/java/util/Collection.html

http://www.di.uminho.pt/~pja/mp2/docs/api/java/util/TreeSet.html

http://www.di.uminho.pt/~pja/mp2/docs/api/java/util/TreeSet.html#TreeSet(java.util.Comparator)

http://www.di.uminho.pt/~pja/mp2/docs/api/java/util/Comparator.html


http://www.di.uminho.pt/~pja/mp2/docs/api/java/util/TreeSet.html#TreeSet(java.util.SortedSet)

http://www.di.uminho.pt/~pja/mp2/docs/api/java/util/SortedSet.html


http://www.di.uminho.pt/~pja/mp2/docs/api/java/util/AbstractQueue.html

http://www.di.uminho.pt/~pja/mp2/docs/api/java/lang/Object.html

http://www.di.uminho.pt/~pja/mp2/docs/api/java/lang/Object.html








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 de Programação II(Mestrado Integrado em Engenharia de Comunicações)

1º Ano, 2º Semestre

Correspondências chave valor (funções finitas usando maps)


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.


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.


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.


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>


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 chavevalor 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.


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.


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.


hashCode() de Integer, Double, etc• Exemplo de hashCode() da classe:

– Integer: valor inteiro correspondente.– 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 chaveInteger val = planoEsp.get(ponto); // busca valorponto.desloca(x, y); // altera chaveplanoEsp.remove(pontoChave); // remove antigaplanoEsp.put(ponto, val); // insere novo par

Conclusão: Devemos usar chaves que são objectos de classes com

hashCode() bem definidos ou composição destes objectos.


TreeMap<K,V>

• A classe TreeMap<K,V> é usada exactamente da mesma forma que um hashmap mas possui a vantagem de manter os pares chavevalor 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).


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) {

if( p1.getX() < p2.getX() ) return -1;if( p1.getX() > p2.getX() ) return 1;if( p1.getY() < p2.getY() ) return -1;else if(p1.getY() > p2.getY()) return 1; else return 0;

}}

Criação de um treemap de PontoComp usando Comparator:

TreeMap<Ponto, Integer> planoEsp =new TreeMap<Ponto, Integer>(new PontoComp());


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;

Documents

Métodos de Programação II (Mestrado Integrado em Engenharia de Comunicações) 1º Ano, 2º Semestre