Résumé des structures de données et de leur complexité en recherche, insertion et suppression

Ce contenu compare l'efficacité des structures de données (tableau, HashMap, pile, file, arbre) selon les opérations de recherche, insertion et suppression. Le choix dépend du coût en temps, noté en notation O.

Le tableau est lent (O(n)) car il faut souvent parcourir tous les éléments pour agir. La HashMap est instantanée (O(1)) car elle utilise un hachage pour accéder directement à la valeur via sa clé, sans parcours. Les piles et files sont rapides (O(1)) pour ajouter ou retirer des éléments, mais lentes (O(n)) pour chercher à l'intérieur, car elles ne permettent d'agir qu'aux extrémités. Enfin, les arbres binaires offrent un compromis idéal (O(log n)) : chaque étape élimine la moitié des éléments restants, ce qui est bien plus rapide qu'un tableau pour de grandes quantités de données, mais moins rapide qu'une HashMap.

Exemple : Pour trouver le nombre 6 dans un arbre contenant 8, 4, 12, 2, 6, 10, 14 :

1. On compare avec la racine 8 : 6 est plus petit, on va à gauche (4).
2. On compare avec 4 : 6 est plus grand, on va à droite (6).
3. On a trouvé 6.
   Seulement 3 étapes au lieu de parcourir les 7 éléments, d'où la complexité logarithmique.