associatif

Deux structures de données se montrent efficaces pour représenter les tableaux associatifs : la table de hachage et l’arbre équilibré. Les avantages et inconvénients respectifs de ces deux solutions sont les suivants :

Les tables de hachage ont une meilleure complexité en moyenne pour l’insertion et la recherche (O(1)), alors que les arbres équilibrés ont une meilleure complexité dans le pire des cas (O(log(n)), au lieu de O(n) pour les tables de hachage) ;
Les tables de hachage ont une représentation mémoire généralement plus compacte ;
Les arbres équilibrés peuvent aisément fournir des structures de données persistantes, ce qui est particulièrement mis en avant dans la programmation fonctionnelle ;
Les tables de hachage nécessitent la définition d’une bonne fonction de hachage, ce qui peut être difficile à réaliser dans certains cas, alors que les arbres équilibrés ne demandent qu’un ordre total sur les clefs. Inversement, les tables de hachage peuvent être utilisées sur des clefs non ordonnées ;
Les arbres équilibrés préservent l’ordre des clefs, permettant notamment d’effectuer un parcours des clefs dans l’ordre ou de localiser efficacement une clé proche d’une valeur donnée. Les tables de hachage, en revanche, ne préservent pas l’ordre des clefs (lorsqu’il existe).

via Tableau associatif — Wikipédia

En informatique, un arbre radix ou arbre PATRICIA (pour Practical Algorithm To Retrieve Information Coded In Alphanumeric en anglais) est une structure de données compacte permettant de représenter un ensemble de mots adaptée pour la recherche. Il est obtenu à partir d’un arbre préfixe en fusionnant chaque nœud n’ayant qu’un seul fils avec celui-ci. On peut alors étiqueter indifféremment chaque arrête par un mot ou bien par une unique lettre.

Si tu avais été une fille, tes parents t’auraient peut être appelé comme ça?

https://fr.wikipedia.org/wiki/Arbre_radix

 

30554049834_8335095ef6_o.jpg

 

Publicités

Laisser un commentaire

Choisissez une méthode de connexion pour poster votre commentaire:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s