21 - Arbre
Après les types abstraits linéaires, il est temps de commencer à parler arborescence et des arbres en informatique.
Documents de cours : open document ou pdf
1 - L'Arbre en tant que type abstrait de données
Vous connaissez déjà ce type de structure. Elle est assez courante dans la vie de tous les jours. Ne serait-ce que par l'arbre généalogique.
D'un point de vue informatique, l'arbre est présent un peu partout. Nous l'avons déjà rencontré l'année dernière lorsque nous avons parlé des balises HTML et de la structure que cela engendre : l'arbre DOM (pour Document Object Model).
Nous avions vu ce exemple de code HTML :
- La balise racine est la balise html. Elle contient :
- Une balise head (les informations qu'on veut donner au vavigateur)
- Une balise body (les choses à afficher) qui contient
- Une balise header (l'en-tête de la page) qui contient d'autres balises...
- Une balise nav (le menu de navigation) qui contient d'autres balises...
- Une balise main (le contenu principal de la page) qui contient d'autres balises...
- Une balise footer (le bas de page) qui contient d'autres balises...
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 | <!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>
|
01° Imaginons que la structure HTML soit stockée dans une simple liste. Pourrait-on trier les balises HTML entre elles pour les localiser plus facilement par dichotomie ? Du coup, quel serait le coup d'une recherche pour par exemple trouver la balise <div> de la ligne 24 à la ligne 28 ?
...CORRECTION...
Difficile d'imaginer un classement performant des balises entre elles. On pourra imaginer quelque chose comme associer chaque balise à un nombre en fonction de la balise qui la contient mais ça risque d'être vite assez complexe.
Du coup, pas de classement. Du coup, pas de dichotomie.
On revient à la recherche ligne par ligne, à coût linéaire donc.
Pourquoi dit-on que cette structure caractérise un arbre ?
Visuellement, c'est clair : cela forme un arbre.
Par contre, attention : nos arbres ne sont jamais tracés dans ce sens. Contrairement aux vrais arbres, on a tendance à les dessiner avec la racine en haut et les feuilles en bas.
Si on parle en terme de recherche, vous imaginez bien que c'est très pratique de réflechir en terme d'arbre.
02° On cherche toujours la balise <div> contenue dans la balise main, elle-même contenue dans la balise body contenue dans html contenue dans ... Ah. Rien. html joue un rôle particulier puisqu'elle n'est pas contenue dans une autre balise. Elle est la racine de notre arbre. Combien de choix doit-on faire pour trouver notre balise div en partant initialement de la racine ?
...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.
Qu'est-ce que n'est pas un arbre ?
Regardons déjà ce que n'est PAS un arbre :
Exemple 1 : ceci n'est pas un arbre car on y trouve un cycle.
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.
Exemple 3 : ceci est un arbre mais on considérera cette année qu'il manque encore une information. Laquelle ?
- Les noeuds sont bien tous reliés entre eux : il y a un chemin possible entre tous les noeuds, l'arbre est connexe
- il n'y a pas de cycle.
- mais il manque un noeud de départ : une racine.
Il s'agit pourtant bien d'un arbre mais on se limitera cette année aux arbres 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.
1er partie de la définition du type abstrait de données ARBRE
Principe général d'organisation
Un arbre est un type abstrait de données ayant les propriétés suivantes (on parle ici des arborescences) :
- Il est composé de "cellules" qu'on nomme des noeuds contenant des informations dont
- Des données du type recherché (un nombre, un string...)
- Les liaisons éventuelles avec d'autres noeuds
- On hierarchise les noeuds entre eux : un noeud peut possèder
- un noeud-père (unique, un noeud ne peut pas posséder deux pères)
- un ou des noeuds-fils (un noeud peut avoir 0, 1 ou plusieurs fils)
- Racine : ce noeud UNIQUE est particulier car il est le seul noeud à ne pas possède de père. Il est tout en haut de la hierarchie.
- Feuille : il s'agit d'un noeud qui ne possède pas de fils.
- Noeud interne : il s'agit d'un noeud possède au moins un autre fils non nul.
Un exemple où les noeuds et les feuilles n'ont pas le même rôle et donc pas le même type de données rattachées :
- La racine est ici la propriété "A des yeux" (on notera qu'on aura pu prendre la propriété "A une tête")
- Les noeuds internes sont des propriétés du type "A des plumes"...
- Les feuilles sont des animaux et pas des propriétés.
Un exemple tiré des noms de domaines (et du système DNS) :
La RACINE se nomme point.
Cette racine possède 6 fils : com, net, org, mil, fr, xxx.
Le noeud fr possède un fils : inforall.
Le noeud infoforall possède trois fils : www, doc et formation.
Les feuilles sur cet arbre d'exemple sont com, net, org, mil, xxx, www, doc et formation.
Cet exemple vise à vous sensibiliser sur les choix des étiquettes : deux noeuds peuvent ici très bien porter la même étiquette sans qu'on les confonde en cas de recherche, tant que le nom n'a pas le même père.
Exemple : www.sitea.com et www.siteb.com : il y a deux noms portant un label www mais ils n'ont pas le même père. Pas de confusion possible.
01° Représenter l'arborescence de l'ordinateur dont on vous fournit ci-dessous la structure (qu'on supposera complète...)
📁 / (la racine de l'ordinateur)
📁 bin
📄 fichierA
📁 home
📁 testprofad
📁 admin
📄 fichierB
📁 www
📁 repC
...CORRECTION...
02° Représenter l'arbre de l'étage où vous vous trouvez dans le lycée ou votre domicile si vous préférez. On considère que la racine est l'entrée du couloir ou l'entrée du domicile. S'il existe des cycles dans le vrai lieu, vous supprimerez certaines liaisons réelles pour obtenir un graphe.
03° Représenter maintenant la même situation mais on changeant de racine : vous prendrez la salle actuelle ou votre chambre. Obtient-on la même chose ?
04° Dans le cas d'une recherche orientée à l'aide d'un arbre, le choix de la racine est-il important ?
...CORRECTION...
05° Que donnerait la représentation directe d'une liste dont la tête est 5 et la queue 10-15-20-25-30-35 sous forme d'un arbre ?
...CORRECTION...
Définition d'un arbre enraciné à partir des noeuds
On peut considérer qu'un arbre enraciné est composé d'un noeud particulier nommé racine ne menant à rien ou menant à un ou plusieurs autres noeuds du même type.
Comme la racine peut mener à d'autres noeuds de ce type, on voit que l'arbre est une structure récursive puisqu'un arbre contient potentiellement d'autres arbres.
06° Avec cette définition, peut-on considérer qu'un arbre enraciné peut-être vide ?
...CORRECTION...
Non, un arbre enraciné ne peut pas être vide : il contient toujours au moins son noeud-racine.
07° Combien d'arbres enracinés contient cet arbre ?
...CORRECTION...
Il y a 7 arbres en tout :
- L'arbre enraciné aa dont la racine est le noeud est A.
- L'arbre enraciné ac dont la racine est le noeud est C.
- L'arbre enraciné ab dont la racine est le noeud est B.
- L'arbre enraciné ag dont la racine est le noeud est G.
- L'arbre enraciné ad dont la racine est le noeud est D.
- L'arbre enraciné ae dont la racine est le noeud est E.
- L'arbre enraciné af dont la racine est le noeud est F.
08° Quelle est la racine cet arbre ? Quelles sont les feuilles de cet arbre ? Quels sont le ou les fils du noeud E ?
...CORRECTION...
09° Représentez l'arbre obtenu si on considère que la racine est maintenant le noeud D. Que pouvez-vous en dire au niveau d'une éventuelle localisation ?
...CORRECTION...
L'arbre est plus profond, il y aura plus de décisions à prendre. La racine précédente permettait une meilleur optimisation de la localisation.
Retenez bien que les arbres (ou arborescences) sont utilisés de façon massive en informatique et dans la vie de façon générale :
- système de fichiers des systèmes d'exploitation
- bases de données,
- documents structurés (HTML, XML),
- toutes les problèmes décisionnels non cycliques
Nous n'irons pas plus loin cette année avec l'arbre général. Je ne donnerai pas les fonctions d'interface nécessaires à sa définition réelle. Nous allons surtout nous concentrer sur un arbre particulier : l'arbre binaire.
2 - Arbre binaire
1er partie de la définition de l'arbre binaire
Un arbre binaire est composé
- soit d'un arbre binaire vide
- soit de l'ensemble
- d'un noeud
- d'un sous-arbre binaire gauche qui possède une raison interne d'être placé à gauche (attention : comme il s'agit d'un arbre binaire, il a le droit d'être potentiellement vide)
- d'un sous-arbre binaire droite qui possède une raison interne d'être placé à droite (attention : comme il s'agit d'un arbre binaire, il a le droit d'être potentiellement vide)
Il existe donc deux différences majeures entre les arbres enracinés et les arbres binaires :
- L'arbre binaire peut être vide, contrairement à l'arbre enraciné
- La distinction entre fils gauche et fils droit est fondamentale : un arbre binaire n'est pas juste un arbre où chaque noeud peut avoir deux fils. Le positionnement à gauche ou à droite doit suivre une logique interne , ce n'est pas un choix aléatoire.
On symbolise parfois l'arbre vide par un symbole particulier sur les arbres binaires.
Exemple
Ici, nous avons deux arbres binaires différents, alors qu'en terme d'arborescence (l'arbre de la partie 1), c'est le même objet :
Ces arbres binaires ne sont pas identiques car le fils gauche de C est B sur le premier mais le fils gauche de C est G sur le second.
VOCABULAIRE :
- Un noeud d'arbre binaire possède
- un fils-gauche et
- un fils-droite mais
- Un arbre binaire possède
- un sous-arbre gauche et
- un sous-arbre droite
- Le fils-gauche est la racine du sous-arbre gauche
- Le fils-droite est la racine du sous-arbre droite
10° 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.
11° 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° Entourer en rouge le sous-arbre gauche de l'arbre précédent. Entourer en bleu le sous-arbre droit. Entourer en vert le sous-arbre droit du sous-arbre gauche.
Abre ou Arbre Binaire ?
Dans la suite du cours, le mot Arbre fait maintenant implicitement référence à la notion d'Arbre Binaire. Les arbres enracinés ont été présentés en introduction pour que vous sachiez qu'il a plusieurs types de structures de données derrière le mot "arbre". Mais les exercices de NSI traitenr quasi-exclusivement 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.
2e partie de la définition du type abstrait de données ARBRE BINAIRE : ses primitives
Description de l'interface minimale du type abstrait Arbre
Je le décris ici sous forme d'un type immuable, mais on pourait faire la même chose en muable.
- nvABV() -> Arbre Binaire VIDE
- nvAB(v:Element, g:Arbre Binaire, d:Arbre Binaire) -> Arbre Binaire NON VIDE
- estABV(arbre:Arbre Binaire) -> bool
- racine(arbre:Arbre Binaire NON VIDE) -> Noeud
- contenu(noeud:Noeud) -> Element
- gauche(arbre:Arbre Binaire NON VIDE) -> Arbre
- droite(arbre:Arbre Binaire NON VIDE) -> Arbre
Crée un nouvel ARBRE BINAIRE vide.
On le note ainsi pour dire nouvelArbreBinaireVide() mais c'est plus long.
Crée un nouvel ARBRE BINAIRE dont la racine porte la valeur v et mène aux sous-arbres sont g et d transmis.
Prédicat qui renvoie True si l'arbre est un arbre binaire vide.
Renvoie le noeud jouant le rôle de la racine pour cet arbre binaire NON VIDE.
Renvoie l'élément rattaché au noeud transmis.
Renvoie le sous-arbre gauche de arbre. On obtient bien un Arbre. Si vous voulez le noeud gauche, il faudra appliquer en plus la fonction racine().
Renvoie le sous-arbre droite de arbre.
13° Créer l'arbre de la question 12 (dont vous avez une copie ci-dessous) à l'aide des primitves founies. On considère que le contenu d'un noeud est juste un string portant le nom du noeud. Ainsi le noeud A porte l'information "A".
...CORRECTION...
arbre_F = nvAB('F', nvABV(), nvABV())
arbre_E = nvAB('E', nvABV(), arbre_F)
arbre_B = nvAB('B', nvABV(), nvABV())
arbre_G = nvAB('G', nvABV(), nvABV())
arbre_C = nvAB('C', arbre_G, arbre_B)
arbre_A = nvAB('A', arbre_C, arbre_E)
14° Utiliser les fonctions d'interface pour aller stocker dans une variable nommée valeur la valeur du noeud correspondant au fils-gauche de la racine de l'arbre.
On considère qu'on a accès initialement uniquement à la variable arbre qui fait référence à l'arbre de racine A.
...CORRECTION...
sous_arbre_g = gauche(arbre) # on récupère l'arbre_C en gros.
Pour récupérer la valeur, on fait :
c = racine(sous_arbre_g) # on récupère le noeud C.
valeur = contenu(c) # on récupère la valeur associée à noeud C.
Ou en une étape :
valeur = contenu(racine(gauche(arbre)))
15° Utiliser les fonctions d'interface pour aller stocker dans une variable reponse le fils droit du fils gauche de la racine.
Stocker alors sa valeur associée dans une variable valeur.
On considère qu'on a accès initialement uniquement à la variable arbre qui fait référence à l'arbre de noeud A.
...CORRECTION...
sous_arbre_gauche = gauche(arbre) # on récupère l'arbre_C en gros.
reponse = droite(sous_arbre_gauche) # on récupère l'arbre_B en gros.
Ou en une étape :
reponse = droite(gauche(arbre))
Pour récupérer la valeur, on fait :
b = racine(reponse) # on récupère le noeud B.
valeur = contenu(b) # on récupère la valeur associée à noeud B.
Ou en une étape :
valeur = contenu(racine(reponse))
3 - Caractéristiques des arbres binaires
Taille d'un arbre
La taille d'un arbre correspond au nombre de noeuds présents dans l'arbre.
On ne compte pas les arbres-vides : l'arbre-vide ne possède pas de noeud.
La taille de cet arbre est donc de 6.
Arête
Une arête est le segment qui relie deux noeuds.
Encore une fois, le terme est important : s'agissant de noeuds, on ne compte pas les "liaisons" entre un noeud et un fils-vide.
Ici, on compte donc 5 arêtes.
Profondeur d'un noeud
Il existe ici deux écoles :
- Convention 1 (la plus courante) : la profondeur représente le nombre d'arêtes à emprunter pour atteindre le noeud voulu en partant de la racine. En conséquence, la profondeur de la racine est de 0 car on n'emprunte aucune arête, on y est déjà. La racine est le rez-de-chaussée, le niveau 0.
- Convention 2 : la profondeur représente le nombre de noeuds rencontrés pour atteindre le noeud voulu en partant de la racine. Avec cette convention, la profondeur de la racine est de 1 puisqu'on rencontre la racine pour atteindre la racine. La racine est alors le premier étage de l'arbre.
On vous indiquera le cas à respecter le jour du BAC.
Propriété : quelque soit la convention choisie, la profondeur d'un noeud-fils est supérieure de 1 à celle de son père.
Propriété : si deux noeuds ont la même profondeur, c'est qu'ils sont à la même distance de la racine.
Hauteur d'un arbre
Il s'agit de la profondeur maximale qu'on trouve dans l'arbre, la "distance" entre la racine et la plus profonde des feuilles.
Moralité : ça dépend de la convention choisie pour trouver la profondeur.
- Convention 1 (nombre d'arêtes) : la profondeur de la racine est de 0.
- Convention 2 (nombre de noeuds) : la racine a une profondeur de 1.
Sur cet exemple, la hauteur de l'arbre est donc de 2.
Avec cette convention, la "hauteur" d'un arbre binaire vide peut être prise à -1. Ca semble bizarre une hauteur négative mais ce n'est pas très grave : en réalité, un arbre binaire vide n'a pas de hauteur puisqu'il n'a pas de noeud. Ca se tient donc.
Sur cet exemple, la hauteur de l'arbre est donc de 3.
Un arbre binaire vide aurait une hauteur de 0. C'est propre aussi.
On dit que l'arbre de notre exemple est presque complet car les seuls noeuds manquants sont sur son dernier étage.
16° On considérera la convention basée sur le nombre d'arête. La racine est donc de profondeur 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 (certains disent complet) car la plus grande profondeur est intégralement composée de feuilles (des noeuds n'ayant pas de fils).
...CORRECTION...
17° On considérera la convention basée sur le nombre d'arête. La racine est donc de profondeur 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 ou d'arbre dégénéré.
...CORRECTION...
18° On considérera la convention 2 (racine de profondeur 0). Fournir la taille, la hauteur et le nombre d'arêtes de cet arbre. Fournir également la profondeur du noeud C.
...CORRECTION...
19° Quelle va être la hauteur d'un arbre filiforme de taille n ?
...CORRECTION...
Si on considère une profondeur de 1 pour la racine, on obtient une hauteur de n.
Si on considère une profondeur de 0 pour la racine, on obtient une hauteur de n-1.
20-A° On considère une profondeur de 1 pour la racine.
- Finir les calculs permettant d'obtenir la taille d'un Arbre Binaire Complet dont on vous donne la hauteur h.
- 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 connaitre la taille n d'un Arbre Binaire complet dont on connait la hauteur h.
On remarquera qu'à chaque nouvel étage, on rajoute le double de noeuds de l'étage précédent.
...CORRECTION...
Profondeur de 1 pour la racine
- Hauteur h = 1 : Taille n = 1
- 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
On remarque que sur chaque étage, on doit rajouter 1 pour obtenir une puissance de deux.
n + 1 est à chaque fois égale à la puissance de 2 de la hauteur h.
On peut donc écrire que n + 1 = 2h
Par exemple, pour la hauteur 5, nous avons 31 noeuds et nous avons bien le résultat suivant :
31 + 1 = 32 = 25
Ceci n'est pas une démonstration, on montre juste que cela fonctionne.
n + 1 = 2h
Ou encore
n = 2h - 1
20-B° Trouvons la formule dans l'autre sens : quelle est la formule qui permet de trouver la hauteur h d'un arbre binaire complet dont on vous donne la taille n ?
Un peu d'aide ? Quelle est la fonction réciproque de la fonction exponentielle 2 ?
...CORRECTION...
n + 1 = 2h
On sait que log2 est la fonction réciproque de 2x.
log2 (2x) = x
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 les deux termes :
h = log2(n+1)
20-C° On considère maintenant une profondeur de 0 pour la racine. Finir les calculs permettant d'obtenir la taille d'un Arbre Binaire Complet dont on vous donne la hauteur h.
On remarquera qu'à chaque nouvel étage, on rajoute le double de noeuds de l'étage précédent.
- Hauteur h = 0 : La taille est n = 1
- Hauteur h = 1 : La taille est n = 1 + 2 = 3
- Hauteur h = 2 : La taille est n = 1 + 2 + 4 = 7
- Hauteur h = 3 : La taille est n = ...
- Hauteur h = 4 : La taille est n = ...
Quelle est la formule permettant de trouver n avec cette convention ? Pour rappel avec la convention d'un profondeur 1 pour la racine, nous avions :
n = 2h - 1
...CORRECTION...
Profondeur de 0 pour la racine
- Hauteur h = 0 : Taille n = 1
- 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
C'est comme avant, la hauteur est juste plus petite de 1.
On peut donc juste reprendre la formule mais rajouter 1 à notre hauteur pour obtenir la hauteur de la convention précédente.
n = 2h+1 - 1
20-D° Quelle relation permettrait alors de trouver la hauteur h connaissant la taille n de l'arbre binaire complet ?
...CORRECTION...
Première démonstration
On part de
n = 2h+1 - 1
On alors obtenir ceci en modifiant la position de 1
n + 1 = 2h+1
On passe au log2 de chaque côté.
log2(n+1) = log2(2h+1)
Or log2 est réciproque de 2x :
log2(n+1) = h + 1
log2(n+1) - 1 = h
En intervertissant les deux termes :
h = log2(n+1) - 1
Deuxième demonstration : on utilise la formule de l'autre convention, celle où la profondeur de la racine est 1.
h = log2(n+1)
Bon, la seule différence c'est qu'on considère que la hauteur est plus petite de 1 :
h = log2(n+1) - 1
On retiendra donc qu'on peut trouver la hauteur h d'un Arbre Binaire de taille n à l'aide de la fonction logarithme 2.
Encadrements de la hauteur d'un Arbre Binaire
Les deux cas extrêmes étant :
- Arbre binaire filiforme : chaque noeud n'a qu'un seul fils non vide au maximum
- Arbre binaire complet : tous les noeuds possèdent deux fils non vides hormis les noeuds de l'étage le plus bas qui n'ont pas de fils.
On en déduit que pour un arbre binaire quelconque, situé entre ces deux cas particuliers extrêmes, on peut encadrer la hauteur de l'arbre binaire quelconque à l'aide de la formule suivante :
Encadrement avec une 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.
Encadrement avec une 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.
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.
Exemple : un arbre binaire complet de 15 noeuds dont la racine a une profondeur de 1 a une hauteur de 4 s'il est complet et 15 s'il est filiforme.
Si on tape ceci dans Python,
>>> import math
>>> math.log2(15+1)
4.0
On voit bien qu'un arbre complet de 15 noeuds à une hauteur de 4.
Par contre, avec 16 noeuds, on obtient une hauteur comprise entre 5 pour l'arbre complet de 16 noeuds et 16 pour l'arbre filiforme de 16 noeuds.
>>> math.log2(16+1)
4.087462841250339
On arrondit 4.08 vers le haut et on obtient 5. C'est normal : avec 15 noeuds, l'arbre pouvait être déjà complet. Si on en rajoute un, il faut nécessairement rajouter un étage...
4 - FAQ
Pourquoi on arrondit à l'inférieur dans le cas de l'encadrement avec une profondeur de 0 pour la racine ?
La formule reliant h et n d'un Arbre Binaire Complet pour cette profondeur est :
h = log2(n+1) - 1 ( formule 1-R0 )
On pourrait donc écrire ceci :
⌈log2(n+1)⌉ - 1 ≤ h ≤ n - 1
On peut obtenir le même résultat en arrondissant simplement à l'inférieur du coup :
⌊log2(n)⌋ ≤ h ≤ n - 1
C'est quoi l'arité ?
C'est le nombre de fils maximum qu'un noeud peut avoir.
Si un arbre est d'arité 2, cela veut donc dire qu'aucun noeud de cet arbre n'a trois fils.
Un arbre classique d'arité 2 implique que les noeuds peuvent avoir 0, 1 ou 2 noeuds-fils.
Un arbre binaire est d'arité 2 puisque chaque noeud mène à deux sous-arbre gauche et droite, même s'ils sont des arbres vides !
C'est quoi le degré d'un noeud ?
Il s'agit tout simplement du nombre de liaison que possède le noeud.
Voir le cours sur les graphes, les arbres pouvant être vus comme un cas particulier des graphes.
J'ai vu un cours avec une hauteur pour un noeud, c'est normal ?
Et oui, il n'y a pas que la racine qui possède une hauteur.
La profondeur d'un noeud est un nombre représentant la "distance" entre la racine et ce noeud.
La hauteur d'un noeud est la "distance" entre le noeud et la racine la plus éloignée dans son sous-arbre.
Et on ne peut pas encadrer la taille n connaissant h ?
Si, mais c'est dans une autre activité.
On obtient ceci :
Encadrement de la taille n dans le cas profondeur de racine 1 :
h ≤ n ≤ 2h - 1
Encadrement de la taille n dans le cas profondeur de racine 0 :
h + 1 ≤ n ≤ 2h+1 - 1
5 -
Activité publiée le 23 11 2020
Dernière modification : 02 12 2020
Auteur : ows. h.