Prologin
2025
Structures communes¶
| Structure | Commentaire |
|---|---|
| liste | suite d'éléments |
| ensemble | se comporte comme un sac d'éléments (sans ordre). On peut tester si un élément donné est dans le sac |
| dictionnaire / tableau associatif | permet d'associer un élément à un autre. Se comporte aussi comme un ensemble |
| graphe | points reliées par des liens |
| arbre préfixe | forme d'arbre où chaque nœud représente un préfixe |
| tas | structure où le minimum (ou maximum, au choix) est immédiatement disponible (base commune des files de priorité, utiles notamment à l'algo de Dijkstra) |
Structures avancées¶
| Structure | Commentaire |
|---|---|
| Arbre d'intervalles | permet de stocker des intervalles et tester leur intersection |
| Union-find | permet de déterminer incrémentalement le partitionnement d'un ensemble (composantes connectées incrémentales, Kruskal) |
| Arbre bicolore | arbre équilibré |
| B Tree | cousin de l'arbre bicolore regroupant, éléments dans le même nœud |
| Quad / Oct Tree | permet d'indexer des éléments dans l'espace |
| Arbre de Merkle | permet de vérifier l'intégrité / identifier de très gros arbres (Git) |
Bestioles ésotériques¶
| Structure | Commentaire |
|---|---|
| Filtre de Bloom | permet de tester la probable présence d'un élément dans un set (utilisés là et dans l'éditeur de lien dynamique GNU) |
| HyperLogLog | permet d'estimer le nombre d'éléments uniques dans un flux (dans redis) |
| Treap | ensemble ordonné, hybride entre tas et arbre (usages: ça et ça) |
| Locality sensitive hashing | recherche de similarités dans des espaces à haute dimension |
| Skip list | liste à l'accès aléatoire « rapide » (presque utile) |
| VList | hybride vecteur / liste |
| Arbre de recherche ternaire | arbre préfixe avec bonne utilisation mémoire |
| Arbre de Van Emde Boas | tableau associatif (dictionnaire) ordonné |
| Arbre préfixe compressé par niveau | meilleure utilisation mémoire que les arbres préfixes normaux (tables de routage) |
| Corde | Permet d'éditer facilement du texte |
| Structure de Dietz | Permet de maintenir efficacement un ordre absolu |
| Arbre d'ondelettes | Compression de chaines |
~
Vous en voulez plus ?
Quelle structure est la plus efficace pour votre problème ? http://bigocheatsheet.com/
