É encorajado que vão falando com os docentes e outros colegas se tiverem dificuldades. No entanto, qualquer ajuda mais direta que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem. Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota.
Cada aula vale 11% da nota desta componente. Como existem 11 aulas com submissões, pode ter pontuação máxima mesmo sem ter feito tudo.
Para um problema contar tem acertar todos os testes (ou seja, ter accepted). Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.
Para ter 100% bastará sempre resolver os exercícios do guião principal.
Conteúdos das teóricas
Nesta aula iremos abordar conceitos de árvores binárias de pesquisa. Será por isso conveniente ver o que foi falado nas teóricas:
Exercício 1) Compreender Árvores Binárias de Pesquisa
Código de árvores binárias de pesquisa.
Faça download do código dado nas teóricas e compile-o:
BSTree - Árvore binária de pesquisa (ex. métodos: número de nós, altura, contains, inserção e remoção; impressões preorder, inorder, postorder, em largura)
(note que também precisa do código de listas, pilhas e filas, por causa dos métodos de DFS e BFS)
Espreite o ficheiro BSTNode.java para ver como um nó é descrito, e note na assinatura como o tipo T tem de ser comparavél ou seja, implementa o interface Comparable.
Um primeiro teste.
Execute a classe de teste das árvores binárias de pesquisa: $ java TestBSTree
Espreite e acompanhe a implementação do método insert da classe BSTree. Relembre que numa árvore binária de pesquisa, para um qualquer nó, todos os elementos da subárvore esquerda são menores e todos os elementos da subárvore direita são maiores. Para o ajudar a compreender, a imagem seguinte mostra o conteúdo da árvore após cada inserção (em cada passo o elemento inserido está indicada a amarelo):
Depois da remoção de 14, que número ficou na raíz? Acompanhe a implementação do método remove da classe BSTree para verificar como isto é feito.
Visualizando Inserções e remoções.
Procure desenhar no seu caderno como ficaria uma árvore binária de pesquisa depois de inserir os seguintes elementos (por esta ordem): 4 8 1 3 9 2 7 6.
Depois de desenhar, use a seguinte página para verificar se acertou no desenho da árvore:
Experimente retirar e inserir mais alguns elementos, procurando primeiro confirmar como ficaria a árvore, e depois usando a página para confirmar o que previu.
Exercício 2) Um exercício envolvendo árvores binárias de pesquisa
Neste exercício vai pode garantir que percebe como internamente a árvore binária de pesquisa está organizada.
Procure aproveitar as características duma árvore binária de pesquisa
O menor elemento está sempre na folha mais à esquerda
O maior elemento está sempre na folha mais à direita
Exercício 3) Usando árvores binárias de pesquisa para representar conjuntos
Uma árvore binária de pesquisa mapeia muito bem num TAD conjunto. Este exercício pede-lhe precisamente para resolver de forma simples um pequeno problema que na sua essência pode ser resolvido pensando em conjuntos.
Este problema é uma versão simplificada de um problema resolvido nos slides das aulas teóricas (ver slides 70 e 71)
Crie uma árvore binária de pesquisa para guardar strings
Insira as palavras na árvore de pesquisa (método insert()). Os elementos iguais são descartados. Para ler palavras pode usar o método next() da classe Scanner.
No final imprima o número de nós da árvore (método numberNodes())
Exercício 4) Dicionários e for-each
Um TAD dicionário (também conhecido como mapa ou array associativo) é uma estrutura de dados que guarda pares (chave,valor), associando a cada chave um determinado valor. Uma implementação possível é precisamente usar uma árvore binária de pesquisa que usa a chave para decidir a posição na árvore (garantindo que só existe uma cópia de cada chave).
Código de dicionários
Faça download do código dado nas teóricas e compile-o:
BSTMap - Dicionário de pares (chave,valor) implementado com árvores binárias de pesquisas (ex. métodos: put, get e keys)
Espreite o ficheiro BSTMapNode.java para ver como um nó é descrito, e note na assinatura como o tipo K (a chave) tem de ser comparável, mas o tipo V não (o valor).
Um primeiro teste.
Execute a classe de teste dos dicionários: $ java TestBSTMap
Espreite e acompanhe a implementação do método put da classe BSTMap, muito semelhante ao insert de uma árvore binária de pesquisa normal. Note também a assinatura dos principais métodos e o que fazem (get, put, remove e keys). Veja também como são percorridas as chaves do mapa (que são devolvidas numa lista ligada de Java). De um modo geral, quanto temos algo iterável no Java, podemos usar a sintaxe for-each:
for (TipoElemento variavel : Sequencia) {
InstrucoesCiclo
}
Um exemplo seria algo como:
importjava.util.LinkedList;importjava.util.TreeSet;importjava.util.Set;publicclassTestForEach{publicstaticvoidmain(String[] args){// Criação de Lista Ligada usando a estrutura de dados do próprio Java// Exemplo de inicialização usando sintaxe "diamond" (<>). Se não// colocarmos o tipo no construtor, o Java consegue inferir qual é// olhando para a variável que estamos a inicializar
LinkedList<String> list =new LinkedList<>();// Adicionando algumas strings à lista ligada
list.addLast("testing");
list.addLast("just");
list.addLast("for");
list.addLast("fun");// Para percorrer a lista podemos usar um for-eachfor(String s : list)
System.out.println(s);// Qualquer TAD iterável pode ser usado com um for each// Aqui fica um exemplo com... conjuntos (interface Set)// TreeSet implementa um conjunto usando árvores binárias de pesquisa
Set<Integer> set =new TreeSet<>();
set.add(42);
set.add(24);
set.add(0);// Podemos usar int por causa do autounboxingfor(int i : set)
System.out.println(i);}}
Um pequeno exercício para usar dicionários
Resolva e submeta o problema [ED172] Contagem de palavras, usando como estrutura de dados base um BSTMap.
Este problema é semelhante a problema resolvido nos slides das aulas teóricas (ver slide 79 do capítulo 7)
Crie um dicionario do tipo <String,Integer>
Para ler as palavras use os métodos hasNext() (para saber se ainda existem palavras para ler) e next() (para ler a próxima palavra)
Para cada palavra lida:
Se a palavra ainda não existe no dicionário (usar método get()), então colocá-la no dicionário com valor igual a 1 (usar método put())
Se palavra já existe, incrementar o seu valor (usar método get() para ler valor e depois método put() para actualizar o valor)
No final é só percorrer a lista de chaves (método keys()) usando um for-each e imprimir os valores. Como é uma árvore binária de pesquisa e o keys é feito inorder, as chaves já vêm por ordem alfabética.
Exercícios extra para consolidação de conhecimentos
Para consolidar os seus conhecimentos sobre como percorrer internamente uma árvore de pesquisa, resolva s submeta o seguinte problema:
Para que um nó x esteja entre a e b, quais devem ser os resultados de x.compareTo(a) e x.compareTo(b)?
Use recursividade para procurar os elementos por toda a árvore
Procure aproveitar as características duma árvore binária de pesquisa: por vezes sabemos que todo um ramo não está contido no intervalo (ex: se x é menor que a, então todo a subárvore esquerda não pertence ao intervalo, pois são elementos menores que x)
Para garantir que percebe as condições necessárias para uma árvore binária ser de pesquisa, resolva e submeta o seguinte problema:
Uma árvore é de pesquisa se ambas as suas subárvores também o são.
Em cada nó, deve verificar se este é válido, ou seja:
Se todos os nós da subárvore esquerda são menores que o nó atual
Se todos os nós da subárvore direita são maiores que o nó atual
Cuidado! Não pode usar directamente os métodos anteriores de máximo e mínimo, pois se a árvore não for binária de pesquisa não é garantido que o mínimo e máximo estejam nessas posições.
Para consolidar os seus conhecimentos sobre o uso de árvores binárias de pesquisa como TAD conjunto, resolva e submeta o seguinte problema:
Crie uma árvore binária de pesquisa para guardar inteiros
Depois de ler os números, passe por todas as somas possiveis (combinações dois a dois - basta fazer dois ciclos) e guarde-as na árvore (método insert()). Note que as somas iguais a anteriores são descartadas (a árvore guarda apenas uma cópia de cada número)
Para responder a cada pergunta basta verificar se o número em causa está ou não contido na árvore (método contains())
Exercício de Desafio
Para esta semana vou colocar um exercício que envolve árvores mas também eficiência algorítmica. É um problema da minha autoria que que foi usado nas Olimpíadas de Informática:
O limite de tempo de execução para cada caso de teste é de 1 segundo, pelo que a solução só será aceite e com pontuação máxima no Mooshak se for eficiente. Não será por isso possível para cada pergunta simular realmente todas as bolas a cair até chegar n-ésima bola.
Para estes problemas de desafio não vou dar logo dicas, para vos deixar pensar, mas se quiserem mesmo resolver o problema e não estejam a conseguir (mesmo depois de terem realmente tentado), podem falar comigo para obter pistas, ou ter uma ideia de como os "atacar".