Jeux d'essai — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 9)

Jeux d'essai

Arbres binaires de recherche de coût minimum · niveau 2

Énoncé

Comparer les coûts et les hauteurs des trois arbres (glouton, hauteur minimum, coût minimum) pour $n = 31$ valeurs et les fréquences suivantes :

toutes égales à $1$ ;
$f_{x} = ∣ x - 15∣$ (distance à la valeur médiane) ;
$f_{x} = 1000$ pour les trois premières et les trois dernières valeurs, $f_{x} = 1$ pour les autres.

Dans quels cas l'abr de hauteur minimum est-il de coût minimum ? Dans quels cas l'abr glouton est-il meilleur que l'abr de hauteur minimum ?

Corrigé

Le programme Ex9Arbres.java construit les trois arbres et calcule leurs coûts (à fréquences égales, le tri des valeurs par fréquences décroissantes laisse les valeurs dans l'ordre croissant) :


fréquences égales     glouton    496 (h=30) | hauteur min    129 (h=4) | coût min    129 (h=4)
f = |x - 15|          glouton   2600 (h=30) | hauteur min   1024 (h=4) | coût min    963 (h=8)
1000 aux extrémités   glouton  21425 (h=28) | hauteur min  28101 (h=4) | coût min  14174 (h=7)

À fréquences égales, le coût est la somme des niveaux plus un : il est minimum quand l'arbre est le plus « tassé » possible, et l'abr de hauteur minimum est de coût minimum. L'abr glouton est ici une liste (insertions dans l'ordre croissant) : coût $1 + 2 + \dots + 31 = 496$ .
Avec $f_{x} = ∣ x - 15∣$ , la valeur médiane n'est jamais recherchée : la mettre à la racine gaspille un niveau. L'abr de coût minimum est plus haut ( $8$ ) mais moins coûteux ( $963$ contre $1024$ ).
Quand quelques valeurs concentrent les recherches, les placer près de la racine compte plus que l'équilibre : le glouton ( $21425$ ) bat l'abr de hauteur minimum ( $28101$ ), qui les range au fond de l'arbre. Le coût minimum ( $14174$ ) fait encore beaucoup mieux que les deux.