Structures de données
Voici une structure de données des structures de données.
Une relation A -> B signifie « B est un cas particulier de A ».
Une relation en pointillés A -> B signifie « A peut être implémenté par B ».
Les nœuds à double bordure sont les types abstraits.
Structures moins connues
- Corde, pour stocker de longues chaînes de caractères
- Arbre cartésien, un arbre tournoi qui maintient une séquence donnée par son ordre infixe, efficace pour des problèmes de minimum d’une plage.
- Tableau de suffixes, une manière efficace de stocker un arbre de suffixes.
Structures de données dynamiques
Une structure de données dynamique doit répondre efficacement à des requêtes, qui sont des opérations sur l’ensemble qu’elle contient.
- Union-find permet de maintenir une partition d’éléments avec des requêtes de recherche et d’union
- Range minimum query, permet de maintenir un tableau d’entiers avec des requêtes de minimum d’une plage
- Arbre de Fenwick, permet de maintenir un tableau d’entiers avec des requêtes de somme d’une plage et de mise à jour d’un élément
- Arbre d’intervalles, permet de maintenir un ensemble d’intervalles avec des requêtes : « Quels intervalles contiennent un certain entier ? »