Coleções Ordenadas em Java: SortedSet, NavigableSet e TreeSet

SortedSet

A interface SortedSet serve para criar coleções que armazenam elementos de forma ordenada, com ordenação em ordem crescente. Essa interface estende Set, o que significa que a coleção guarda apenas valores únicos. SortedSet oferece métodos como:

• E first(): retorna o primeiro elemento do conjunto.
• E last(): retorna o último elemento do conjunto.
• SortedSet<E> headSet(E end): retorna um objeto SortedSet com todos os elementos do conjunto original até o elemento end, sem incluir end.
• SortedSet<E> subSet(E start, E end): retorna um objeto SortedSet com todos os elementos do conjunto original entre start e end, incluindo start, mas sem incluir end.
• SortedSet<E> tailSet(E start): retorna um objeto SortedSet com todos os elementos do conjunto original a partir de start, incluindo start.

NavigableSet

A interface NavigableSet estende SortedSet e permite extrair elementos com base em seus valores. NavigableSet define métodos como:

• E ceiling(E obj): busca no conjunto o menor elemento e que seja maior ou igual a obj. Caso encontre, retorna esse elemento; caso contrário, retorna null.
• E floor(E obj): busca no conjunto o maior elemento e que seja menor ou igual a obj. Caso encontre, retorna esse elemento; caso contrário, retorna null.
• E higher(E obj): busca no conjunto o menor elemento e que seja maior que obj. Caso encontre, retorna esse elemento; caso contrário, retorna null.
• E lower(E obj): busca no conjunto o maior elemento e que seja menor que obj. Caso encontre, retorna esse elemento; caso contrário, retorna null.
• E pollFirst(): retorna o primeiro elemento e o remove do conjunto.
• E pollLast(): retorna o último elemento e o remove do conjunto.
• NavigableSet<E> descendingSet(): retorna um objeto NavigableSet com todos os elementos do conjunto original em ordem reversa.
• NavigableSet<E> headSet(E upperBound, boolean incl): retorna um objeto NavigableSet com todos os elementos do conjunto original até upperBound. O parâmetro incl, quando true, inclui upperBound no resultado.
• NavigableSet<E> tailSet(E lowerBound, boolean incl): retorna um objeto NavigableSet com todos os elementos do conjunto original a partir de lowerBound. O parâmetro incl, quando true, inclui lowerBound no resultado.
• NavigableSet<E> subSet(E lowerBound, boolean lowerIncl, E upperBound, boolean highIncl): retorna um objeto NavigableSet com todos os elementos do conjunto original de lowerBound até upperBound, com inclusão definida pelos parâmetros lowerIncl e highIncl.

TreeSet

A classe genérica TreeSet<E> representa uma estrutura de dados em forma de árvore, na qual todos os objetos ficam armazenados de forma ordenada em ordem crescente. TreeSet herda de AbstractSet e implementa NavigableSet, o que inclui também SortedSet.

TreeSet possui construtores como:

• TreeSet(): cria uma árvore vazia.
• TreeSet(Collection<? extends E> col): cria uma árvore e adiciona todos os elementos da coleção col.
• TreeSet(SortedSet<E> set): cria uma árvore e adiciona todos os elementos do conjunto ordenado set.
• TreeSet(Comparator<? super E> comparator): cria uma árvore vazia, na qual os elementos adicionados serão ordenados pelo comparador.

TreeSet suporta métodos padrão para inserção e remoção de elementos. No exemplo a seguir, uma TreeSet de strings é criada e elementos são adicionados. Em seguida, o tamanho é exibido, um elemento é removido e os restantes são impressos em um loop for-each. Como os elementos se ordenam automaticamente ao serem inseridos, a saída aparece em ordem crescente.

import java.util.TreeSet;

public class Program{

    public static void main(String[] args) {

        TreeSet<String> states = new TreeSet<String>();

        // adicionamos na lista alguns elementos
        states.add("Germany");
        states.add("France");
        states.add("Italy");
        states.add("Great Britain");

        System.out.printf("TreeSet contains %d elements \n", states.size());

        // remoção de elemento
        states.remove("Germany");
        for(String state : states){

            System.out.println(state);
        }
    }
}

A saída mostra o conjunto ordenado:

TreeSet contains 4 elements
France
Great Britain
Italy

Como TreeSet implementa NavigableSet e, por extensão, SortedSet, métodos dessas interfaces podem ser aplicados. No exemplo abaixo, elementos são adicionados a uma TreeSet e métodos como first, last, subSet, higher, lower, descendingSet, headSet e tailSet são chamados para manipular e exibir subconjuntos ou elementos específicos. Isso demonstra como a estrutura permite acessar partes ordenadas do conjunto de maneira simples.

import java.util.*;

public class Program{

    public static void main(String[] args) {

        TreeSet<String> states = new TreeSet<String>();

        // adicionamos na lista alguns elementos
        states.add("Germany");
        states.add("France");
        states.add("Italy");
        states.add("Spain");
        states.add("Great Britain");

        System.out.println(states.first()); // obtemos o primeiro elemento, o menor
        System.out.println(states.last()); // obtemos o último elemento, o maior

        // obtemos um subconjunto de um elemento até outro
        SortedSet<String> set = states.subSet("Germany", "Italy");
        System.out.println(set);
        // elemento do conjunto maior que o atual
        String greater = states.higher("Germany");
        // elemento do conjunto menor que o atual
        String lower = states.lower("Germany");

        // retornamos o conjunto em ordem reversa
        NavigableSet<String> navSet = states.descendingSet();

        // retornamos o conjunto com todos os elementos menores que o atual
        SortedSet<String> setLower=states.headSet("Germany");

        // retornamos o conjunto com todos os elementos maiores que o atual
        SortedSet<String> setGreater=states.tailSet("Germany");
        System.out.println(navSet);
        System.out.println(setLower);
        System.out.println(setGreater);
    }
}

Resumo

• SortedSet: Interface para coleções ordenadas em ordem crescente, com elementos únicos e métodos para acessar partes do conjunto.
• NavigableSet: Extensão de SortedSet que permite buscas baseadas em valores, como ceiling, floor e subconjuntos inclusivos.
• TreeSet: Classe que implementa NavigableSet em estrutura de árvore, com ordenação automática e construtores para inicialização variada.

📝 Exercícios

Tarefa 1

Descrição: Considere o seguinte TreeSet de números, que já está em ordem: {10, 20, 40, 50}. Qual das chamadas de método abaixo retornaria o valor 20?

// Suponha que este TreeSet já existe:
TreeSet<Integer> numeros = new TreeSet<>(Arrays.asList(10, 20, 40, 50));

Alternativas:

• numeros.higher(20)
• numeros.ceiling(25)
• numeros.floor(25)
• numeros.lower(10)

Tarefa 2

Descrição: Você tem um TreeSet de notas de exames. Use os métodos de NavigableSet para encontrar e imprimir:

1. A maior nota que ainda é considerada "reprovada" (qualquer nota estritamente abaixo de 60).
2. A menor nota que já é considerada "excelente" (qualquer nota maior ou igual a 90).

Código inicial:

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> notas = new TreeSet<>();
        notas.add(88);
        notas.add(55);
        notas.add(92);
        notas.add(75);
        notas.add(49);
        notas.add(98);
        notas.add(65);
        notas.add(90);

        // Encontre a maior nota que é < 60
        Integer maiorNotaReprovado = null; // Seu código aqui

        // Encontre a menor nota que é >= 90
        Integer menorNotaExcelente = null; // Seu código aqui

        System.out.println("Maior nota entre os reprovados (< 60): " + maiorNotaReprovado);
        System.out.println("Menor nota entre os excelentes (>= 90): " + menorNotaExcelente);
    }
}

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> notas = new TreeSet<>();
        notas.add(88);
        notas.add(55);
        notas.add(92);
        notas.add(75);
        notas.add(49);
        notas.add(98);
        notas.add(65);
        notas.add(90);

        // O método lower(E e) retorna o maior elemento estritamente menor que 'e'.
        Integer maiorNotaReprovado = notas.lower(60);

        // O método ceiling(E e) retorna o menor elemento maior ou igual a 'e'.
        Integer menorNotaExcelente = notas.ceiling(90);

        System.out.println("Maior nota entre os reprovados (< 60): " + maiorNotaReprovado);
        System.out.println("Menor nota entre os excelentes (>= 90): " + menorNotaExcelente);
    }
}

Maior nota entre os reprovados (< 60): 55
Menor nota entre os excelentes (>= 90): 90