02 - Structures de données persistantes : Arbres équilibrés + copie de branches = persistance
Contenu de l'épisode
Xavier Leroy
Collège de France
Science du logiciel
Année 2022-2023
Structures de données persistantes
Arbres équilibrés + copie de branches = persistance
Copier et modifier une branche d'un arbre équilibré, tout en partageant les sous-arbres non modifiés avec l'arbre d'origine, est une technique simple et générale pour construire de nombreuses structures de données persistantes ayant des complexités O(log n). Le cours montrera cette technique à l'œuvre sur des structures de type « dictionnaire » : arbres de recherche, arbres préfixes, arbres préfixes avec hachage (HAMT), arbres de Braun, etc.