Estruturas de Dados 2020/2021 (CC1007) - DCC/FCUP

Aula Prática #13 - Árvores Binárias de Pesquisa
(semana de 31/05 a 04/06)

Exercícios para submissão

Para efeitos da nota atribuída à resolução de exercícios ao longo do semestre, os exercícios que pode submeter desta aula são:

Prazo de submissão: 12 de Junho (submeter no Mooshak de EDados)

É 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 10% da nota desta componente. Como existem 12 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 o interface Comparable

Em Java, a maneira padrão de impor uma ordem entre objectos do mesmo tipo e permitir a comparação de dois objectos é usar o interface Comparable, que determina que a classe em questão deve implementar o método compareTo(). Se tivermos dois objectos o1 e o2 do mesmo tipo, então uma chamada a o1.compareTo(o2) deve devolver:

Este exercício vai permitir-lhe explorar um pouco este interface.

  1. Usando o método compareTo().
    Compile e execute o seguinte programa, verificando o output. 
    // Testando o metodo compareTo()
class TestCompare {
   public static void main(String[] args) {

      String s1 = "ana";
      String s2 = "carlos";
      String s3 = "adalberto";
      System.out.println("s1.compareTo(s1) = " + s1.compareTo(s1));
      System.out.println("s1.compareTo(s2) = " + s1.compareTo(s2));
      System.out.println("s1.compareTo(s3) = " + s1.compareTo(s3));

      System.out.println();

      Integer i1 = 23;
      Integer i2 = 10;
      Integer i3 = 42;
      System.out.println("i1.compareTo(i2) = " + i1.compareTo(i2));
      System.out.println("i1.compareTo(i3) = " + i1.compareTo(i3));
   }
}
     
  2. Métodos que usam o interface Comparable.
    Alguns métodos do Java usam o interface Comparable para poder comparar objectos. Um exemplo é o Arrays.sort, que permite ordenar um array de objectos "comparáveis".

    3. Para ver um exemplo, compile e execute o seguinte programa, verificando o output: 

    import java.util.Arrays;

// Testando o metodo Arrays.sort()
class TestSort {
   public static void main(String[] args) {
      // Inicializar array v
      String[] v = {"ana","carlos","adalberto","maria","luis","filipa"};

      // Ordenar array v
      Arrays.sort(v);

      // Se fosse escrito diretamente v, apenas seria mostrada a sua referência
      System.out.println(Arrays.toString(v));
   }
}
     
  3. Uma classe customizada com comparador. Compile e execute o seguinte pedaço de código, que tem como intuito imprimir uma tabela classificativa de equipas de futebol: 
    import java.util.Arrays;

// Classe para representar uma equipa
class Team {
   String name;
   int points;

   // Construtor
   Team(String n, int p) {
      name = n;
      points = p;
   }

   // Método para dar representação em String de um objecto da classe
   public String toString() {
      return "(" + name + "," + points + ")";
   }
}

// Testando o método Arrays.sort()
class TestTeams {
   public static void main(String[] args) {
      // Inicializar array v
      Team[] v = new Team[7];

      v[0] = new Team("Leicester", 20);
      v[1] = new Team("Chelsea", 31);
      v[2] = new Team("Arsenal", 20);
      v[3] = new Team("Liverpool", 42);
      v[4] = new Team("Man United", 37);
      v[5] = new Team("Man City", 20);
      v[6] = new Team("Tottenham", 39);
      
      // Ordenar e escrever array v
      Arrays.sort(v);
      System.out.println(Arrays.toString(v));
   }
}
     
  4. Indicando que se pretende implementar o comparador.
    Altere a linha class Team para class Team implements Comparable<Team> e recompile. Que erros de compilaçao obtém agora?
  5. Implementando um comparador.
    Adicione o seguinte código dentro da classe Team:
    public int compareTo(Team t) {
       return name.compareTo(t.name);
    }
    Recompile, execute e verifique o output.
  6. Corrigindo o comparador.
    Corrija a implementação do comparador para que a ordenação venha por ordem decrescente de pontuação, e em caso de empate por ordem alfabética crescente. Recompile e execute para testar.

Exercício 2) Compreender Árvores Binárias de Pesquisa

  1. Código de árvores binárias de pesquisa.
    Faça download do código dado nas teóricas e compile-o:

    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.

  2. 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):


     
  3. 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 3) 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.


  1. Descobrindo o mínimo e o máximo.
    Resolva e submeta o problema [ED208] Minímo e máximo

Exercício 5) 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.


  1. Resolva e submeta o problema [ED164] Quantas palavras?

Exercício 1) 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).

  1. Código de dicionários
    Faça download do código de dado nas teóricas e compile-o:

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

  2. 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:


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

Exercícios extra para consolidação de conhecimentos

  1. Para consolidar os seus conhecimentos do interface Comparable, resolva e submeta o seguinte problema (disponível no volume de árvores), que é uma extensão do exercício 1 desta aula:.
  2. Para consolidar os seus conhecimentos sobre como percorrer internamente uma árvore de pesquisa, resolva s submeta o seguinte problema:
  3. Para garantir que percebe as condições necessárias para uma árvore binária ser de pesquisa, resolva e submeta o seguinte problema:
  4. Para consolidar os seus conhecimentos sobre o uso de árvores binárias de pesquisa como TAD conjunto, resolva e submeta o seguinte problema:

Exercícios extra de treino para o 2º teste prático

Para o ajudar a preparar o 2º teste prático (8 de Junho), estão também disponíveis para submissão os quatro problemas usados no teste prático equivalente de 19/20 (a estrutura e objetivos do teste eram muito semelhantes):

Estão também disponíveis dois problemas que foram usados para uma submissão com tempo mais alargado no ano passado:

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

Pedro Ribeiro (DCC/FCUP) / Última actualização: