Données Arbre

Identification

Infoforall

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 le HTML, dans lequel des balises contiennent 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>

Pourquoi dit-on que cette structure caractérise un arbre ?

Le DOM en arbre montant
Visualisation de l'arbre DOM en version montante

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.

Le DOM en arbre descendant
Visualisation de l'arbre DOM en version descendante

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.

La recherche dans DOM
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.

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.

Pas un arbre : il y a un cycle

Exemple 3 : ceci est un arbre mais on considérera cette année qu'il manque encore une information. Laquelle ?

Un arbre mais sans hierarchie
  • 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
Arbre 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) :

Domaines

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 ?

Arbre récursif

...CORRECTION...

Il y a 7 arbres en tout :

  1. L'arbre enraciné aa dont la racine est le noeud est A.
  2. L'arbre enraciné ac dont la racine est le noeud est C.
  3. L'arbre enraciné ab dont la racine est le noeud est B.
  4. L'arbre enraciné ag dont la racine est le noeud est G.
  5. L'arbre enraciné ad dont la racine est le noeud est D.
  6. L'arbre enraciné ae dont la racine est le noeud est E.
  7. 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 ?

Arbre récursif

...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 ?

Arbre récursif

...CORRECTION...

Arbre récursif

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

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 :

  1. L'arbre binaire peut être VIDE, alors qu'un arbre enraciné possède au moins un noeud-racine.
  2. 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 :

Arbre binaire Arbre binaire

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.

Arbre question 11

...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.

Arbre question 10

...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.

Arbre binaire

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.

Arbre question 10

...CORRECTION...

Arbre question 10
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.

  1. nvABV() -> Arbre Binaire VIDE
  2. Crée un nouvel ARBRE BINAIRE vide.
    On le note ainsi pour dire nouvelArbreBinaireVide() mais c'est plus long.

  3. nvAB(v:Element, g:Arbre Binaire, d:Arbre Binaire) -> Arbre Binaire NON VIDE
  4. 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.

  5. estABV(arbre:Arbre Binaire) -> bool
  6. Prédicat qui renvoie True si l'arbre est un arbre binaire vide.

  7. racine(arbre:Arbre Binaire NON VIDE) -> Noeud
  8. Renvoie le noeud jouant le rôle de la racine pour cet arbre binaire NON VIDE.

  9. contenu(noeud:Noeud) -> Element
  10. Renvoie l'élément rattaché au noeud transmis.

  11. gauche(arbre:Arbre Binaire NON VIDE) -> Arbre Binaire
  12. 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().

  13. droite(arbre:Arbre Binaire NON VIDE) -> Arbre Binaire
  14. 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".

Arbre question 10

...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.

Arbre question 10

...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.

Arbre question 10

...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

3.1 Taille d'un arbre

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.

Arbre question 10

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.

Arbre question 10

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.

Racine à une profondeur de 0

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.

Racine à une profondeur de 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.

Racine à une profondeur de 0
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.
Racine à une profondeur de 1

En terme de nombre d'arêtes, cela revient finalement à tenir compte des arêtes qui mènent aux ABV.

Arbre binaire

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.

Arbre question 16

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.

Arbre question 17

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.

Arbre question 18

...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 complet
Arbre parfait

Un arbre est parfait lorsqu'il ne manque aucun noeud.

Arbre parfait
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 dégénré
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.

Arbre filiforme
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.

  1. Finir les calculs permettant d'obtenir la taille d'un Arbre Binaire Parfait dont on vous donne la hauteur h.
  2. 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 = ...
  3. 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...

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.