8. Structures de données avancées

Durée : 7 périodes de 45 minutes Option complémentaire

Ce qu'il faudra retenir du chapitre 8

• Piles, files, arbres
• Arbres binaires
• Complexité
• Arbre binaire de recherche
• Arbre AVL
• Tas
• Trie
• Représentation de graphes
• Table de hachage

Chapitre 8

Structures de données avancées

Version 2022.03

Programmes Python

• trie_fr.py, test_dico.py, dictionnaire.txt

Compléments

• La théorie de la complexité algorithmique pour calculer efficacement, Interstices
• HP-11C : manuel d'utilisation

Corrigés des exercices

8.1, 8.3, 8.4, 8.5, 8.7, 8.8, 8.10, 8.11, 8.12a, 8.12b, 8.13, 8.14

Pages interactives

• Visualgo
• Data Structure Visualizations

Sites de référence

• Wikipédia : Structure de données
• Wikipédia : Arbre (structure de données)
• Wikipédia : Théorie de la complexité des algorithmes

Livres

• The Art of Computer Programming, Volumes 1-3, Donald E. Knuth, Addison Wesley, 1998
• Data Structures and Algorithm Analysis in C++, Mark A. Weiss, Pearson, 2005
• Algorithms, Robert Sedgewick, Addison Wesley, 2011
• Introduction à l'algorithmique, Thomas H. Cormen et al., Dunod, 2002