Estruturas de Dados 2018/2019 (CC1007) - DCC/FCUP

Aula Prática #12 - Árvores Binárias de Pesquisa e Conjuntos
(semana de 18/05 a 22/05)

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 = new Integer(23);
      Integer i2 = new Integer(10);
      Integer i3 = new Integer(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) Alguns exercícios com árvores binárias de pesquisa

  1. Descobrindo o mínimo e o máximo.
    Resolva e submeta o problema [ED208] Minímo e máximo
  2. Contando nós.
    Resolva e submeta o problema [ED209] Intervalo de valores

Exercício 4) 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 dois pequenos problemas que na sua essência pode ser resolvidos pensando em conjuntos.

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

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 garantir que percebe as condições necessárioas para uma árvore binária ser de pesquisa, resolva e submeta o seguinte problema:
  3. Para consolidar os seus conhecimentos sobre a árvores binárias de pesquisa, sugerimos que explore a altura de uma árvore binária de pesquisa com dados aleatórios. O seguinte pedaço de código gera 20 árvores binárias de pesquisa com 100 000 valores aleatórios entre 0 e 109-1. Antes de executar, procure ter uma ideia da ordem de grandeza da altura que vai encontrar. Depois de estimar, compile e execute para verificar se acertou na magnitude do valor.

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: