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/