5. Ensembles et dictionnaires

Les ensembles et les dictionnaires constituent les structures de données les plus couramment utilisées. Ce chapitre présente plusieurs façons de réaliser des ensembles, en montrant à chaque fois comment elles peuvent être facilement adaptées pour des dictionnaires. Certaines structures s'appliquent à des éléments d'un type quelconque, d'autres sont plus spécialisées, pour des éléments d'une forme particulière (des listes) ou encore d'un type particulier (des entiers).

Certaines de ces structures sont présentées dans une version persistante et d'autres dans une version impérative. C'est là un choix assez arbitraire. D'autres choix sont souvent possibles, comme des tables de hachage persistantes ou encore des AVL impératifs, et parfois proposés en exercice.

Le choix d'une structure de données ne se fait pas uniquement en fonction de son caractère persistant ou impératif. D'autres critères dictent ce choix, comme les opérations disponibles sur les éléments (ex. l'existence d'un ordre total), les opérations fournies par la structure (ex. une opération d'union), ou encore leurs coûts respectifs (ex. la possibilité de construire un ensemble en temps linéaire).

programme page télécharger

32. Signature pour des ensembles persistants 197 p32.ml
33. Signature des types ordonnés 197 p33.ml
34. Arbres binaires de recherche (1/2) 201 p34.ml
35. Arbres binaires de recherche (2/2) 203 p35.ml
36. Équilibrage d'un AVL 209 p36.ml
37. Insertion et suppression dans un AVL 210 p37.ml
38. Signature minimale pour des dictionnaires persistants 212 p38.ml
39. Recherche dans un dictionnaire AVL 213 p39.ml
40. Signature pour des ensembles impératifs 216 p40.ml
41. Signature exigée pour les éléments d'une table de hachage 216 p41.ml
42. Recherche dans une table de hachage 218 p42.ml
43. Insertion dans une table de hachage 219 p43.ml
44. Suppression dans une table de hachage 219 p44.ml
45. Redimensionnement d'une table de hachage 221 p45.ml
46. Recherche dans une table de hachage associative 223 p46.ml
47. Signature minimale du module de lettre 225 p47.ml
48. Signature d'ensembles persistants 225 p48.ml
49. Structure d'arbre de préfixes 227 p49.ml
50. Ajout et suppression dans un arbre de préfixes 229 p50.ml
51. Intersection d'arbres de préfixes 231 p51.ml
52. Recherche dans un arbre de préfixes 233 p52.ml
53. Recherche dans un arbre de Patricia 236 p53.ml
54. Insertion dans un arbre de Patricia 238 p54.ml
55. Suppression dans un arbre de Patricia 241 p55.ml
56. Union de deux arbres de Patricia 244 p56.ml

programme	page	télécharger
32. Signature pour des ensembles persistants	197	`p32.ml`
33. Signature des types ordonnés	197	`p33.ml`
34. Arbres binaires de recherche (1/2)	201	`p34.ml`
35. Arbres binaires de recherche (2/2)	203	`p35.ml`
36. Équilibrage d'un AVL	209	`p36.ml`
37. Insertion et suppression dans un AVL	210	`p37.ml`
38. Signature minimale pour des dictionnaires persistants	212	`p38.ml`
39. Recherche dans un dictionnaire AVL	213	`p39.ml`
40. Signature pour des ensembles impératifs	216	`p40.ml`
41. Signature exigée pour les éléments d'une table de hachage	216	`p41.ml`
42. Recherche dans une table de hachage	218	`p42.ml`
43. Insertion dans une table de hachage	219	`p43.ml`
44. Suppression dans une table de hachage	219	`p44.ml`
45. Redimensionnement d'une table de hachage	221	`p45.ml`
46. Recherche dans une table de hachage associative	223	`p46.ml`
47. Signature minimale du module de lettre	225	`p47.ml`
48. Signature d'ensembles persistants	225	`p48.ml`
49. Structure d'arbre de préfixes	227	`p49.ml`
50. Ajout et suppression dans un arbre de préfixes	229	`p50.ml`
51. Intersection d'arbres de préfixes	231	`p51.ml`
52. Recherche dans un arbre de préfixes	233	`p52.ml`
53. Recherche dans un arbre de Patricia	236	`p53.ml`
54. Insertion dans un arbre de Patricia	238	`p54.ml`
55. Suppression dans un arbre de Patricia	241	`p55.ml`
56. Union de deux arbres de Patricia	244	`p56.ml`

Dernière mise à jour : 24/1/2024