Exercices corrigés — Arbres de recherche, tas et files de priorité (informatique (MP2I/MPI))

15 exercices avec corrigé rédigé, du plus simple au plus exigeant.

• Le test local ne suffit pas Exercice de TD
• Chercher dans un tas coûte $\Omega (n)$ Exercice de TD
• Fusionner deux tas : réinsérer ou reconstruire ? Exercice de TD
• Le $k$-ième plus petit en $O(h)$ Exercice de TD
• Une file de priorité sur des couples, et la diminution de clé Exercice de TD
• Problème — La suppression dans un ABR, et la dégradation qu'elle provoque Exercice de TD
• Problème — Le tri par tas, en place et en $\Theta (n\log n)$ Exercice de TD
• Deux ordres d'insertion, un seul parcours infixe Application directe du cours
• L'arithmétique du tas dans un tableau Application directe du cours
• Un tas maximum sans réécrire une ligne Application directe du cours
• Un tableau associatif par arbre binaire de recherche Application directe du cours
• Le tri par tas du cours est-il en place ? Application directe du cours
• Problème — L'arbre bicolore : d'où vient la garantie, et jusqu'où elle est serrée Application directe du cours
• Problème — Ce que la complexité ne dit pas : deux tris en $\Theta (n\log n)$ Application directe du cours
• Problème — Deux usages d'un tas de taille $k$ Application directe du cours

Lire le cours de ce chapitre