Java TreeSet

TreeSet<E> é a implementação de Set que mantém seus elementos ordenados. É suportado por uma árvore rubro-negra (a mesma árvore binária de busca balanceada que suporta o TreeMap internamente), portanto toda operação — add, remove, contains, first, last, consultas por intervalo — é O(log n). Isso é mais lento que O(1) do HashSet, mas você obtém algo que o HashSet não consegue oferecer: um iterador ordenado, o menor elemento sob demanda, e a capacidade de perguntar "todas as tags entre a e m."

TreeSet implementa a interface mais rica NavigableSet<E> (que estende SortedSet<E>), portanto todas as consultas por intervalo e por vizinhança estão na própria classe, não enterradas em utilitários do Collections. Se você ainda não conhece o contrato base, leia primeiro o capítulo sobre a interface Set — tudo que está lá (sem duplicatas, add retorna false em repetição) ainda se aplica.

Duas formas de definir a ordem

Um TreeSet precisa de alguma forma de comparar elementos. Há duas:

1. Ordenação natural — o tipo de elemento implementa Comparable<E>. String, Integer, LocalDate, todo wrapper, todo enum, todo record que você escreva implementando Comparable. O construtor sem argumentos new TreeSet<>() usa isso.
2. Um Comparator<E> que você fornece — passe um para o construtor. O conjunto usa seu comparador para cada comparação.

Set<String> caseInsensitive = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
caseInsensitive.add("Banana");
caseInsensitive.add("apple");
caseInsensitive.add("BANANA");   // equals "Banana" by this comparator → not added
System.out.println(caseInsensitive); // [apple, Banana]

O segundo exemplo é importante. TreeSet decide "igual" quando compareTo retorna 0, não por equals. Duas strings que a ordenação natural diz serem diferentes, mas que um comparador diz serem iguais, serão colapsadas em um único elemento. Isso é quase sempre o que você quer — mas é uma armadilha se você não percebeu.

A API NavigableSet

Um TreeSet expõe operações que um Set simples não consegue fazer:

TreeSet<Integer> t = new TreeSet<>(List.of(10, 20, 30, 40, 50));
t.first();          // 10  — smallest
t.last();           // 50  — largest
t.lower(30);        // 20  — strictly less than 30
t.floor(30);        // 30  — ≤ 30
t.higher(30);       // 40  — strictly greater than 30
t.ceiling(30);      // 30  — ≥ 30
t.pollFirst();      // 10, removes
t.pollLast();       // 50, removes
t.headSet(30);      // {10, 20}        — strictly less than 30
t.tailSet(30);      // {30, 40, 50}    — ≥ 30
t.subSet(20, 40);   // {20, 30}        — [20, 40)
t.descendingSet();  // a reverse-order view

Essas são as operações que justificam o custo O(log n): um HashSet não consegue fazer nenhuma delas sem ordenar o conjunto inteiro primeiro. Se você precisar de qualquer uma delas, TreeSet é a escolha certa.

Sem nulls

Um TreeSet não pode conter null porque precisaria comparar null com os outros elementos, e compareTo(null) lança NullPointerException. O conjunto lança na primeira inserção. Se você precisar de um sentinela, use um valor diferente do tipo de elemento — Integer.MIN_VALUE, uma String vazia, ou um marcador dedicado em um enum.

Mutar elementos é proibido (mesma armadilha do HashSet)

O TreeSet decide o posicionamento no momento da inserção chamando compareTo (ou seu Comparator). Se você mutar um elemento após a inserção de forma que altere a ordenação, os invariantes da árvore são quebrados: contains pesquisa na subárvore errada, remove pode falhar silenciosamente, a iteração pode retornar o mesmo elemento duas vezes ou pular elementos inteiramente.

A regra, reafirmada: coloque elementos efetivamente imutáveis em um TreeSet. Ou, se seu elemento mudar, remova-o antes da mudança e adicione-o novamente depois.

Quando escolher TreeSet

Fluxo de decisão:

• Você precisa de iteração ordenada ou consultas por intervalo → TreeSet. A única escolha.
• Você precisa de verificação rápida de pertencimento e a ordem não importa → HashSet. O(1) vence.
• Você precisa de verificação rápida de pertencimento e ordem de iteração previsível → LinkedHashSet. Ordem de inserção, não ordenada.
• O tipo de elemento é um enum → EnumSet. Mais rápido que TreeSet e naturalmente ordenado.

Um padrão útil: faça uma computação pesada baseada em HashSet quando a velocidade importa, depois new TreeSet<>(hashSet) uma vez no final se precisar apresentar o resultado em ordem. Construa rápido, apresente ordenado.

Um exemplo prático: placar, comparador e consultas por intervalo

O programa abaixo usa TreeSet para manter um placar ordenado por pontuação (com um comparador personalizado), demonstra os métodos de navegação e mostra como a igualdade baseada em compareTo difere da igualdade baseada em equals.

O que tirar da execução:

• Os inteiros voltaram em ordem crescente sem nenhuma ordenação explícita. Esse invariante de ordenação é mantido em cada add — o preço é O(log n) por inserção.
• O placar usou um comparador em dois estágios: decrescente por pontuação, depois crescente por nome para manter jogadores empatados distintos. Sempre inclua um desempate quando pontuações podem se repetir ou o TreeSet os colapsará.
• O conjunto insensível a maiúsculas rejeitou "JAVA" porque, pelo comparador, é igual a "Java" — mesmo que "JAVA".equals("Java") seja false. Igualdade pelo comparador, não igualdade pelo equals.
• null lançou exceção — não há como compará-lo com outros elementos.

O que vem a seguir

Set está concluído; a outra metade do framework é Map, a abstração de chave-valor. Um Set pode ser pensado como um Map onde você não se importa com o valor. O capítulo sobre a interface Map é o próximo, e a estrutura paralela com Set ficará óbvia assim que começarmos. O TreeSet é, de fato, suportado por um TreeMap, portanto os métodos de navegação de mapa ordenado que você viu aqui reaparecerão lá com chaves em vez de elementos.

Prática