Activité complémentaire de l'activité Algorithmes des arbres binaires.
Nous allons voir différentes façons de rédiger une réponse permettant d'expliquer les appels récursifs.
Logiciel nécessaire pour l'activité : -
Prérequis :
Evaluation ✎ :
Documents de cours : open document ou pdf
Voici la liste des primitives :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75 | |
Le jour de l'examen, comment parvenir à retrouver la fonction récursive hauteur() ?
Définir le cas de base : quand peut-on répondre définitivement ?
Si l'Arbre Binaire est un arbre VIDE, on peut répondre : la hauteur est -1 si on prend comme convention une profondeur de 0 pour la racine.
Définir le cas récursif
Si on tombe sur un Noeud, il peut pas répondre immédiatement il doit lancer des appels récursifs. Lesquels ?
Le cas récursif doit répondre 1 + la plus grande de deux hauteurs à gauche et à droite.
Version Python
1
2
3
4
5
6
7 | |
Exemple détaillé avec la recherche de la hauteur de l'Arbre ag, l'Arbre dont la racine est G.
On notera AV l'arbre vide.
hauteur(ag) va renvoyer 1 + max(hauteur(gauche(ag)), hauteur(droite(ag))), ce qui devient
hauteur(ag) va renvoyer 1 + max(hauteur(AV), hauteur(ah)).
hauteur(AV) RENVOIE -1 (un cas de base).
hauteur(ah) va renvoyer 1 + max(hauteur(AV), hauteur(AV)) = 1 + max(-1, -1)
-> hauteur(ah) RENVOIE 0
-> hauteur(ag) RENVOIE 1
Comment rédiger cela sans y passer 15 minutes ? Deux façons de faire :
Commençons avec un exemple de rédaction de réponse complète si on vous demande des justifications :
On écrit les appels dans l'ordre d'apparition :
Ensuite, on rajoute les réponses lorsqu'elles arrivent lors du dépilement.
Il suffit alors de compléter votre rédaction au fur et à mesure des réponses qu'on parvient à obtenir.
Au final, on aura alors quelque chose qui ressemble à cela :
01° Réaliser l'empilement des appels récursifs de la fonction hauteur() sur l'arbre de racine A, qu'on notera aa. Fournir ensuite la réponse finale que va renvoyer la fonction.
1
2
3
4
5
6
7 | |
Pour avoir moins de choses à noter, écrire h() plutôt que hauteur().
...CORRECTION...
L'empilement provoque des appels à ces fonctions.
| |
Il n'y a plus qu'à dépiler et notant les résultats qu'on trouve au fur et à mesure.
| |
02° Recopier cet arbre et noter sur les arêtes parent-enfant la réponse que l'enfant va faire à son parent sur les appels à la fonction hauteur() sur l'arbre aa. Fournir ensuite la réponse finale que va renvoyer la fonction.
...CORRECTION...
03° En utilisant uniquement les fonctions d'interface (et sans regarder le code déjà fourni), retrouver le code de la fonction récursive hauteur().
Pour cela, demandez-vous quel est (ou sont) le (ou les) cas de base qui permettent de répondre immédiatement. Réflechir ensuite à la réponse qu'on peut fournir dans le cas récursif.
...CORRECTION...
1
2
3
4
5
6
7 | |
La taille correspond au nombre de noeuds.
04° Fournir le code d'une fonction taille() où le seul cas de base est l'arbre vide : on doit renvoyer 0 puisqu'il ne contient pas de noeud.
...CORRECTION...
1
2
3
4
5
6
7 | |
05° Fournir le code d'une fonction taille() qui possède deux cas de base : l'arbre vide (on renvoie 0) et la feuille (on renvoie 1).
Pour un humain, est-ce une meilleure ou une moins bonne version que la précédente ?
Pour la machine, est-ce une meilleure ou une moins bonne version que la précédente ?
...CORRECTION...
1
2
3
4
5
6
7
8
9 | |
Bien mieux pour un humain qui rédige car on atteint plus vite un cas de base (la feuille) qu'on parvient à détecter visuellement et facilement.
Par contre, pour la machine c'est moins bien : on tombe plus souvent sur des noeuds qui ne sont pas des feuillles. Et donc :
La version à un seul cas de base va donc être plus rapide.
06° Réaliser l'empilement des appels récursifs de la fonction taille() sur l'arbre de racine A, qu'on notera aa. Fournir ensuite la réponse finale que va renvoyer la fonction. On prendra l'algorithme à deux cas de base pour limiter les appels récursifs : sur le cas d'une feuille, on peut répondre immédiatement.
...CORRECTION...
07° Dessiner l'arbre ci-dessous et noter sur les arêtes parent-enfant le résultat que l'enfant envoie à son parent lors de l'utilisation de taille(). Fournir ensuite la réponse finale que va renvoyer la fonction. On prendra l'algorithme à deux cas de base pour limiter les appels récursifs : sur le cas d'une feuille, on peut répondre immédiatement.
...CORRECTION...
Voyons également comment trouver
08° Que doit renvoyer la fonction récursive nb_f() qui compte les feuilles sur le cas de base "Arbre Vide" ? Sur le cas de base "Feuille" ? Comment tester qu'un arbre est en réalité constitué uniquement d'une feuille ?
Fournir alors le code de la fonction récursive nb_f().
...CORRECTION...
Si l'arbre est vide : on renvoie 0.
Si l'arbre est constitué uniquement une feuille : on renvoie 1.
L'arbre est constitué d'une feuille si les sous-arbres gauche et droite sont des arbres vides.
Sinon, c'est le cas récursif : on renvoie la somme de l'appel de cette fonction à gauche et de l'appel à droite.
1
2
3
4
5
6
7
8
9 | |
09° Réaliser l'empilement des appels récursifs de la fonction nb_f() sur l'arbre de racine A, qu'on notera aa. Fournir ensuite la réponse finale que va renvoyer la fonction.
...CORRECTION...
10° Recopier cet arbre et noter sur les arêtes parent-enfant les réponses que fournissent les enfants à leur parent sur un appel de la fonction nb_f() sur l'arbre aa. Fournir ensuite la réponse finale que va renvoyer la fonction.
...CORRECTION...
11° Réaliser le prédicat est_present(). La fonction doit renvoyer True si la clé fournie apparaît bien dans l'Arbre Binaire.
Question subsidiaire : quel est le seul cas où un OU renvoie False ?
1
2
3 | |
...CORRECTION...
1
2
3
4
5
6
7
8
9 | |
12° Réaliser l'empilement des appels récursifs de la fonction est_present() sur l'arbre de racine A en recherchant la clé "B". Fournir ensuite la réponse finale que va renvoyer la fonction. N'oubliez pas que le OU et le ET sont paresseux en Python : si la lecture du premier terme permet de répondre, on n'évalue pas le deuxième terme.
...CORRECTION...
13° Réaliser l'empilement des appels récursifs de la fonction est_present() sur l'arbre de racine A en recherchant la clé "C". Fournir ensuite la réponse finale que va renvoyer la fonction. N'oubliez pas que le OU et le ET sont paresseux en Python.
...CORRECTION...
14° Calculer ceci avec Python.
>>> from math import log2
>>> log2(2**3)
>>> log2(2**8)
>>> log2(2**27)
Que vaut log2(2x) visiblement ?
...CORRECTION...
>>> from math import log2
>>> log2(2**3)
3.0
>>> log2(2**8)
8.0
>>> log2(2**27)
27.0
Ce n'est pas une démonstration, mais on constate qu'on peut certainement écrire log2(2x) = x.
15° Calculer ceci avec Python.
>>> from math import log2
>>> 2**(log2(3))
>>> 2**(log2(13))
>>> 2**(log2(23))
Que vaut 2log2(x) à priori ?
...CORRECTION...
>>> from math import log2
>>> 2**(log2(3))
3.0
>>> 2**(log2(13))
13.0
>>> 2**(log2(26))
25.999999999999993
Ce n'est pas une démonstration, mais on constate qu'on peut certainement écrire 2log2(x) = x.
Le dernier cas pourrait être interprété comme le fait que la formule n'est pas totalement exacte, mais il s'agit bien entendu d'un exemple de l'inexactitude des calculs sur les flottants par un ordinateur.
Les rappels ci-dessous sont à lire uniquement si vous ne savez plus de quoi ils parlent.
Un arbre est parfait lorsqu'il ne manque aucun noeud.
On dit qu'un est complet lorsque les noeuds manquants sont uniquement sur son dernier étage.
Lorsque chaque noeud possède au maximum un seul enfant, on dit qu'il est dégénéré.
Lorsque l'arbre comporte uniquement des sous-arbres d'un côté identique, on dit qu'il est filiforme. Il pourrait représenter une liste.
Mais ce vocabulaire n'est pas si défini que cela. Certains utilisent des termes différents. On trouve parfois :
Un arbre binaire parfait est un arbre binaire où le dernier niveau est entièrement composé de Feuilles.
Exemple avec un Arbre Binaire Parfait de hauteur 3 si on prend une profondeur de 1 pour la racine :
L'arbre binaire parfait est la meilleure configuration en terme de réduction de la hauteur.
Pour un Arbre Binaire Parfait, la hauteur h est liée au log2 de la taille n quelque que soit la convention :
h = log2(n+1) (avec la convention PR=1)
Sur l'exemple : h = log2(7+1)= log2(8) = log2(23) = 3
Pour un arbre binaire parfait, la taille n est liée à une puissance de 2 de la hauteur h quelque que soit la convention. Avec la convention choisie ici, cela donne :
n = 2h - 1 (avec la convention PR=1)
Sur l'exemple : n = 2h - 1 = 23 - 1= 8 - 1 = 7
L'Arbre Binaire Filiforme est la pire configuration en terme de réduction de la hauteur.
h = n (avec la convention PR=1)
Le plus simple est d'apprendre par coeur ces trois formules, valables avec la convention profondeur 1 :
h = n (avec convention profondeur 1)
h = log2(n+1) (avec convention profondeur 1)
n = 2h - 1 (avec convention profondeur 1)
Les deux cas extrêmes sont :
A savoir : pour un arbre filiforme, l'ordre de grandeur de h est en n.
A savoir : pour un arbre parfait, l'ordre de grandeur de h est en lg(n).
Un arbre binaire quelconque est situé entre ces deux cas extrêmes. On peut encadrer la hauteur de l'arbre binaire quelconque à l'aide de l'une des formules suivantes.
Pour un arbre binaire quelconque :
⌈log2(n+1)⌉ ≤ h ≤ n (formule valable si profondeur 1 pour la racine)
Les signes ⌈ ⌉ indiquent un arrondi à l'entier supérieur (demi-crochets vers le haut).
>>> import math
>>> math.log2(15+1)
4.0
# n = 15 donc h=4 au minimum
>>> math.log2(16+1)
4.087462841250339
# Pour n = 16, on arrondi à 5 : h=5 au minimum
On voit alors qu'un arbre de 15 noeuds a une hauteur comprise dans [4; 15].
Par contre, avec 16 noeuds, on obtient une hauteur comprise dans [5;16].
C'est normal : avec 15 noeuds, l'arbre peut être parfait. Si on en rajoute un, il faut nécessairement rajouter un étage...
Pour un arbre binaire quelconque :
⌈log2(n+1)⌉ - 1 ≤ h ≤ n - 1 (formule valable si profondeur 0 pour la racine)
>>> import math
>>> math.log2(15+1)
4.0
# Pour n = 15, on calcule donc h=(4-1)=3 au minimum
>>> math.log2(16+1)
4.087462841250339
# Pour n = 16, on arrondit à 5 et on calcule h=(5-1)=4 au minimum
Ou encore cette autre formule :
⌊log2(n)⌋ ≤ h ≤ n - 1 (formule valable si profondeur 0 pour la racine)
Les signes ⌊ ⌋ indiquent un arrondi à l'entier inférieur (demi-crochets vers le bas).
>>> import math
>>> math.log2(15)
3.9068905956085187
Pour n=15, on arrondit donc à 3 et on a h=3 au minimum
>>> math.log2(16)
4.0
Pour n=16, on arrondit donc à 4 et on a h=4 au minimum
L'ordre de grandeur de la hauteur d'un Arbre Binaire est compris entre log2(n) et n.
16-A° Si on ne sait pas comment cibler la recherche dans un arbre binaire (c'est à dire utiliser la différence de position entre sous-arbre gauche et droite), quel est le coût (dans le pire des cas) d'une recherche NON CIBLEE qui doit trouver un noeud dans un arbre binaire de taille n ?
...CORRECTION...
On doit fouiller l'arbre binaire noeud par noeud.
Le coût est donc linéaire par rapport à n.
Si on ne sait pas comment utiliser les propriétés de l'arbre, qu'on ai un arbre binaire parfait ou filiforme, il faut donc chercher un peu au hasard.
16-B° Une recherche NON CIBLEE dans un arbre binaire est-elle efficace que dans une Listen ?
...CORRECTION...
Non, puisque la recherche dans une Liste est également à coût linéaire par rapport au nombre n de Places/Cases/Cellules.
Regardons maintenant la différence d'efficacité si on sait où chercher.
17-A° Répondre à ces questions :
...CORRECTION...
En partant de la racine Alice, on a trois choses à faire :
Avec cet arbre de hauteur 3, on a donc 3 noeuds à parcourir.
17-B° Le coût d'une recherche ciblée dans un arbre binaire est donc linéaire en h.
Est-ce que la convention choisie a une influence sur ce coût asymptotique ?
...CORRECTION...
Aucune différence car lorsqu'on détermine le coût, on cherche ce qui se passe lorsque h devient très grand.
O(h-1) = O(h+1) = O(h) : on ne tient pas compte des facteurs constants.<Tout ce qui nous intéresse est de savoir globalement comment l'algorithme va réagir à l'augmentation des données.
Ici, c'est bien linéaire en h à chaque fois.
17-C° En déduire le coût de la recherche CIBLEE dans un arbre binaire FILIFORME en fonction de la taille n de l'arbre. Choisir parmi :
...CORRECTION...
La complexité de la recherche ciblée est O(h).
Dans le cas filiforme, h est de l'ordre de n quelque soit la convention.
La complexité de la recherche est donc O(n) et donc linéaire par rapport à n.
17-D° En déduire le coût de la recherche CIBLEE dans un arbre binaire PARFAIT en fonction de la taille n de l'arbre. Choisir parmi :
...CORRECTION...
La complexité de la recherche ciblée est O(h).
Dans le cas parfait, h est de l'ordre de log2(n) quelque soit la convention.
La complexité de la recherche est donc O(log2(n)), logarithmique par rapport à n.
Le coût de la recherche ciblée dans un arbre quelconque est donc compris entre le coût logarithmique et le coût linéaire.
Recherche non ciblée est linéaire en n : 𝓞(n)
Recherche ciblée est linéaire en h :
Il faut différencier la recherche non ciblée et ciblée.
La recherche non ciblée est linéaire en n, aucun avantage par rapport à une Liste.
On peut noter 𝓞(n) puisqu'on peut tomber par hasard sur le bon résultat avant la fin de l'exploration.
La recherche ciblée est linéaire en h, cela veut dire que son efficacité va dépendre de la forme réelle de l'arbre.
On peut noter 𝓞(h) puisqu'on peut tomber par hasard sur le bon résultat avant la fin de l'exploration.
Mais attention, cette fois la valeur de h va dépendre de la forme de l'arbre :
On peut noter 𝓞(log2(n))
On peut noter 𝓞(n)
On peut noter 𝓞(n)
16° Montrer qu'on peut passer de la formule (1) à la formule (2).
h = log2(n+1) ( Formule 1)
n = 2h - 1 ( Formule 2)
...CORRECTION...
On part de cela la formule 1.
Formule (1)
h = log2(n+1)
2h = 2log2(n+1)
On sait que 2log2(x) = x car ces deux fonctions sont reciproques.
2h = n + 1
Il suffit de passer +1 dans le membre de gauche :
2h - 1 = n
On obtient bien la formule (2) :
n = 2h - 1
17° Quelle est la taille n d'un arbre binaire parfait de hauteur 11 (avec la convention pR = 1) ?
...CORRECTION...
>>> 2**(11) - 1
2047
Un arbre binaire parfait de 11 étages possède donc 2047 Noeuds.
Comment calculer cela sans calculatrice ? Il faut énumérer les cas un par un jusqu'au bon.
2**1 = 2.
2**2 = 4.
2**3 = 8.
2**4 = 16.
2**5 = 32.
2**6 = 64.
2**7 = 128.
2**8 = 256.
2**9 = 512.
2**10 = 1024.
2**11 = 2048.
18° Un Arbre Binaire de 500 Noeuds peut-il être parfait ?
...CORRECTION...
On peut faire un raisonnement par l'absurde :
Hypothèse : on considère qu'il l'est. On peut donc utiliser la formule permettant de trouver sa hauteur :
h = log2(n+1) (avec PR=1)
Il faut donc calculer h = log2(500+1) sans calculatrice.
On sait que :
log2(1) = log2(20) = 0
log2(2) = log2(21) = 1
log2(4) = log2(22) = 2
log2(8) = log2(23) = 3
log2(16) = log2(24) = 4
log2(32) = log2(25) = 5
log2(64) = log2(26) = 6
log2(128) = log2(27) = 7
log2(256) = log2(28) = 8
log2(512) = log2(29) = 9
Puisque la fonction log2 est croissante et continue, on en déduit que h = log2(501) ne peut pas être entière car cela vaut 8,...
On tombe sur un résultat qui n'est pas un entier : c'est donc que l'hypothèse est fausse, un arbre binaire de 500 noeuds ne peut pas être un Arbre Binaire Parfait.
Remarque :
>>> from math import log2
>>> log2(500+1)
8.968666793195208
Activité publiée le 13 12 2020
Dernière modification : 13 12 2020
Auteur : ows. h.