04 - Structures de données persistantes : Comment rendre persistante une structure impérative ?

Xavier LeroyCollège de FranceScience du logicielAnnée 2022-2023Structures de données persistantesConcilier amortissement et persistance : de l'importance de la paresseDans ce cours, nous nous intéresserons aux structures de données persistantes dont l'implémentation utilise « sous le capot » des structures impératives et de la mutation en place, tout en préservant une interface purement fonctionnelle. Nous partirons des tableaux fonctionnels de Baker, qui combinent un tableau impératif et des liste de différences, puis introduirons progressivement la technique des « fat nodes » de Driscoll, Sarnak, Sleator et Tarjan, qui donne un procédé systématique pour rendre persistante une structure d'arbre impérative.