9 - Exercices Formules sur les AB
Exerices sur les formules des arbres binaires.
Exercices liés à cette activité Données Exercices sur les Arbres
01° Que pouvez-vous dire des fonctions log2(x) et 2x ?
...CORRECTION...
Ce sont des fonction réciproques.
log2( 2x ) = x
2log2(x) = x
02° Voyons comment retrouver la formule de la hauteur d'un arbre binaire parfait le jour de l'examen.
Dessiner un arbre binaire parfait ayant 7 noeuds..
Donner la formule permettant de calculer la hauteur h d'un arbre parfait en fonction de n ( en convention pR = 1).
...CORRECTION...

7 n'est pas une puissance de 2.
Par contre 7+1 = 8 = 23.
Ce 3 correspond bien à la hauteur h de l'arbre parfait si n=7.
On en déduit la formule suivante :
h = log2(n+1) (avec la convention pR = 1)
03° En déduire h=f(n) avec pR = 0.
...CORRECTION...
h = log2(n+1) - 1 (avec la convention pR = 0)
04° Justifier qu'un arbre de 14 noeuds puisse être parfait, ou pas.
SANS CALCULATRICE
...CORRECTION...
On utilise h = log2(n+1) et on tente de voir si on peut obtenir un entier.
log2(2) = log2(21) = 1
log2(4) = log2(22) = 2
log2(8) = log2(23) = 3
log2(16) = log2(24) = 4
La fonction logarithme est croissante et continue.
On doit calculer h = log2(14+1) = log2(15).
8 < 15 < 16
log2(8) < log2(15) < log2(16)
3 < log2(15) < 4
Le log ne peut donc pas fournir un entier et l'arbre n'est donc pas parfait.
05° Utiliser la formule fournie pour encadrer la hauteur d'un arbre de 17 noeuds.
⌈log2(n+1)⌉ ≤ h ≤ n (formule valable si profondeur 1 pour la racine)
...CORRECTION...
L'arbre quelconque a une forme entre filiforme et parfait.
h = n = 17 pour le cas filiforme.
Pour l'autre cas, il faut calculer log2(18) et arrondir au supérieur.
log2(16) = log2(24) = 4
log2(32) = log2(25) = 5
La fonction logarithme étant croissante et continue, on en déduit que h = log2(18) = 4,.... Si on arrondit au supérieur, on obtient 5.
Conclusion :
5 ≤ h ≤ 17 (formule valable si profondeur 1 pour la racine)
FIN
Activité publiée le 26 01 2025
Dernière modification : 26 01 2025
Auteur : ows. h.