Aller au contenu

Arbres - Généralités

I. Introduction⚓︎

arbres

Source Gilles Lassus

Arbre

Un arbre est une structure hiérarchique permettant de représenter de manière symbolique des informations structurées.

L'arborescence d'un disque dur

Les systèmes Unix (MacOS ou GNU/Linux) organisent leur disque dur suivant l'arborescence ci-dessous :

Unix

Un arbre généalogique des descendants ou des ascendants

graph TD
A(Vous)
B(Père)
C(Mère)
F(Grand-père paternel)
G(Grand-mère paternelle)
D(Grand-père maternel)
E(Grand-mère maternelle)
A --- B
A --- C
B --- F
B --- G
C --- D
C --- E

Organisation des matchs d'un tournoi de sport

graph TD
A(Vainqueur)
B(Finaliste 1)
C(Finaliste 2)
D(Demi-finaliste 1)
E(Demi-finaliste 2)
F(Demi-finaliste 3)
G(Demi-finaliste 4)
H(Quart-finaliste 1)
I(Quart-finaliste 2)
J(Quart-finaliste 3)
K(Quart-finaliste 4)
L(Quart-finaliste 5)
M(Quart-finaliste 6)
N(Quart-finaliste 7)
P(Quart-finaliste 8)
A --- B
A --- C
B --- D
B --- E
C --- F
C --- G
D --- H
D --- I
E --- J
E --- K
F --- L
F --- M
G --- N
G --- P

II. Terminologie⚓︎

Attention

l'analogie avec les arbres réels peut s'avérer trompeuse. Les arbres - en informatique - sont le plus souvent représentés avec la racine en haut, puis les nœuds, et les feuilles en bas.

racines envers

Un arbre

Un arbre est une structure hiérarchique de données, composée de nœuds.

terminologie

Source Gilles Lassus

  • Chaque nœud a exactement un seul nœud père, à l'exception du nœud racine qui est le seul nœud à ne pas avoir de père. (oui, la racine d'une arbre est en haut)

  • Chaque nœud peut avoir un nombre quelconque de fils, dont il est le père.

  • Les nœuds qui n'ont pas de fils sont appelés les feuilles (ou nœuds externes).
  • Les nœuds qui ne sont pas des feuilles sont des nœuds internes.
  • Le nom de chaque nœud est appelé son étiquette.

Exemple

graph TD
A(A)
B(B)
C(C)
D(D)
E(E)
F(F)
G(G)
H(H)
I(I)
A --- B
A --- C
B --- D
B --- E
B --- F
C --- G
E --- H
E --- I
  • La racine est le nœud A.
  • Le nœud B possède 3 fils (les nœuds D, E et F), le noeud C possède un fils (le nœud G), le nœud F ne possède aucun fils.
  • Le nœud B a pour père le nœud A.
  • Les feuilles sont les nœuds D, H, I, F et G (ceux qui n'ont pas de fils).

Attention

Attention : il faut bien repérer dans les définitions suivantes, si on compte les nœuds, ou si on regarde la longueur d'une branche.

Il y a en effet un décalage de 1 entre ces deux nombres.

Conventions retenues dans ce cours

  • ⚠️Un arbre ne contenant qu'un élément à une hauteur de 1.
  • La profondeur de la racine est 0

Définitions

  • La taille d'un arbre est le nombre de nœuds qu'il possède.

  • La profondeur d'un nœud ou d'une feuille d'un arbre est la longueur du chemin le plus court vers la racine .

    • La profondeur d’un nœud est égale à la profondeur de son père plus 1
    • Si un nœud est à une profondeur \(p\), tous ses fils sont à une profondeur \(p+1\)

  • Il existe plusieurs méthode pour déterminer la profondeur d'un nœud :

    • La profondeur d'un nœud est le nombre d'arêtes entre la racine et ce nœud (c'est la convention retenue dans ce cours)
    • La profondeur d’un nœud est le nombre de nœuds du chemin qui va de la racine à ce nœud sans compter la racine
    • 🤿 on peut imaginer que la racine est à la surface de l'eau, donc à une profondeur 0, et que les nœuds sont à des profondeurs 1, 2, 3, etc.
      Dans l'arbre précédent : profondeur de B = 1 - profondeur de I = 3 .

  • La hauteur d’un arbre est le nombre de nœuds du plus long chemin de la racine aux feuilles en comptant la racine et la feuille.

Dans l'arbre précédent : hauteur de l'arbre = 4

Autres définitions

Attention : On trouve aussi dans la littérature, que la profondeur de la racine est égale à 1, ce qui modifie la hauteur de l'arbre également puisqu'alors l'arbre réduit à la racine a pour hauteur 0 et l'arbre vide a pour hauteur -1. Les deux définitions se valent, il faut donc bien lire celle qui est donnée.

Exemple

graph TD
A(A)
B(B)
C(C)
D(D)
E(E)
F(F)
G(G)
H(H)
I(I)
A --- B
A --- C
B --- D
B --- E
B --- F
C --- G
E --- H
E --- I
  • La taille de l'arbre est égale à 9 (il possède 9 nœuds : 4 nœuds internes et 5 feuilles).
  • Le nœud E a une profondeur égale à 2 (le chemin A-B-E est de longueur 2).
  • La hauteur de l'arbre est égale à 4 car la branche A-B-E-H possède 4 nœuds (la profondeur maximale est égale à 3, c'est celle des nœuds les plus profonds : H et I. On a bien profondeur + 1 = hauteur).

III. Arbres binaires⚓︎

👉 Dans la suite, on ne s'intéressera qu'aux arbres dont les nœuds ont au plus deux fils.

Les arbres binaires sont des cas particuliers d'arbre : l'arbre du tournoi sportif et l'arbre "père, mère..." sont des arbres binaires, en revanche, l'arbre représentant la structure du système de fichier n'est pas un arbre binaire.

Arbre binaire

Un arbre binaire est un arbre dont tous les nœuds ont au plus deux fils.

Exemple

L'arbre vu dans le paragraphe précédent n'est pas binaire car le nœud B possède 3 fils. En revanche, l'arbre ci-dessous est lui un arbre binaire.

graph TD
A(A)
B(B)
C(C)
D(D)
F(F)
M( )
G(G)
E(E)
H(H)
I(I)
L( )
J(J)
K(K)


A --- B
A --- C
B --- D
B --- F
C --- M
C --- G
D --- E
D --- H
F --- I
F --- L
G --- J
G --- K
linkStyle 4 stroke-width:0px;
linkStyle 9 stroke-width:0px;
style L opacity:0;
style M opacity:0;

Définition et vocabulaire spécifique aux arbres binaire (A connaître par ❤️)

Les définitions vues précédemment pour des arbres quelconques restent valables pour les arbres binaires. Pour les arbres binaires :

  • chaque nœud possède deux sous-arbres, éventuellement vides, que l'on appelle sous-arbre gauche et sous-arbre droit.
  • les nœuds qui ne sont pas des feuilles peuvent avoir une fils gauche et/ou un fils droit.

sous_arbres.jpeg

Les sous-arbres gauche et droit de A sont eux-mêmes des arbres dont les racines sont respectivement B et C. B et C possèdent eux-même des sous-arbres gauche et droit.

  • le nœud C possède un sous-arbre gauche, qui est vide, et un sous-arbre droit qui est l'arbre dont la racine est G,
  • le nœud B possède un sous-arbre gauche, qui est l'arbre dont la racine est D, et un sous-arbre droit qui est l'arbre dont la racine est F.
  • et ainsi de suite.

Fils gauche et fils droit

Il ne faut pas confondre fils gauche et fils droit, ainsi les arbres suivants ne sont pas les mêmes :

4 arbres

Structure récursive

Il est aussi important de bien noter que l'on peut aussi voir les arbres comme des structures récursives : les fils d'un nœud sont des arbres (sous-arbre gauche et un sous-arbre droite dans le cas d'un arbre binaire), ces arbres sont eux mêmes constitués d'arbres...

A vos crayons 😊

Tracez tous les arbres binaires possibles avec 3 nœuds puis quelques-uns avec 4 nœuds.

IV. Visualiser un arbre binaire⚓︎

😀 Voici une correction ...

V. Relations entre la hauteur et la taille d'un arbre binaire⚓︎

😀 Voici une correction ...

VI. Implémentations⚓︎

Plusieurs possibilités

Il existe, comme toujours, plusieurs implémentations possibles d'un arbre binaire. Nous allons voir dans ce TP quelques possibilités qui s'offrent à nous.

Partie 1 : implémentation avec une seule classe

Télécharger les trois fichiers, et les enregistrer dans un même dossier.

🌐 Fichier à télécharger : Fichier visu_arbre_3.py : "Clic droit", puis "Enregistrer la cible du lien sous"

🌐 Fichier à télécharger : Fichier visu_tree.py : "Clic droit", puis "Enregistrer la cible du lien sous"

🌐 Notebook jupyter à télécharger : Fichier arbres_une_classe_sujet.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

Lien pour lire le notebook jupyter : Notebook Basthon

😀 Voici une correction ... à télécharger dans le même dossier que les fichiers précédents.

🌐 Fichier arbres_une_classe_corr.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

Partie 2 : implémentation avec un dictionnaire

Après avoir téléchargé le fichier, vous pourrez le lire à partir de Basthon

🌐 TD à télécharger : Fichier arbre_dico_2022_sujet.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

😀 Voici une correction ...

🌐 Fichier arbre_dico_2022_corr.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

Crédits⚓︎

Gilles Lassus, Jean-Louis Thirot , Mireille Coilhac, Valérie Mousseaux, sur la base du travail de :

  • David ROCHE publié sur Pixees
  • Equipe éducative DIU EIL, Université de Nantes.
  • Ressource d'accompagnement Eduscol sur les structures de données.
  • Livre Prepabac NSI, Tle, G. Connan, V. Petrov, G. Rozsavolgyi, L. Signac, éditions HATIER.