informatique (MP2I/MPI) · Chapitre 11 · Application directe du cours
Deux ordres d'insertion, un seul parcours infixe
Arbres de recherche, tas et files de priorité · niveau 2
Énoncé
On insère les mêmes sept clés dans un ABR initialement vide, dans deux ordres :
- ordre A : ;
- ordre B : .
Donner la hauteur, le parcours infixe et le parcours préfixe de chaque arbre. Que peut-on en conclure ?
Corrigé
Mesuré en OCaml :
| hauteur | infixe | préfixe | |
|---|---|---|---|
| ordre A | |||
| ordre B |
Trois conclusions, et la troisième est la plus utile.
- Le parcours infixe ne dépend pas de l'ordre d'insertion : c'est la suite triée des clés, toujours. Il ne dit rien de la forme.
- La forme, elle, en dépend entièrement. L'ordre B produit le peigne annoncé par la mise en garde du chapitre : hauteur , et toute recherche devient un parcours de liste.
- Donc le parcours infixe ne suffit pas à décrire un ABR, alors que le préfixe, lui, le détermine — les deux préfixes diffèrent. Ce point resservira au chapitre chap:hachage : pour sérialiser un arbre, c'est le préfixe qu'on écrit, pas l'infixe.
Le coût de la construction se ressent : mesuré sur mots d'un dictionnaire, l'insertion en ordre trié bâtit un peigne de hauteur en s, contre une hauteur en s pour le même ensemble mélangé — un facteur pour les mêmes clés.
