Vous connaissez déjà ce type de structure en réalité.
Elle est assez courante dans la vie de tous les jours : l'arbre généalogique, vous connaissez ?
En informatique, l'arbre est présent un peu partout. Ainsi, en HTML, les balises qui se succèdent et s'imbriquent les unes dans les autres forment un arbre : l'arbre DOM (pour Document Object Model).
Ci-dessous, un exemple de code HTML et l'arbre correspondant.
<!DOCTYPE html><html><head></head><body><header><h3>Le titre de mon site</h3></header><nav><ul><li>Accueil</li><li>Partie 1</li><li>Partie 2</li></ul></nav><main><h1>Le titre de ma page.</h1><h2>1 Première partie</h2><div><p>Bla bla.</p><p>Encore du Bla bla.</p><p>Toujours du Bla bla.</p></div><h2>2 Deuxième partie</h2><p>Encore du blabla.</p></main><footer><p>Pour contacter le webmaster, on met son adresse ici.</p><p>Pour l'instant, il préfère rester discret :</p><p>le contenu n'est pas très conséquent.</p></footer></body></html>
Visualisation de l'arbre DOM en version montante
Visuellement, c'est clair : cela forme un arbre.
INTRO : représentatin des arbres en informatique
La représentation graphique d'un arbre est plutôt faite avec la racine en haut et les feuilles en bas en informatique.
Visualisation de l'arbre DOM en version descendante
Pourquoi ?
Nous allons voir que l'arbre est une structure hierarchique : on place donc la donné la plus importante en haut (la racine) et les données situées tout en bas sont en bas de la hierarchie (les feuilles).
En terme de recherche, c'est très pratique : on part de la racine et on choisit une direction lors de la descente vers l'une des feuilles.
01° L'élément html joue un rôle particulier puisqu'il n'est pas contenu dans une autre balise. Cet élément est la racine de notre arbre. Combien de choix de direction doit-on faire pour trouver la balise div en partant de cette racine html ?
...CORRECTION...
On part de la balise html, la racine et on voit qu'il faut partir vers la balise body. Ensuite, main. Et on localise notre balise div. 3 recherches donc.
1.1 Qu'est-ce qui n'est pas un arbre enraciné ?
Regardons d'abord les structures qui ne sont pas des arbres enracinés :
Exemple 1 : ceci n'est pas un arbre car on y trouve un cycle. C'est un graphe.
Exemple 2 : ceci n'est pas un arbre car l'objet obtenu n'est pas connexe : on trouve des couples de points sans chemin de l'un à l'autre. C'est une forêt, un ensemble de plusieurs arbres.
Exemple 3 : ceci est un arbre mais ce n'est pas un arbre enraciné : il manque une information, on ne voit pas de racine.
Pas de cycle : ok
La structure est connexe : ok.
mais il manque un noeud de départ, une racine.
Il s'agit bien d'un arbre mais on se limitera cette année aux structures hierarchiques : il faut que l'un des sommets ai un rôle particulier qui sert de point de départ. On nommera ce noeud la racine.
Si vous tombez sur une représentation de ce type, il suffit donc de choisir l'un des noeuds comme étant la racine et vous obtiendrez un arbre enraciné.
1.2 L'idée générale du type abstrait ARBRE ENRACINE (1er partie de la définition)
Principe général d'organisation
Un arbre enraciné est un type abstrait ayant les propriétés suivantes (on parle ici des arborescences) :
Il est composé de noeuds contenant au moins deux informations :
Une donnée d'un type donnée (un nombre, un string...);
Les adresses de ses noeuds-successeurs éventuels.
On hiérarchise les noeuds entre eux et il en existe trois types :
Une racine unique : ce noeud est particulier car il est le seul à ne pas posséder de noeud-parent. Il est tout en haut de la hiérarchie.
possède pas de fils.
Les noeuds internes : il s'agit des noeuds qui ont un noeud-parent et possède un ou plusieurs noeuds-enfants.
Les feuilles : il s'agit des noeuds qui ont un noeud-parent mais qui n'ont pas de noeud-enfant.
Le terme noeud générique fait donc référence à la racine, aux noeuds internes et aux feuilles.
Exemple
Voici un exemple où
les noeuds sont des caractéristiques
les feuilles sont des espèces
Image tirée d'une activité CC-BY-NC-SA La Main à la Pâte de Guillaume Lecointre
Exemple 2
Un exemple tiré des noms de domaines (et du système DNS) :
La RACINE se nomme point.
Cette racine possède 6 enfants : com, net, org, mil, fr, xxx.
Le noeud interne fr possède un enfant : inforall.
Le noeud interne infoforall possède trois enfants : www, doc et formation.
Les feuilles de cet arbre sont com, net, org, mil, xxx, www, doc et formation.
Deux noeuds peuvent très bien porter la même étiquette sans qu'on les confonde en cas de recherche, ils n'auront pas le même parent.
Exemple : www.sitea.com et www.siteb.com : il y a deux noeuds portant une étiquette www mais ils n'ont pas le même parent. Pas de confusion possible.
02° Représenter l'arborescence de l'ordinateur dont on vous fournit la structure suivant :
📁 / (la racine de l'ordinateur)
📁 bin
📄 fichierA
📁 home
📁 testprofad
📁 admin
📄 fichierB
📁 www
📁 repC
📄 fichierC
...CORRECTION...
03° Représenter l'arbre d'une maison ou d'un appartement dont vous connaissez la structure.
Chaque noeud est une pièce ou un escalier;
Les liaisons sont celles qui permettent de passer d'un noeud ou à un autre;
La racine sera liée à l'entrée principale;
Important : s'il existe des cycles dans le vrai lieu, vous supprimerez certaines liaisons pour obtenir un arbre.
...CORRECTION...
04° Représenter maintenant la même situation mais en changeant de racine : vous prendrez comme racine une autre salle que l'entrée principale. Obtient-on le même arbre ?
...CORRECTION...
05° Dans le cas d'une recherche orientée à l'aide d'un arbre, le choix de la racine est-il important ? Répondre en montrant qu'aux questions 03 et 04 certaines salles n'auront pas le même éloignement de la racine.
1.3 Définition d'un arbre enraciné à partir des noeuds
Définition : un arbre enraciné est composé d'au moins un noeud particulier : une racine.
Avec cette définition, on voit qu'un arbre enraciné ne peut pas être vide : il y a toujours au moins la racine.
L'arbre est une structure récursive puisqu'un arbre contient potentiellement d'autres arbres.
06° Combien d'arbres enracinés peut-on définir sur cet arbre ?
...CORRECTION...
Il y a 7 arbres en tout :
L'arbre enraciné abr_A dont la racine est le noeud est A.
L'arbre enraciné abr_C dont la racine est le noeud est C.
L'arbre enraciné abr_B dont la racine est le noeud est B.
L'arbre enraciné abr_G dont la racine est le noeud est G.
L'arbre enraciné abr_D dont la racine est le noeud est D.
L'arbre enraciné abr_E dont la racine est le noeud est E.
L'arbre enraciné abr_F dont la racine est le noeud est F.
Non, un arbre enraciné ne peut pas être vide : il contient toujours au moins son noeud-racine.
08° Quelle est la racine cet arbre ? Quelles sont les 4 feuilles de cet arbre ? Quels sont le ou les enfants du noeud E ?
...CORRECTION...
La racine est le noeud A.
Les 4 feuilles sont les noeuds d'étiquette B G D et F.
L'enfant du noeud-interne E est le noeud F.
09° Représentez l'arbre enraciné obtenu si on considère que la racine est plutôt le noeud D.
Si on veut utiliser cette structure dans le but de faire des recherches, vaut-il mieux utiliser l'arbre enraciné en A ou l'arbre enraciné en D ?
...CORRECTION...
L'arbre enraciné en D est plus profond, il y aura plus de décisions à prendre. La racine précédente permettait une meilleur optimisation : on atteint plus rapidement les feuilles.
10° Trois questions :
Représenter un arbre qui serait la représentation directe d'une liste dont :
la tête est 5 et
la queue 10->15->20->25->30->35.
Quelle est la caractéristique en terme de nombre d'enfants qu'on obtient sur ce cas particulier d'arbre enraciné ?
Peut-on vraiment considérer qu'une liste est un cas particulier d'arbre enraciné ?
...CORRECTION...
Cela donnerait un arbre en forme de tige : la racine est 5 et la feuille le 35.
Le 5 est la racine qui mène à 10, le 10 mène à 15...
Il s'agit d'un cas particulier d'arbre : celui où chaque noeud n'a qu'un enfant au maximum. On nommerait cet enfant le successeur sur une liste.
Par contre, une Liste n'est pas réellement un cas particulier d'arbre enraciné : une Liste peut être vide, un arbre enraciné est nécessairement non vide !
2.1 L'idée générale de l'arbre binaire (1er partie de la définition)
A - Définition récursive d'un Arbre Binaire
Un arbre binaire est composé
soit d'un arbre binaire VIDE∅ ;
soit d'un arbre binaire NON VIDE, un triplet (r,g,d) composé d'un noeud-racine r menant à deux sous-arbres
le sous-arbre binaire gauche g(qui peut donc être un arbre binaire VIDE ou NON VIDE)
le sous-arbre binaire droite d(qui peut donc être un arbre binaire VIDE ou NON VIDE)
B - Différences avec l'arbre enraciné
Il existe trois différences majeures entre les arbres enracinés et les arbres binaires :
L'arbre binaire peut être VIDE, alors qu'un arbre enraciné possède au moins un noeud-racine ;
Chaque noeud mène au maximum à deux enfants ;
Il doit exister une logique interne pour savoir si on place un enfant à gauche ou à droite de son parent : ce n'est pas un choix aléatoire. Dans le cas d'un arbre généalogique, on décide souvent de placer le père à gauche et la mère à droite.
C - Exemple
On peut représenter ou pas l'arbre VIDE. Ci-dessous, on utilise un symbole particulier : le petit carré jaune.
Voici deux arbres binaires différents :
Ces arbres binaires ne sont pas identiques car l'enfant-gauche de C est B sur le premier mais l'enfant-gauche de C est G sur le deuxième.
D - Remarque importante
Chaque noeud d'un arbre binaire non vide a au maximum deux enfants mais chaque arbre binaire a exactement deux sous-arbres binaires (puisque l'arbre binaire vide est un arbre binaire).
11° Expliquer si cet arbre est un arbre binaire. Si l'arbre est binaire, noter les arbres vides non représentés sur l'arbre.
...CORRECTION...
Ce n'est pas un arbre binaire car le noeud A possède 3 fils.
12-A° Expliquer si cet arbre est un arbre binaire. Si l'arbre est binaire, noter le symbole des arbres vides non représentés sur l'arbre.
...CORRECTION...
Chaque noeud non vide possède bien deux sous-arbres : un sous-arbre gauche et un sous-arbre-droite.
Certains sous-arbres sont des arbres-vides mais cela fait partie de la définition.
12-B° Entourer en rouge le sous-arbre gauche de l'arbre binaire. Entourer en bleu le sous-arbre droite. Entourer en vert le sous-arbre droite du sous-arbre gauche.
...CORRECTION...
Arbre ou Arbre Binaire ?
Dans la suite du cours, si le mot Arbre apparaît sans plus de précision, il fait maintenant implicitement référence à l'Arbre Binaire. Le programme de NSI traite du type ARBRE BINAIRE.
Pour ne pas alourdir le texte ou les programmes, le mot ARBRE est donc à lire comme si on avait noté ARBRE BINAIRE.
2.2 Les primitives (2e partie de la définition de l'arbre binaire)
nvABV() -> Arbre Binaire VIDE
Crée un nouvel ARBRE BINAIRE vide.
nouvelArbreBinaireVide() c'est trop long.
nvAB(v:Element, g:Arbre Binaire, d:Arbre Binaire) -> Arbre Binaire NON VIDE
Crée un nouvel ARBRE BINAIRE dont la racine porte l'étiquette v et mène aux sous-arbres g et d qui peuvent être vides.
estABV(arbre:Arbre Binaire) -> bool
Prédicat qui renvoie True si l'arbre est un arbre binaire vide.
racine(arbre:Arbre Binaire NON VIDE) -> Noeud
Renvoie le noeud jouant le rôle de la racine pour cet arbre binaire NON VIDE.
Comme avec la notion de Place / Case / Cellule des Listes, nous verrons que beaucoup d'implémentations n'ont pas besoin de vraiment gérer cette notion de Noeud en pratique.
contenu(noeud:Noeud) -> Element
Renvoie l'élément rattaché au noeud transmis.
gauche(arbre:Arbre Binaire NON VIDE) -> Arbre Binaire
Renvoie le sous-arbre gauche de arbre.
Si vous voulez le noeud gauche, il faudrait appliquer racine(gauche(arbre)). Attention, le sous-arbre gauche existe nécessairement, mais il peut être vide et, dans ce cas, le noeud gauche n'est pas forcément présent.
droite(arbre:Arbre Binaire NON VIDE) -> Arbre Binaire
Renvoie le sous-arbre droite de arbre.
Si vous voulez le noeud droite, il faudrait appliquer racine(gauche(arbre)). Attention, le sous-arbre droite existe nécessairement, mais il peut être vide et, dans ce cas, le noeud droite n'est pas forcément présent.
13° Créer l'arbre binaire ci-dessous à l'aide des primitives. On considère que le contenu d'un noeud est juste un string portant le nom du noeud : le noeud A porte l'information "A".
...CORRECTION...
On doit commencer par créer les arbres les plus bas et remonter progressivement jusqu'à créer l'arbre dont la racine est "A".
abr_F = nvAB('F', nvABV(), nvABV())
abr_E = nvAB('E', nvABV(), abr_F)
abr_B = nvAB('B', nvABV(), nvABV())
abr_G = nvAB('G', nvABV(), nvABV())
abr_C = nvAB('C', abr_G, abr_B)
abr_A = nvAB('A', abr_C, abr_E)
14° Utiliser les primitives pour stocker dans une variable nommée valeur l'étiquette du noeud correspondant à l'enfant-gauche de la racine de l'arbre.
On considère qu'on a accès initialement uniquement à la variable abr qui fait référence à l'arbre de racine A.
...CORRECTION...
En plusieurs étapesabr_g = gauche(abr) # on récupère l'arbre de racine C.
Pour récupérer la valeur, on fait :
nd = racine(abr_g) # on récupère le noeud C.
valeur = contenu(nd) # on récupère la valeur associée à noeud C.
En une lignevaleur = contenu(racine(gauche(abr)))
15° Utiliser les primitives pour stocker dans une variable reponse l'enfant-droite de l'enfant-gauche de la racine.
Attention : n'oubliez pas qu'on part de la racine, on doit donc lire la phrase de l'énoncé en sens inverse.
Stocker ensuite la valeur associée à ce noeud dans une variable valeur.
On considère qu'on a accès initialement uniquement à la variable abr qui fait référence à l'arbre de noeud A.
...CORRECTION...
En plusieurs étapesabr_g = gauche(abr) # on récupère l'arbre_C
reponse = droite(abr_g) # on récupère l'arbre_B.
Pour récupérer la valeur, on fait :
nd_b = racine(reponse) # on récupère le noeud B.
valeur = contenu(nd_b) # on récupère la valeur associée à noeud B.
En deux lignesreponse = droite(gauche(abr))
valeur = contenu(racine(reponse))
Définition : la taille d'un arbre correspond au nombre de noeuds présents dans l'arbre.
Attention, on compte les noeuds, on ne compte donc pas les arbres vides, même si on les affiche via un petit carré : ce ne sont des noeuds.
La taille de cet arbre est donc de 6.
3.2 Arête
Définition : une arête est le segment qui relie deux noeuds.
Encore une fois, le terme noeud est important : s'agissant de liaisons entre noeuds, on ne compte pas les "liaisons visibles" entre un noeud et un arbre vide. Ce n'est pas une arête.
Ici, on compte donc 5 arêtes.
3.3 Profondeur d'un noeud
Deux conventions possibles : on vous indiquera le cas à utiliser dans le sujet le jour du BAC.
Convention profondeur 0 pour la racine
Cette convention consiste à dire que le rez-de-chaussée est l'étage 0.
profondeurR = 0
Définition : la profondeur d'un noeud est le nombre d'arêtes à emprunter pour atteindre ce noeud en partant de la racine.
Convention profondeur 1 pour la racine
Cette convention consiste à dire que le rez-de-chaussée est l'étage 1 puisqu'il y a une hauteur de mur.
profondeurR = 1
Définition : la profondeur d'un noeud est alors 1 + le nombre d'arêtes à emprunter pour atteindre ce noeud en partant de la racine.
Quelques propriétés
Propriété : la profondeur d'un enfant est supérieure de 1 à celle de son parent.
Propriété : si deux noeuds ont la même profondeur, c'est qu'ils sont à la même distance de la racine, sur le même "étage" de l'arbre.
3.4 Hauteur d'un arbre
Définition de hauteur d'un arbre
Définition : la hauteur d'un ARBRE est liée à la profondeur maximale qu'on trouve dans l'arbre binaire. Est-il "profond" ou non ?
Puisque la hauteur dépend de la profondeur, il y a deux façons de gérer les hauteurs.
Hauteur en utilisant une profondeur de 0 pour la racine
On cherche le noeud le plus profond : ici, la hauteur de l'arbre est donc 2.
Avec cette convention :
la hauteur d'un arbre composé d'un noeud unique est 0.
la hauteur d'un arbre vide serait donc -1.
On fait souvent ce choix sur les arbres enracinés : ils ne peuvent pas être vides. La valeur bizarre de -1 ne pose donc pas problème.
Hauteur en utilisant une profondeur de 1 pour la racine
On cherche le noeud le plus profond : ici, la hauteur de l'arbre est donc 3.
Avec cette convention :
la hauteur d'un arbre composé d'un noeud unique est 1.
la hauteur d'un arbre vide serait donc 0.
On fait souvent ce choix sur les arbres binaires : ils peuvent être vides.
Pourquoi deux définitions ?
Pourquoi se compliquer la vie ? En réalité, certaines formules caractérisant les arbres seront faciles en prenant l'une des conventions et plus complexes avec l'autre. En fonction de exercices, on vous proposera donc le choix qui simplifie le plus la formule à trouver.
De plus, lors des analyses asymptotiques des coûts, une différence de 1 ne crée jamais de différence puisqu'on s'intéresse à l'allure du coût et pas à sa valeur réelle.
16° On considère la convention pR = 0. Fournir la taille, la hauteur et le nombre d'arêtes de cet arbre. Fournir également la profondeur du noeud C.
On dit que cet arbre est parfait car le dernier étage est entiérement rempli par des feuilles.
...CORRECTION...
17° On considère la convention pR = 0. Fournir la taille, la hauteur et le nombre d'arêtes de cet arbre. Fournir également la profondeur du noeud C.
On parle d'arbre filiforme.
...CORRECTION...
18° On considère la convention pR = 0. Fournir la taille, la hauteur et le nombre d'arêtes de cet arbre. Fournir également la profondeur du noeud C.
...CORRECTION...
3.5 Vocabulaire : quelques arbres particuliers
Arbre binaire parfait
Un arbre est parfait lorsqu'il ne manque aucun noeud.
Arbre binaire complet
On dit qu'un est complet lorsque les noeuds manquants sont uniquement sur son dernier étage.
Arbre binaire dégénéré
Lorsque chaque noeud possède au maximum un seul enfant, on dit qu'il est dégénéré.
Arbre binaire filiforme
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.
D'autres définitions existent !
Mais ce vocabulaire n'est pas si défini que cela. Certains utilisent des termes différents. On trouve parfois :
Un arbre binaire peut avoir une forme quelconque mais que cette forme est bornée par deux cas extrêmes :
L'arbre parfait (où tous les noeuds sont présents)
L'arbre filiforme (où chaque noeud n'a qu'un enfant au maximum)
Nous allons chercher les formules qui relient la taille n de l'arbre binaire avec sa hauteur h.
Encadrement de la hauteur avec la convention profondeur 1 pour la racine
19-A ° Quelle va être la hauteur d'un arbre filiforme de taille n si on prend une profondeur de 1 pour la racine ?
...CORRECTION...
Sur l'exemple, on a 7 noeuds (n=7).
A est à la profondeur 1, G est à la profondeur 7.
La hauteur de l'arbre est donc de h=7, ce qui correspond à h=n.
Généralisons :
Pour un arbre filiforme, on a
h=n(avec profondeur 1 pour la racine)
19-B° On considère la convention pR = 1.
Calculer les tailles manquantes pour les Arbres Binaires Parfaits dont on vous donne des valeurs de hauteur h.
On remarquera qu'à chaque nouvel étage, on rajoute le double de noeuds de l'étage précédent.
Hauteur h = 1 : La taille est n = 1
Hauteur h = 2 : La taille est n = 1 + 2 = 3
Hauteur h = 3 : La taille est n = 1 + 2 + 4 = 7
Hauteur h = 4 : La taille est n = ...
Hauteur h = 5 : La taille est n = ...
Trouver alors la formule permettant de connaître la taille n d'un Arbre Binaire Parfait dont on connaît la hauteur h.
...CORRECTION...
L'énoncé impose une profondeur de 1 pour la racine
Question 1
Hauteur h = 1 : Taille n = 1 et on remarque que 1 + 1 = 2 = 21
Hauteur h = 2 : Taille n = 1 + 2 = 3 et on remarque que 3 + 1 = 4 = 22
Hauteur h = 3 : Taille n = 1 + 2 + 4 = 7 et on remarque que 7 + 1 = 8 = 23
Hauteur h = 4 : Taille n = 1 + 2 + 4 + 8 = 15 et on remarque que 15 + 1 = 16 = 24
Hauteur h = 5 : Taille n = 1 + 2 + 4 + 8 + 16 = 31 et on remarque que 31 + 1 = 32 = 25
Question 2 (sans démonstration, juste de l'observation)
On remarque qu'on peut visiblement écrire ceci : n + 1 = 2h
Il suffit alors d'isoler la variable n et on obtient :
n = 2h - 1(avec profondeur 1 pour la racine)
Pour ceux qui suivent la spé math :
Question 2 (avec démonstration utilisant les séries géométriques)
On calcule n = 1 + 2 + 4 + ... + 2h-1
En écrivant cela en puissance de 2 : n = 20 + 21 + 22 + ... + 2h-1
Cela devrait vous permettre de vous souvenir de cette formule liée aux séries géométriques :
Si on compore les deux formules :
1 + x1 + x2 + ... + xn
1 + 21 + 22 + ... + 2h-1
En identifiant les termes des deux formules, on trouve :
n correspond à (h-1) donc xn+1 = xh-1+1 = xh
x correspond à 2 donc (x-1)=(2-1)=1
Au final, on obtient n = (2h-1)/1 = 2h-1
Vous aviez peut-être vu la formule avec l'utilisation du symbole somme :
19-C° En partant de la formule précédente, trouver la formule donnant la hauteur h d'un arbre binaire parfait en fonction de sa taille n.
n = 2h - 1(formule valable si profondeur 1 pour la racine)
Un peu d'aide ? Quelle est la fonction réciproque de la fonction exponentielle 2 ?
...CORRECTION...
On sait que log2 est la fonction réciproque de 2x.
log2 (2x) = x
Nous allons utiliser cela pour parvenir à obtenir h connaissant 2h.
n = 2h - 1
On déplace le -1 pour que 2h soit isolée.
n + 1 = 2h
On utilise le log2 de chaque côté :
log2(n+1) = log2(2h)
On obtient une simplification du terme de droite :
log2(n+1) = h
En intervertissant simplement les deux termes :
h = log2(n+1)(formule valable si profondeur 1 pour la racine)
19-D° Déduire des questions 19-A et 19-C l'encadrement de la hauteur d'un arbre binaire quelconque :
... ≤ h ≤ ...(formule valable si profondeur 1 pour la racine)
On ne tiendra pas compte pour le moment du fait que les logarithmes donnent parfois des valeurs non entières.
...CORRECTION...
Il suffit de reprendre les formules obtenues pour les deux cas extrêmes et de borner la hauteur du cas quelconque par ces deux valeurs : la hauteur du cas filiforme est la plus grande et la hauteur du cas parfait la plus petite.
log2(n+1) ≤ h ≤ n(formule valable si profondeur 1 pour la racine)
Attention, on ne tient pas compte des valeurs non entières dans cette version.
Remarque : on utilise souvent les notations suivantes :
Logarithme népérien : ln pour parler de loge
Logarithme base 2 : lg pour parler de log2
Avec cette notation, la formule peut s'écrire :
lg(n+1) ≤ h ≤ n
Encadrement de la hauteur avec la convention profondeur 0 pour la racine
20-A ° Quelle va être la hauteur d'un arbre filiforme de taille n si on prend une profondeur de 0 pour la racine ?
...CORRECTION...
Sur l'exemple, on a 7 noeuds (n=7).
A est à la profondeur 0, G est à la profondeur 6.
La hauteur de l'arbre est donc de h=6, ce qui correspond à h=n-1.
Généralisons :
Pour un arbre filiforme, on a
h=n-1(avec profondeur 0 pour la racine)
20-B° On rappelle que, avec la convention d'une profondeur 1 pour la racine, nous avions :
n = 2h - 1(formule valable si profondeur 1 pour la racine)
Déterminer la formule avec la convention 0 pour la racine en vous basant sur la formule proposée.
...CORRECTION...
C'est comme avant, la hauteur est juste plus petite de 1.
Si la hauteur est de h=4 avec la convention 0, on aurait 5 étages de noeuds.
Or, arbre de 5 étages en convention 1 auraut une hauteur de 5.
Il suffit donc de rajouter 1 à h pour passer de la convention 0 à la convention 1.
Il suffit donc de reprendre la formule donnée en convention 1 et de remplacer les h par h+1.
n = 2h - 1(formule valable si profondeur 1 pour la racine)
D'où :
n = 2h+1 - 1(formule valable si profondeur 0 pour la racine)
20-C° En partant de la formule précédente, trouver la formule donnant la hauteur h d'un arbre binaire parfait en fonction de sa taille n.
n = 2h+1 - 1(formule valable si profondeur 0 pour la racine)
Un peu d'aide ? Quelle est la fonction réciproque de la fonction exponentielle 2 ?
...CORRECTION...
On sait que log2 est la fonction réciproque de 2x.
log2 (2x) = x
Nous allons utiliser cela pour parvenir à obtenir h connaissant 2h.
n = 2h+1 - 1(formule valable si profondeur 0 pour la racine)
n = 2h+1-1
On déplace le -1 pour que 2h soit isolée.
n + 1 = 2h+1
On utilise le log2 de chaque côté :
log2(n+1) = log2(2h+1)
On obtient une simplification du terme de droite :
log2(n+1) = h+1
log2(n+1) - 1 = h
En intervertissant simplement les deux termes :
h = log2(n+1) - 1(formule valable si profondeur 0 pour la racine)
Avec la notation lg :
h = lg(n+1) - 1(formule valable si profondeur 0 pour la racine)
.
20-D° Déduire des questions 20-A et 20-C l'encadrement de la hauteur d'un arbre binaire quelconque avec la convention profondeur 0 pour la racine. :
... ≤ h ≤ ...(formule valable si profondeur 0 pour la racine)
On ne tiendra pas compte pour le moment du fait que les logarithmes donnent parfois des valeurs non entières.
...CORRECTION...
Il suffit de reprendre les formules obtenues pour les deux cas extrêmes et de borner la hauteur du cas quelconque par ces deux valeurs : la hauteur du cas filiforme est la plus grande et la hauteur du cas parfait la plus petite.
log2(n+1) - 1 ≤ h ≤ n - 1(formule valable si profondeur 0 pour la racine)
lg(n+1) - 1 ≤ h ≤ n - 1(formule valable si profondeur 0 pour la racine)
Remarque : on ne tient pas compte des valeurs non entières dans cette version.
Pour rappel avec l'autre convention :
log2(n+1) ≤ h ≤ n(formule valable si profondeur 1 pour la racine)
On a donc juste une différence de 1 : logique !
4.1 Arbre binaire parfait : caractéristiques
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
4.2 Arbre Binaire Filiforme : caractéristiques
L'Arbre Binaire Filiforme est la pire configuration en terme de réduction de la hauteur.
h = n(avec la convention PR=1)
4.3 Formules à connaître par coeur sur l'Arbre Binaire
Le plus simple est d'apprendre par coeur ces trois formules, valables avec la convention profondeur 1 :
Arbre binaire filiforme :
h = n(avec convention profondeur 1)
Arbre binaire complet :
h = log2(n+1)(avec convention profondeur 1)
n = 2h - 1(avec convention profondeur 1)
4.4 Encadrements de la hauteur d'un Arbre Binaire
Les deux cas extrêmes
Les deux cas extrêmes sont :
Arbre binaire filiforme : chaque noeud n'a qu'un seul enfant au maximum.
A savoir : pour un arbre filiforme, l'ordre de grandeur de h est en n.
Arbre binaire parfait : tous les noeuds possèdent deux enfant, hormis les noeuds de l'étage le plus bas qui sont tous des feuilles.
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.
Encadrement avec une profondeur 1 pour la racine (à savoir utiliser)
Arbre binaire complet : h = log2(n+1)
Arbre binaire filiforme : h = n
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...
Encadrement avec une profondeur 0 pour la racine (à savoir utiliser)
Arbre binaire complet : h = log2(n+1) - 1
Arbre binaire filiforme : h = n - 1
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.9068905956085187Pour n=15, on arrondit donc à 3 et on a h=3 au minimum>>> math.log2(16)
4.0Pour n=16, on arrondit donc à 4 et on a h=4 au minimum
Ordre de grandeur de la hauteur d'un arbre (à connaître par coeur)
L'ordre de grandeur de la hauteur d'un Arbre Binaire est compris entre log2(n) et n.
La hauteur va nous intéresser en algorithmique pour estimer le coût de certains algorithmes. Or, on cherche dans ce cas le coût asymptotique lorsque le nombre de données devient très grand.
Avec cette optique en tête, il n'est pas utile de connaître par coeur les formules pour les deux conventions car la convention n'aura aucune influence sur le coût puisque :
𝞗(log2(n+1))= = 𝞗(log2(n))
Tout ce qui est important c'est qu'on obtient un coût logarithmique en n.
Parfait ou pas ? : considérons un arbre binaire de 15 noeuds. Peut-il être parfait ?
On peut raisonner par l'absurde : on considère qu'il est parfait, on calcule log2(n+1).
S'il parfait, on va tomber sur une hauteur correspondant bien à un entier.
Sinon on aura un flottant, ce qui est absurde : une hauteur doit être entière. Cela indiquera que l'arbre ne peut pas être parfait.
Exemple en Python avec 15 noeuds :
>>> import math
>>> math.log2(15+1)
4.0
On tombe sur une hauteur entière : un arbre de 15 noeuds peut être parfait et a alors une hauteur de 4.
Exemple avec 16 noeuds : la formule donne un résultat non entier :
>>> math.log2(16+1)
4.087462841250339
Un arbre de 16 noeuds ne pourra jamais être parfait.
