Deux ordres d'insertion, un seul parcours infixe

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 11 — Arbres de recherche, tas et files de priorité

Énoncé

On insère les mêmes sept clés $2, 4, 6, 8, 10, 12, 14$ dans un ABR initialement vide, dans deux ordres :

ordre A : $8, 4, 12, 2, 6, 10, 14$ ;
ordre B : $2, 4, 6, 8, 10, 12, 14$ .

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	$2$	$2, 4, 6, 8, 10, 12, 14$	$8, 4, 2, 6, 12, 10, 14$
ordre B	$6$	$2, 4, 6, 8, 10, 12, 14$	$2, 4, 6, 8, 10, 12, 14$

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 $n - 1 = 6$ , 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 $20000$ mots d'un dictionnaire, l'insertion en ordre trié bâtit un peigne de hauteur $19999$ en $5, 39$ s, contre une hauteur $32$ en $0, 008$ s pour le même ensemble mélangé — un facteur $648$ pour les mêmes clés.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.