Exercices sur les Arbres
Quelques exercices sur les arbres avant d'aborder les algorithmes qui nous permettront de traiter les données contenues dans les noeuds, données qu'on nomme
- les étiquettes pour un Arbre
- les clés pour un Arbre Binaire de Recherche.
1 - Caractéristiques générales des arbres
01° Donner la racine de l'arbre, la taille de l'arbre et la hauteur de l'arbre en considérant que la hauteur de la racine est de 1. ?
Terminer en donnant le nombre de feuilles.
...CORRECTION...
La racine est le noeud noté HTML.
Taille de 23 car 23 noeuds.
Si on prend une profondeur de 1 pour la racine, on obtient une hauteur d'Arbre de 5.
On compte 15 feuilles.
02° Pourquoi ne peut-on pas considérer qu'il s'agit d'un Arbre Binaire ? Comment nomme-t-on ce type d'arbre qui possède une hierarchie ?
Quel critère est utilisé pour créer la hierarchie ?
...CORRECTION...
Non : certains noeuds ont plus de 2 fils.
Il s'agit d'une arborescence.
Le critère de sélection est le fait que certaines balises sont contenues dans d'autres balises : la balise HTML contenant toutes les autres balises, elle est la racine.
2 - Arbre Binaire ou pas ?
03° Alice désire représenter ses ancêtres directes de cette façon.
Quelle est la taille de cet arbre ? Sa racine ? La hauteur de l'arbre ?
...CORRECTION...
La taille de l'arbre est 1+2+4 = 7.
La racine est le noeud Alice.
Sa hauteur est de 3 si on considère que la hauteur d'Alice est de 1.
Taille de 23 car 23 noeuds.
04° En terme de nombre de fils par noeud, peut-on considérer qu'il s'agit d'un Arbre Binaire ? Est-ce suffisant ?
...CORRECTION...
Chaque noeud a bien des fils-noeuds au maximum.
On peut ainsi dire que chaque arbre possède deux sous-arbres, au pire des arbres vides.
Mais pour dire qu'il s'agit d'un Arbre Binaire, il faut que la place d'un noeud à gauche ou à droite ai une signification.
05° Quelle est l'information encodée par la position gauche ou droite d'un fils dans cet arbre ? Peut-on alors dire qu'il s'agit d'un arbre binaire ?
...CORRECTION...
Placer un noeud à gauche signifie qu'il s'agit d'un homme. Placer un noeud à droite signifie qu'il s'agit d'une femme.
Il s'agit donc bien d'un Arbre Binaire car on distingue le rôle d'un fils gauche et d'un fils droite.
06° Devinez quelle pourrait être l'information encodée par la position gauche ou droite d'un fils dans cet autre Arbre Binaire...
Remarque : comme je signale qu'il s'agit d'un Arbre Binaire, gauche et droite ont nécessairement une signification.
...CORRECTION...
On place à droite un noeud-fils dont le prénom étiquette est du même sexe que le prénom-étiquette du noeud lui même.
Si le sexe est différent, il s'agit d'un fils gauche.
3 - Hauteur des Arbres Binaires
Dans la suite des activités, nous prendrons une profondeur de 0 pour les racines par défaut si aucune information n'est fournie.
Estimation de la hauteur h d'un Arbre Binaire connaissant sa taille n
Les deux cas extrêmes étant :
- Arbre binaire filiforme
- Arbre binaire complet
On en déduit que pour un arbre binaire quelconque, situé entre ces deux cas particuliers extrêmes, on peut encadrer la hauteur h de l'arbre binaire quelconque à l'aide de la formule suivante :
Profondeur 1 pour la racine :
⌈log2(n+1)⌉ ≤ h ≤ n
On notera que les signes ⌈ ⌉ indiquent simplement un arrondi à l'entier supérieur.
>>> import math
>>> math.log2(15+1)
4.0
>>> math.log2(16+1)
4.087462841250339
On voit alors qu'un arbre de 15 noeuds à 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 serait complet dans le meilleur des cas. Si on en rajoute un, il faut nécessairement rajouter un étage...
Profondeur 0 pour la racine :
⌊log2(n)⌋ ≤ h ≤ n - 1
Cette fois, les signes ⌊ ⌋ veulent dire d'arrondir à l'inférieur.
>>> import math
>>> math.log2(15)
3.9068905956085187
>>> math.log2(16)
4.0
On voit alors qu'un arbre de 15 noeuds à une hauteur comprise dans [3; 14].
Par contre, avec 16 noeuds, on obtient une hauteur comprise dans [4;15].
C'est normal : avec 15 noeuds, l'arbre serait complet dans le meilleur des cas. Si on en rajoute un, il faut nécessairement rajouter un étage...
07° Encader (sans calculatrice) la hauteur d'un Arbre Binaire quelconque possèdant 120 noeuds. On prendra une profondeur de 0 pour la racine. Est-ce qu'il peut s'agir d'un Arbre Binaire complet ?
...CORRECTION...
Profondeur 0 pour la racine : ⌊log2(n)⌋ ≤ h ≤ n - 1
La borne maximale est 119, facile (120-1).
Pour la borne minimale, il faut calculer log2(120). De tête !
Enfin, pas vraiment : il faut trouver l'arrondi à l'inférieur de log2(120).
Or, on sait que :
- log2(2) = log2(21) qui vaut 1.
- log2(4) = log2(22) qui vaut 2.
- log2(8) = log2(23) qui vaut 3.
- log2(16) = log2(24) qui vaut 4.
- log2(32) = log2(25) qui vaut 5.
- log2(64) = log2(26) qui vaut 6.
- log2(128) = log2(27) qui vaut 7.
On peut donc en déduire que log2(120) vaut 6 virgule quelque chose.
Si on arrondit à l'inférieur, on aura 6.
On peut donc écrire ceci pour un Arbre Binaire quelconque de 120 noeuds
6 ≤ h ≤ 119
Il ne peut pas s'agit d'un Arbre Binaire complet : il aura fallu 63 ou 127 noeuds.
08° Encader (sans calculatrice) la hauteur d'un Arbre Binaire quelconque possèdant 50 noeuds. On prendra une profondeur de 1 pour la racine.
...CORRECTION...
Profondeur 1 pour la racine : ⌈log2(n+1)⌉ ≤ h ≤ n
La borne maximale est 50, facile.
Pour la borne minimale, il faut trouver log2(51)
- log2(2) = log2(21) qui vaut 1.
- log2(4) = log2(22) qui vaut 2.
- log2(8) = log2(23) qui vaut 3.
- log2(16) = log2(24) qui vaut 4.
- log2(32) = log2(25) qui vaut 5.
- log2(64) = log2(26) qui vaut 6.
On peut donc en déduire que log2(51) vaut 5 virgule quelque chose.
Si on arrondit au supérieur, on aura 6.
On peut donc écrire ceci pour un Arbre Binaire quelconque de 50 noeuds
6 ≤ h ≤ 50
09° Encader (sans calculatrice) la hauteur d'un Arbre Binaire quelconque possèdant 34 noeuds. Attention, on prendra cette fois la formule pour une profondeur de 0 pour la racine.
...CORRECTION...
Profondeur 0 pour la racine :⌊log2(n)⌋ ≤ h ≤ n - 1
La borne maximale est 33 (n-1), facile.
Pour la borne minimale, il faut trouver l'arrondi inférieur de log2(34)
- log2(2) = log2(21) qui vaut 1.
- log2(4) = log2(22) qui vaut 2.
- log2(8) = log2(23) qui vaut 3.
- log2(16) = log2(24) qui vaut 4.
- log2(32) = log2(25) qui vaut 5.
- log2(64) = log2(26) qui vaut 6.
On peut donc en déduire que log2(34) vaut 5 virgule quelque chose.
Si on arrondit à l'inférieur, on aura 5.
On peut donc écrire ceci pour un Arbre Binaire quelconque de 34 noeuds
5 ≤ h ≤ 33
10° Quelle est la taille d'un Arbre Binaire de hauteur 0, 1, 2 jusqu'à 5 si on considère que la profondeur de la racine est de 0 ?
...CORRECTION...
Pour une profondeur de racine de 0 :
Hauteur h = 0 : Taille n = 1, facile.
Hauteur h = 1 : Taille n = 1 + 2 = 3
Hauteur h = 2 : Taille n = 1 + 2 + 4 = 7
Hauteur h = 3 : Taille n = 1 + 2 + 4 + 8 = 15
Hauteur h = 4 : Taille n = 1 + 2 + 4 + 8 + 16 = 31
Hauteur h = 5 : Taille n = 1 + 2 + 4 + 8 + 16 + 32 = 63
11° Retrouver alors la formule permettant de trouver le nombre de noeuds d'un arbre complet de hauteur connue. Fournir les deux formules (cas d'une profondeur 0 ou 1 pour la racine)
...CORRECTION...
Pour une profondeur de racine de 0 :
Hauteur h = 0 : Taille n = 1, facile.
Hauteur h = 1 : Taille n = 1 + 2 = 3
Hauteur h = 2 : Taille n = 1 + 2 + 4 = 7
Hauteur h = 3 : Taille n = 1 + 2 + 4 + 8 = 15
Hauteur h = 4 : Taille n = 1 + 2 + 4 + 8 + 16 = 31
Hauteur h = 5 : Taille n = 1 + 2 + 4 + 8 + 16 + 32 = 63
On voit qu'il suffit de faire ceci :
n = 2h+1 - 1
Dans le cas d'une profondeur 1 pour la racine, on a alors simplement
Hauteur h = 1 : Taille n = 1, facile.
Hauteur h = 2 : Taille n = 1 + 2 = 3
Hauteur h = 3 : Taille n = 1 + 2 + 4 = 7
Hauteur h = 4 : Taille n = 1 + 2 + 4 + 8 = 15
Hauteur h = 5 : Taille n = 1 + 2 + 4 + 8 + 16 = 31
Hauteur h = 6 : Taille n = 1 + 2 + 4 + 8 + 16 + 32 = 63
n = 2h - 1
4 - Arbre Binaire ou pas ?
12° Doit-on considérer cet Arbre comme un Arbre Binaire ou pas ? Que porte l'étiquette des noeuds-pères comme information ?
...CORRECTION...
A priori ici gauche et droite n'ont pas de signification réelle : les deux fils sont simplement les deux équipes qui se rencontrent et le père porte comme clé le nom de l'équipe qui a gagné.
Il s'agit donc d'un Arbre où chaque noeud-père a au plus deux fils mais il ne s'agit pas d'un Arbre Binaire a proprement parlé car on peut inverser la position gauche-droite d'un fils sans que cela n'ai de conséquence sur l'information stockée.
13° Dans un Arbre, des noeuds différents peuvent-ils porter des étiquettes identiques ?
...CORRECTION...
Oui, aucun problème.
On voit bien que l'étiquette France est attaché à trois noeuds différents.
14° Même si ce problème n'est pas exactement représentable comme un Arbre Binaire (si on ne donne pas de sens particulier au fils gauche par rapport au fils droit), peut-on utiliser l'encadrement de la taille du cas de l'arbre binaire quelconque ?
...CORRECTION...
Oui : dans le cas des matchs, chaque noeud aura bien 2 fils-noeuds ou sera une feuille (et aura donc deux fils vides).
On peut donc utiliser les formules d'encadrement de la hauteur puisque la propriété de distinction n'intervient pas dans sa démonstration.
15° Quelle est la hauteur de l'arbre "presque vraiment binaire" qui représenterait une compétition du type précédent où il y aurait 64 équipes au départ ?
...CORRECTION...
Il suffit de compter les étages pour obtenir la hauteur puisqu'il s'agit de l'équivalent d'un Arbre Binaire complet.
Les feuilles sont 64 (profondeur +1)
Au dessus, on trouve 32 noeuds (profondeur +2)
Puis encore 16 noeuds (profondeur +3)
Puis encore 8 noeuds (profondeur +4)
Puis encore 4 noeuds (profondeur +5)
Puis encore 2 noeuds (profondeur +6)
Puis la racine : si on lui donne une profondeur de 0, on obtient donc une hauteur de 6.
Nous aurions pu retrouver ce résultat en utilisant simplement la borne inférieure de l'encadrement puisque nous obtenons ici le cas le plus petit :
h =
⌊ log2(64+32+16+8+4+2+1) ⌋ =
⌊ log2(127) ⌋ =
⌊ 6.9886846867721655 ⌋ =
6
Si on considère que la profondeur de la racine est 0, on obtient 6. Si la profondeur est 1, on prendra 7.
5 - FAQ
Rien pour l'instant
Activité publiée le 04 02 2021
Auteur : Andjekel
Sources : Infoforall