TreeSet en Java

Java fournit un vaste ensemble de structures de données pour travailler efficacement avec les collections d'éléments. L'une de ces structures de données est TreeSet, une implémentation d'un arbre rouge-noir en Java. TreeSet maintient un ordre trié pour stocker les éléments uniques. Les débutants peuvent trouver l’utilisation de la classe Java TreeSet un peu difficile au début. Dans cet article, nous allons découvrir comment utiliser TreeSet , en expliquant ses concepts de base et en fournissant des exemples de code pour vous aider à commencer à intégrer TreeSet dans vos projets Java.

Structure TreeSet : arbre rouge-noir

Comme nous l'avons mentionné précédemment, la structure de classe Java TreeSet est implémentée sous la forme d'un arbre de recherche binaire auto-équilibré connu sous le nom d'arbre rouge-noir. Expliquons ce que c'est... Un arbre rouge-noir représente une structure de données de recherche binaire équilibrée couramment utilisée pour stocker et organiser des données triées. Il tire son nom des propriétés qui maintiennent son équilibre :

• Chaque nœud de l'arborescence est rouge ou noir.
• La racine de l’arbre Rouge-Noir est toujours noire.
• Tous les nœuds feuilles (nœuds NIL ou liens nuls) sont noirs.
• Si un nœud de l’arbre est rouge, alors ses enfants sont noirs.
• Chaque chemin simple d'un nœud à ses nœuds descendants contient un nombre égal de nœuds noirs.

Les arbres rouge-noir présentent des performances efficaces pour les opérations d'insertion, de suppression et de recherche d'éléments en assurant l'équilibre. Cela garantit que la hauteur de l'arbre reste proportionnelle au logarithme du nombre de nœuds qu'il contient, ce qui entraîne une complexité temporelle logarithmique pour les opérations. Les arbres rouge-noir trouvent de nombreuses applications dans divers domaines, y compris la mise en œuvre d'arbres de recherche équilibrés dans les langages de programmation, les bases de données (par exemple, les structures d'index internes) et d'autres scénarios où un stockage et des opérations efficaces sur des données triées sont nécessaires.

Caractéristiques et faiblesses de TreeSet

TreeSet fournit plusieurs fonctionnalités clés qui en font un outil précieux pour gérer des collections d'objets de manière triée. Avantages :

• Maintenance automatique des éléments dans un ordre trié. Lors de l'ajout ou de la suppression d'éléments, la structure arborescente s'ajuste pour les maintenir triés. Cela élimine le besoin de tri manuel et fournit un accès efficace par ordre croissant ou décroissant.
• Opérations efficaces de recherche, d’insertion et de suppression. Il utilise une structure arborescente de recherche binaire, permettant ces opérations avec une complexité temporelle de O(log N) . Ici N est le nombre d’éléments.
• TreeSet garantit le caractère unique des éléments en utilisant leur ordre naturel ou un Comparator personnalisé . Ceci est utile lorsque vous travaillez avec des collections qui nécessitent des éléments distincts.

Limites:

• Légèrement plus lent que HashSet en raison du maintien de l'ordre de tri.
• N'autorise pas les éléments nuls, car il repose sur un ordre naturel ou un comparateur personnalisé pour la comparaison des éléments.

Java TreeSet : exemple d'opérations principales

Montrons maintenant comment créer un TreeSet en Java, obtenir la taille de la collection, y ajouter des éléments, les supprimer et vérifier si un élément se trouve dans le TreeSet . Ces exemples de code illustrent les principales opérations lors de l'utilisation de TreeSet : créer une instance, ajouter des éléments, supprimer des éléments, vérifier la présence d'éléments et obtenir la taille du TreeSet . Création d'une instance TreeSet et ajout d'éléments :

// Creating a TreeSet of Integer type
TreeSet<Integer> numbers = new TreeSet<>();

// Adding elements to the TreeSet
numbers.add(18);
numbers.add(2);
numbers.add(7);
numbers.add(28);

System.out.println(numbers); // Output: [2, 7, 18, 28]

Ici, nous utilisons la méthode add() pour ajouter 4 nombres dans notre TreeSet . Si nous créons une méthode principale et exécutons le programme, la sortie sera triée (2, 7, 18, 28). Suppression d'éléments de TreeSet :

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

names.add("Johnny");
names.add("Ivy");
names.add("David");
names.add("Ricky");

// Removing an element from the TreeSet
names.remove("David");

System.out.println(names); // Output: [Ivy, Johnny, Ricky]

Vérification de la présence d'un élément dans TreeSet :

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

musicalInstrument.add("Piano");
musicalInstrument.add("Drums");
musicalInstrumentfruits.add("Violin");
musicalInstrument.add("Double Bass");

// Checking if an element exists in the TreeSet
boolean containsPiano = musicalInstrument.contains("Piano");
boolean containsCello = musicalInstrument.contains("Cello");

System.out.println(containsPiano); // Output: true
System.out.println(containsCello); // Output: false

Obtention de la taille de TreeSet :

TreeSet<Character> letters = new TreeSet<>();

letters.add('A');
letters.add('B');
letters.add('C');
letters.add('D');

// Getting the size of the TreeSet
int size = letters.size();

System.out.println(size); // Output: 4

Tri et itération dans TreeSet

TreeSet en Java fournit des fonctionnalités puissantes pour trier et itérer sur des collections d'éléments. Dans cette section, nous explorerons diverses techniques pour trier les éléments, itérer sur TreeSet et effectuer des recherches basées sur des plages à l'aide des méthodes subSet() , headSet() et tailSet() . Par défaut, TreeSet conserve automatiquement les éléments dans l'ordre trié. Cependant, nous pouvons personnaliser le comportement de tri en fournissant un Comparator lors de la création du TreeSet . Voyons un exemple :

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetSortingExample {
  public static void main(String[] args) {
    // Create a TreeSet with custom sorting
    TreeSet<Integer> numbers = new TreeSet<>(Comparator.reverseOrder());

    // Add elements to the TreeSet
    numbers.add(5);
    numbers.add(3);
    numbers.add(7);
    numbers.add(1);

    System.out.println(numbers); // Output: [7, 5, 3, 1]
  }
}

Dans le code ci-dessus, nous créons un TreeSet de type Integer et fournissons un Comparator personnalisé en utilisant Comparator.reverseOrder() pour trier les éléments par ordre décroissant. Le TreeSet résultant contiendra des éléments [7, 5, 3, 1] . Il existe plusieurs façons de parcourir TreeSet . Nous pouvons utiliser un itérateur ou utiliser la boucle for-each améliorée . Voyons des exemples des deux approches :

import java.util.TreeSet;
import java.util.Iterator;

public class TreeSetIterationExample {
  public static void main(String[] args) {
    TreeSet<String> names = new TreeSet<>();

    names.add("Johnny");
    names.add("Ivy");
    names.add("Ricky");
    names.add("David");

    // Iterating using an iterator
    Iterator<String> iterator = names.iterator();
    while (iterator.hasNext()) {
      String name = iterator.next();
      System.out.println(name);
    }

    // Iterating using the enhanced for-each loop
    for (String name : names) {
      System.out.println(name);
    }
  }
}

Dans le code ci-dessus, nous créons un TreeSet appelé noms et ajoutons quelques éléments. Nous démontrons ensuite deux manières d'itérer sur le TreeSet : en utilisant un itérateur et en utilisant la boucle for-each améliorée. TreeSet fournit des méthodes pour effectuer des recherches basées sur des plages, nous permettant de récupérer des sous-ensembles d'éléments en fonction de critères spécifiques. Les trois principales méthodes de recherche basées sur une plage sont :

• subSet(E fromElement, E toElement) : renvoie un sous-ensemble d'éléments de fromElement (inclus) à toElement (exclusif).
• headSet(E toElement) : renvoie un sous-ensemble d'éléments inférieur à toElement .
• tailSet(E fromElement) : renvoie un sous-ensemble d'éléments supérieur ou égal à fromElement .

Voyons un exemple :

import java.util.TreeSet;

public class TreeSetRangeSearchExample {
  public static void main(String[] args) {
    TreeSet<Integer> numbers = new TreeSet<>();

    numbers.add(1);
    numbers.add(3);
    numbers.add(5);
    numbers.add(7);
    numbers.add(9);

    // Performing range-based search using subSet()
    TreeSet<Integer> subset = new TreeSet<>(numbers.subSet(3, 8));
    System.out.println(subset); // Output: [3, 5, 7]

    // Performing range-based search using headSet()
    TreeSet<Integer> headSet = new TreeSet<>(numbers.headSet(6));
    System.out.println(headSet); // Output: [1, 3, 5]

    // Performing range-based search using tailSet()
     TreeSet<Integer> tailSet = new TreeSet<>(numbers.tailSet(5));
    System.out.println(tailSet); // Output: [5, 7, 9]
  }
}

Dans le code ci-dessus, nous créons un TreeSet appelé nombres et ajoutons quelques éléments. Nous démontrons ensuite les recherches basées sur des plages à l'aide des méthodes subSet() , headSet() et tailSet() .

• Le sous-ensemble TreeSet contient des éléments compris entre 3 (inclus) et 8 (exclusif), qui sont [3, 5, 7] .
• Le headSet TreeSet contient des éléments inférieurs à 6, qui sont [1, 3, 5] .
• Le tailSet TreeSet contient des éléments supérieurs ou égaux à 5, qui sont [5, 7, 9] .

Ces méthodes de recherche basées sur des plages nous permettent de récupérer des sous-ensembles d'éléments en fonction de critères spécifiques, offrant ainsi une flexibilité dans le travail avec des données triées.

Comparateur dans TreeSet : tri avec des critères personnalisés

Sauf pour l'ordre naturel, vous pouvez utiliser un Comparator personnalisé pour trier TreeSet . Dans cette section, nous approfondirons le concept de comparateur et son rôle dans TreeSet . Nous explorerons comment créer un TreeSet avec un comparateur personnalisé et fournirons des exemples de code pour démontrer le tri de TreeSet en fonction de critères spécifiques.

Qu'est-ce que le comparateur ?

Un comparateur est une interface en Java qui permet un tri personnalisé des objets. Il fournit un moyen de définir l'ordre des éléments en fonction d'attributs ou de propriétés spécifiques. En implémentant l' interface Comparator et en remplaçant sa méthode compare() , nous pouvons spécifier comment les éléments doivent être triés dans un TreeSet .

Création de TreeSet avec un comparateur personnalisé

Pour créer un TreeSet avec un comparateur personnalisé, nous devons fournir le comparateur comme argument lors de la création de l' instance TreeSet . Voyons un exemple :

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetComparatorExample {
  public static void main(String[] args) {
    // Create a TreeSet with a custom comparator
    TreeSet<String> names = new TreeSet<>(new LengthComparator());

    // Add elements to the TreeSet
    names.add("Johnny");
    names.add("Ivy");
    names.add("Rick");
    names.add("David");

    System.out.println(names); // Output: [Ivy, Johnny, David, Rick]
  }
}

class LengthComparator implements Comparator<String> {
  @Override
  public int compare(String s1, String s2) {
    return Integer.compare(s1.length(), s2.length());
  }
}

Dans le code ci-dessus, nous créons un TreeSet appelé noms avec un comparateur personnalisé appelé lengthComparator . Le lengthComparator compare la longueur de deux chaînes et les trie en conséquence. En conséquence, le TreeSet est trié en fonction de la longueur des chaînes, nous donnant le résultat [Ivy, Rick, David, Johnny] .

Exemples de tri de TreeSet à l'aide d'un comparateur

En plus de créer un TreeSet avec un comparateur personnalisé, nous pouvons également utiliser un comparateur pour trier temporairement un TreeSet sans modifier son ordre naturel. Voyons un exemple :

import java.util.Comparator;
import java.util.TreeSet;

  public class TreeSetTest {
    public static void main(String[] args) {
      TreeSet<String> names = new TreeSet<>();

      names.add("Johnny");
      names.add("Ivy");
      names.add("Ricky");
      names.add("David");

      // Sort TreeSet temporarily using a comparator
      TreeSet<String> sortedNames = new TreeSet<>(Comparator.reverseOrder());
      sortedNames.addAll(names);

      System.out.println(sortedNames); // Output: [Ricky, Johnny, Ivy, David]
      System.out.println(names); // Output: [David, Ivy, Johnny, Ricky]
    }
  }

Dans le code ci-dessus, nous créons un TreeSet appelé noms et ajoutons quelques éléments. Nous créons ensuite un nouveau TreeSet appelé sortedNames avec un comparateur personnalisé Comparator.reverseOrder() . En ajoutant tous les éléments des noms originaux TreeSet aux sortedNames , nous obtenons une version triée temporaire du TreeSet .

Comparaison de TreeSet avec d'autres structures de données

Comparaison de TreeSet avec HashSet

TreeSet et HashSet sont tous deux des implémentations de l' interface Set en Java. Il existe cependant des différences significatives entre eux. TreeSet : TreeSet stocke les éléments uniques dans un ordre trié. Il utilise un arbre de recherche binaire auto-équilibré (généralement un arbre rouge-noir) pour maintenir l'ordre de tri, ce qui entraîne une complexité temporelle logarithmique pour les opérations telles que l'insertion, la suppression et la recherche. TreeSet est efficace pour maintenir une collection triée et effectuer des opérations basées sur des plages. Cependant, il nécessite une surcharge de mémoire plus élevée en raison de la structure arborescente et n'autorise pas les éléments nuls. HashSet : HashSet stocke des éléments uniques de manière non ordonnée en utilisant des codes de hachage et une table de hachage en interne. Il offre une complexité temporelle constante pour les opérations de base telles que l'insertion, la suppression et la recherche. HashSet est efficace pour une recherche rapide d'éléments et n'impose aucune surcharge de mémoire supplémentaire pour le maintien de l'ordre. Cependant, il ne garantit aucun ordre spécifique des éléments.

Quand utiliser TreeSet :

• Lorsque vous devez conserver automatiquement les éléments dans un ordre trié.
• Lorsque vous avez besoin d’opérations basées sur une plage ou que vous devez rechercher efficacement des éléments dans une plage spécifique.
• Lorsque les éléments en double ne sont pas autorisés et que l’unicité est essentielle.
• Lorsque vous êtes prêt à sacrifier une utilisation de la mémoire légèrement plus élevée pour bénéficier des avantages des opérations de tri et de plage automatiques.

Comparaison de TreeSet avec ArrayList

ArrayList est une implémentation de tableau dynamique en Java. Voici les principales différences entre TreeSet et ArrayList :

• TreeSet : TreeSet stocke les éléments uniques dans un ordre trié, fournissant des opérations efficaces pour maintenir une collection triée et effectuer des recherches basées sur des plages. Il a une complexité temporelle logarithmique pour les opérations. TreeSet ne convient pas à un accès aléatoire ou au maintien de l'ordre d'insertion.
• ArrayList : ArrayList stocke les éléments dans l'ordre d'insertion, offrant un accès aléatoire rapide aux éléments à l'aide d'index. Il a une complexité temporelle constante pour la plupart des opérations lors de l'accès aux éléments par index. Cependant, sa complexité temporelle est linéaire pour insérer ou supprimer des éléments du milieu de la liste, car elle nécessite le déplacement d'éléments.

Quand envisager d’autres structures de données

• Si le maintien des éléments dans un ordre trié n'est pas nécessaire et que vous avez besoin d'une recherche rapide d'éléments ou d'une collection non ordonnée, HashSet pourrait être un meilleur choix.
• Si vous avez besoin d'un accès aléatoire fréquent aux éléments par index ou si vous devez conserver l'ordre d'insertion, ArrayList serait plus approprié.