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

Lire le cours de ce chapitre