Structure de données
Un article de Freepedia.
On nomme structure de données une structure logique destinée à contenir des données afin de leur donner une organisation permettant de simplifier leur traitement.
Pour prendre un exemple de la vie quotidienne, on peut présenter des numéros de téléphone par département, par nom, par profession (pages jaunes), par numéro téléphonique (annuaires destinés au télémarketing), par rue et/ou une combinaison quelconque de ces classements. À chaque usage correspondra une structure d'annuaire appropriée.
Sommaire |
Types de collections
Collections séquentielles
Une collection séquentielle permet de ranger des objets dans un ordre arbitraire. On parle de collection indexée quand on peut accéder à chaque élément de la collection par un numéro d'orde. Le choix d'une implémentation particulière dépend d'un certain nombre de compromis comme l'occupation mémoire ou les performances requises pour diverses opérations de base : itération, ajout d'un élément, indexation, suppression d'un élément, décompte du nombre d'éléments…
Un certain nombre de structures de données sont des restrictions de collections séquentielles qui n'autorisent qu'un sous ensemble des opérations de base :
Files à priorités
Le type abstrait file à priorités est une collection d'éléments indexés par des clés sur lesquels ont peut effectuer deux opérations: l'insertion d'un élément et l'extraction de l'élément de plus grande clé.
- Tas ou tas binaire
On peut implémenter une union sur les files à priorité:
Tables de symboles ou collections mappées
Ce type de collection nommé dictionnaire ou map permet de ranger des objets en fonction d'une clef dans une table de symboles. La clef doit généralement respecter un certain nombre d'invariants pour être valide (valeur de hachage ou résultats de la comparaison par exemple).
- Table de hachage
- Arbre binaire de recherche ou ABR
- Arbre balancé ou arbre à critère d'équilibre.
- Arbre AVL
- Arbre 2-3-4
- Arbre rouge-noir ou arbre SBB (Symetric Binary Tree)
- Arbre B ou B-Tree
