22 - 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 parfois
- les étiquettes pour un Arbre et
- les clés pour un Arbre Binaire de Recherche.
Mais rien n'est écrit dans le marbre non plus.
Documents de cours : open document ou pdf
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 directs 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 deux fils 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
Profondeur 1 pour la racine :
Arbre binaire complet : h = log2(n+1)
Arbre binaire filiforme : h = n
Pour un arbre binaire quelconque :
⌈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 :
Arbre binaire complet : h = log2(n+1) - 1
Arbre binaire filiforme : h = n - 1
Pour un arbre binaire quelconque :
⌊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...
Ordre de grandeur de la hauteur d'un arbre (à connaître par coeur) :
L'ordre de grandeur de la hauteur d'un Arbre est comprise entre log2(n) et n.
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 Complet 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 - Le Labyrinthe : un choix courant en réalité
Voici un mini-labyrinthe que nous avions utilisé pendant l'activité sur les matrices :
16° Dessiner l'arbre obtenu en prenant comme point de départ le magicien (c'est la racine). Déterminer la hauteur du labyrinthe. Déterminer alors les cases du plateau les plus éloignées où vous pourriez mettre la sortie.
17° Montrer, à partir de l'arbre, qu'on n'offre que 3 vrais choix au joueur et qu'il faut 7 mouvements au maximum pour sortir du labyrinthe.
Ce type de problèmes avec prise de décisions multiples est assez courant. Et à chaque fois, on en revient à une réprésentation sous forme d'arbres. Du coup, quelque soit le problème réel (un labyrinthe, un livre dont vous êtes le héros, une chaîne de production de voitures, un choix de position des thèmes dans un célèbre magasin d'ammeublements), on en revient à un simple arbre. Le tout, c'est qu'il n'y ai pas de boucles (sinon, c'est un problème de graphes).
Il est donc temps de voir comment parcourir ces arbres à l'aide de méthodes algorithmiques. La suite est donc dans la partie ALGO.
6 - FAQ
Rien pour l'instant
Activité publiée le 29 11 2020
Dernière modification : 29 11 2020
Auteur : ows. h.