Java TreeSet

TreeSet<E> est l'implémentation de Set qui maintient ses éléments triés. Elle repose sur un arbre rouge-noir (le même arbre binaire de recherche équilibré qui sous-tend TreeMap), donc chaque opération — add, remove, contains, first, last, requêtes de plage — est en O(log n). C'est plus lent que le O(1) de HashSet, mais vous obtenez quelque chose que HashSet ne peut absolument pas offrir : un itérateur trié, le plus petit élément à la demande, et la possibilité de demander « tous les tags entre a et m ».

TreeSet implémente l'interface plus riche NavigableSet<E> (qui étend SortedSet<E>), donc toutes les requêtes de plage et de voisinage sont directement sur la classe, et non enfouies dans des utilitaires Collections. Si vous n'avez pas encore vu le contrat de base, lisez d'abord le chapitre sur l'interface Set — tout ce qui s'y trouve (pas de doublons, add retourne false en cas de répétition) s'applique toujours.

Deux façons de définir l'ordre

Un TreeSet a besoin d'un moyen de comparer les éléments. Il en existe deux :

1. Ordre naturel — le type d'élément implémente Comparable<E>. String, Integer, LocalDate, chaque classe englobante, chaque enum, chaque record que vous écrivez et qui implémente Comparable. Le constructeur sans argument new TreeSet<>() utilise cela.
2. Un Comparator<E> que vous fournissez — passez-en un au constructeur. L'ensemble utilise votre comparateur pour chaque comparaison.

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]

Le deuxième exemple est important. TreeSet décide de l'« égalité » en se basant sur compareTo retournant 0, pas sur equals. Deux chaînes que l'ordre naturel considère différentes mais qu'un comparateur considère égales seront fusionnées en un seul élément. C'est presque toujours ce que vous voulez — mais c'est un piège subtil si vous ne l'aviez pas réalisé.

L'API NavigableSet

Un TreeSet expose des opérations qu'un Set simple ne peut pas offrir :

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

Ce sont les opérations qui justifient le coût en O(log n) : un HashSet ne peut en faire aucune sans trier l'ensemble entier au préalable. Si vous en avez besoin, TreeSet est le bon choix.

Pas de nulls

Un TreeSet ne peut pas contenir null car il devrait comparer null avec les autres éléments, et compareTo(null) lève une NullPointerException. L'ensemble lève une exception dès la première insertion. Si vous avez besoin d'une valeur sentinelle, utilisez une autre valeur du type d'élément — Integer.MIN_VALUE, un String vide, ou un marqueur dédié dans un enum.

Muter les éléments est interdit (même piège que HashSet)

TreeSet détermine l'emplacement dans l'arbre à l'insertion en appelant compareTo (ou votre Comparator). Si vous mutez un élément après l'insertion d'une façon qui modifie l'ordre, les invariants de l'arbre sont rompus : contains cherche dans le mauvais sous-arbre, remove peut échouer silencieusement, et l'itération peut retourner le même élément deux fois ou en sauter d'autres entièrement.

La règle, reformulée : placez des éléments effectivement immuables dans un TreeSet. Ou, si votre élément change, retirez-le avant le changement et réinsérez-le après.

Quand choisir TreeSet

Arbre de décision :

• Vous avez besoin d'une itération triée ou de requêtes de plage → TreeSet. Le seul choix.
• Vous avez besoin d'une appartenance rapide et l'ordre n'a pas d'importance → HashSet. O(1) gagne.
• Vous avez besoin d'une appartenance rapide et d'un ordre d'itération prévisible → LinkedHashSet. Ordre d'insertion, pas trié.
• Le type d'élément est un enum → EnumSet. Plus rapide que TreeSet et naturellement ordonné.

Un pattern utile : faites un calcul intensif basé sur HashSet quand la vitesse compte, puis new TreeSet<>(hashSet) une seule fois à la fin si vous devez présenter le résultat en ordre. Construire vite, présenter trié.

Un exemple concret : classement, comparateur et requêtes de plage

Le programme ci-dessous utilise TreeSet pour maintenir un classement trié par score (avec un comparateur personnalisé), démontre les méthodes de navigation, et montre en quoi l'égalité basée sur compareTo diffère de l'égalité basée sur equals.

Ce qu'il faut retenir de l'exécution :

• Les entiers sont revenus dans l'ordre croissant sans aucun tri explicite. Cet invariant trié est maintenu à chaque add — le prix est O(log n) par insertion.
• Le classement a utilisé un comparateur en deux étapes : décroissant par score, puis croissant par nom pour garder les joueurs à égalité distincts. Incluez toujours un critère de départage lorsque les scores peuvent se répéter, sinon TreeSet les fusionnera.
• L'ensemble insensible à la casse a rejeté "JAVA" car, selon le comparateur, il est égal à "Java" — même si "JAVA".equals("Java") est false. Égalité par comparateur, pas par equals.
• null a levé une exception — il n'y a aucune façon sensée de le comparer aux autres éléments.

La suite

Set est terminé ; l'autre moitié du framework est Map, l'abstraction clé-valeur. Un Set peut être vu comme un Map où la valeur ne vous intéresse pas. Le chapitre sur l'interface Map est le suivant, et la structure parallèle avec Set sera évidente dès que nous commencerons. TreeSet est en fait soutenu par un TreeMap, donc les méthodes de navigation de map triée que vous avez vues ici réapparaissent là avec des clés au lieu d'éléments.

Pratique