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 le HTML, dans lequel des balises contiennent d'autres balises.
<!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>
Pourquoi dit-on que cette structure caractérise un arbre ?
Visuellement, c'est clair : cela forme un arbre.
Par contre, attention : les arbres informatiques ne sont pas tracés dans ce sens : on les dessiner avec la racine en haut et les feuilles en bas.
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'elle n'est pas contenue dans une autre balise. Elle est la racine de notre arbre. Combien de choix de direction doit-on faire pour trouver la 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.
1.1 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.
1.2 L'idée générale (1er partie de la définition du type abstrait ARBRE)
Principe général d'organisation
Un arbre est un type abstrait 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.
Exemple
Voici un exemple où
les noeuds sont des caractéristiques
les feuilles sont des espèces
Exemple 2
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.
02° 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...
03° 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.
...CORRECTION...
04° 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 ?
...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.
06° 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...
Cela donnerait un arbre en forme de liste.
Le 5 est la racine qui mène à 10, le 10 mène à 15...
1.3 Définition d'un arbre enraciné à partir des noeuds
On peut considérer qu'un arbre enraciné est composé nécessairement au moins 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.
07° 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.
08° 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.
09° Quelle est la racine cet arbre ? Quelles sont les feuilles de cet arbre ? Quels sont le ou les fils du noeud E ?
...CORRECTION...
10° 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.
2.1 L'idée générale (1er partie de la définition de l'arbre binaire)
A - Description
Un arbre binaire est composé
soit d'un arbre binaire VIDE
soit d'un arbre binaire NON VIDE composé d'un noeud menant à deux sous-arbres
le sous-arbre binaire gauche peut être un arbre binaire VIDE ou un arbre binaire NON VIDE
le sous-arbre binaire droite peut être un arbre binaire VIDE ou un arbre binaire NON VIDE
Il existe deux 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.
un arbre binaire n'est pas juste un arbre où chaque noeud peut avoir deux fils au maximum. Le positionnement à gauche ou à droite doit suivre une logique interne de positionnement, ce n'est pas un choix aléatoire. Dans le cas d'un arbre généalogique, on pourrait ainsi placer le père à gauche et la mère à droite dans tout l'arbre binaire. Ou faire le choix inverse, mais dans tout l'arbre.
On symbolise parfois l'arbre vide par un symbole particulier sur les arbres binaires. Ci-dessous, c'est un petit carré jaune.
B - Exemple
Ci-dessous, vous trouverez deux arbres binaires différents :
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 deuxième.
S'il s'agissait de deux arbres enracinés, il s'agirait par contre du même arbre. Il serait simplement représenté de deux façons différentes.
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...
Abre 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 à 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 traitent 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.
2.2 Les primitives (2e partie de la définition de l'arbre binaire)
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
Crée un nouvel ARBRE BINAIRE vide.
On le note ainsi pour dire nouvelArbreBinaireVide() mais c'est plus long.
nvAB(v:Element, g:Arbre Binaire, d:Arbre Binaire) -> Arbre Binaire NON VIDE
Crée un nouvel ARBRE BINAIRE dont la racine porte la valeur v et mène aux sous-arbres transmis à la fonction, g et d.
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.
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. On obtient bien un Arbre. Si vous voulez le noeud gauche, il faudra appliquer en plus la fonction racine().
droite(arbre:Arbre Binaire NON VIDE) -> Arbre Binaire
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 primitives 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...
On doit commencer car créer les arbres les plus bas et remonter ensuite jusqu'à créer l'arbre dont la racine est "A".
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))
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 peut les afficher via un petit carré : ils n'ont pas de noeud.
La taille de cet arbre est donc de 6.
3.2 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.
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
pR = 0
La profondeur représente le nombre d'arêtes à emprunter pour atteindre le noeud voulu en partant de la racine.
Avec cette convention, la profondeur de la racine est de 0 : on n'emprunte aucune arête.
Cette convention consiste à dire que le rez-de-chaussée est l'étage 0.
Convention profondeur 1 pour la racine
pR = 1
La profondeur est le nombre d'arêtes rencontrées plus une en partant de la racine auquel on rajoute 1.
Avec cette convention, la profondeur de la racine est de 1 : 0 arête mais il y a le plus 1.
Cette convention consiste à dire que le rez-de-chaussée est l'étage 1.
Quelques propriétés
Propriété : 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, sur le même "étage" de l'arbre.
3.4 Hauteur d'un arbre
La hauteur d'un ARBRE est liée à la distance maximale qu'on trouve dans l'arbre binaire. Est-il "profond" ou non ?
Convention profondeur de 0 pour la racine
pR = 0
On cherche le noeud le plus profond.
la hauteur d'un AB composé d'un noeud unique est 0.
la hauteur d'un ABV est donc -1.
Sur cet exemple, la hauteur de l'arbre est donc de 2.
Convention profondeur de 1 pour la racine
pR = 1
p>On cherche le noeud le plus profond.
la hauteur d'un AB composé d'un noeud unique est 1.
la hauteur d'un ABV est donc 0.
En terme de nombre d'arêtes, cela revient finalement à tenir compte des arêtes qui mènent aux ABV.
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 ou d'arbre dégénéré.
...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...
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.
3.5 Vocabulaire : quelques arbres particuliers
Arbre complet
On dit qu'un est complet lorsque les noeuds manquants sont tous sur son dernier étage.
Arbre parfait
Un arbre est parfait lorsqu'il ne manque aucun noeud.
Arbre dégénéré
Lorsque chaque noeud possède au maximum un seul noeud-fils, on dit qu'il est dégénéré.
Arbre 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 :
presque complet à la place de complet
complet à la place de parfait.
20-A° On considére la convention pR = 1.
Finir les calculs permettant d'obtenir la taille d'un Arbre Binaire Parfait 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 = 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 Parfait dont on connait la hauteur h.
...CORRECTION...
Profondeur de 1 pour la racine
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
On remarque qu'on peut visiblement écrire n + 1 = 2h
Ceci n'est pas une démonstration, on montre juste que cela SEMBLE fonctionner.
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 parfait 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 la convention pR = 0. Finir les calculs permettant d'obtenir la taille d'un Arbre Binaire Parfait 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 parfait ?
...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.
3.6 Encadrements de la hauteur d'un Arbre Binaire
Les deux cas particuliers
Les deux cas extrêmes sont :
Arbre binaire filiforme : chaque noeud n'a qu'un seul noeud-fils non vide au maximum.
Arbre binaire parfait : tous les noeuds possèdent deux noeuds-fils hormis les noeuds de l'étage le plus bas qui sont tous des feuilles.
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 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
Les signes ⌈ ⌉ indiquent un arrondi à l'entier supérieur (demi-crochets vers le haut).
>>> import math
>>> math.log2(15+1)
4.0>>> math.log2(16+1)
4.087462841250339
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
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
Ou encore :
⌊log2(n)⌋ ≤ h ≤ n - 1
Les signes ⌊ ⌋ indiquent un arrondi à l'entier inférieur (demi-crochets vers le bas).
>>> import math
>>> math.log2(15)
3.9068905956085187>>> math.log2(16)
4.0
On voit alors qu'un arbre de 15 noeuds a 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 peut être parfait. 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 Binaire est compris entre log2(n) et n.
Parfait ou pas ? : considérons un arbre binaire de 15 noeuds. Peut-il être parfait ?
On peut raisonner par l'absurbe : on considère qu'il est parfait, on applique la formule.
S'il peut être 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.
Si on tape ceci dans Python,
>>> 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.
Par contre, avec 16 noeuds, la formule donne un résultat non entier :
>>> 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à parfait. Si on en rajoute un, il faut nécessairement rajouter un étage...