🌳 TreeSet, TreeMap
Les TreeSet et TreeMap sont des structures de données qui permettent de stocker des éléments de façon triée, en s’appuyant sur des arbres binaires de recherche équilibrés (typiquement des Red-Black Trees ou AVL).
Un arbre binaire de recherche équilibré est différent de l'arbre binaire de recherche codé en exercice, car il garantit que les opérations de recherche, d'insertion et de suppression sont effectuées en temps logarithmique, même dans le pire des cas. Pour ce faire, il maintient l'équilibre de l'arbre après chaque opération, c'est-à -dire qu'il ajuste la structure de l'arbre pour que la hauteur reste minimale.
TreeSet​
Définition​
Un TreeSet est un arbre binaire de recherche équilibré qui stocke des éléments uniques, triés selon leur ordre naturel (ou un comparateur fourni). Il n’autorise pas les doublons et garantit que les éléments sont toujours ordonnés.
Complexités​
| Opération | Recherche | Insertion | Suppression | Parcours trié |
|---|---|---|---|---|
| TreeSet | O(log n) | O(log n) | O(log n) | O(n) |
Quand l’utiliser ?​
- Besoin d’un ensemble sans doublons
- Recherche rapide de l’existence d’un élément
- Parcours des éléments dans l’ordre croissant
En Python, le module sortedcontainers fournit une implémentation appelée
SortedSet, mais qui n'est pas en fait implémentée avec un arbre binaire de
recherche équilibré. Il utilise plutôt une liste
triée et des
opérations de recherche binaire pour maintenir l'ordre.
TreeMap​
Définition​
Un TreeMap est une table de correspondance (clé-valeur) où les clés sont triées selon leur ordre naturel (ou un comparateur fourni). Les clés sont uniques. On peut voir un TreeMap comme un TreeSet, mais avec des valeurs associées à chaque clé.
Complexités​
| Opération | Recherche | Insertion | Suppression | Parcours trié |
|---|---|---|---|---|
| TreeMap | O(log n) | O(log n) | O(log n) | O(n) |
Quand l’utiliser ?​
- Parcours des éléments dans l’ordre croissant
Comparaison avec set et dict​
Python propose des structures de données similaires, mais sans implémentation d'arbre binaire de recherche équilibré natif. Voici un tableau comparatif entre les structures de données Python et les concepts de TreeSet et TreeMap :
| Structure | Doublons | Ordre | Recherche | Insertion | Suppression | Parcours trié | Cas d’usage typiques |
|---|---|---|---|---|---|---|---|
| set | Non | Non | O(1) | O(1) | O(1) | Non | Ensemble rapide, non trié |
| TreeSet | Non | Oui | O(log n) | O(log n) | O(log n) | Oui | Ensemble trié, sans doublons |
| dict | Clés uniques | Non | O(1) | O(1) | O(1) | Non | Dictionnaire rapide |
| TreeMap | Clés uniques | Oui | O(log n) | O(log n) | O(log n) | Oui | Dictionnaire trié |
Bien que le tableau ci-dessus montre que la différence peut paraître petite, car O(log n) est en général très proche de O(1) pour des valeurs de n raisonnables, il est important de noter que set et dict sont bien plus rapides, car la localité des données est meilleure. En effet, le parcours d'une structure de données comme un arbre binaire de recherche équilibré nécessite de suivre des pointeurs, ce qui peut être moins efficace que l'accès direct aux indices d'une liste ou d'un dictionnaire.