02 - Structures de données persistantes : Arbres équilibrés + copie de branches = persistance

Xavier LeroyCollège de FranceScience du logicielAnnée 2022-2023Structures de données persistantesArbres équilibrés + copie de branches = persistanceCopier 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.