Terminale - Arbres

Les arbres : une nouvelle structure de données

Jusqu'à présent, nous avons appris à manipuler des structures de données linéaires : listes, dictionnaires, piles, files. Bien que très utiles, ces structures de données ne sont pas adaptées à tous les problèmes, comme la classification ou la recherche des données, pour lesquels il est préférable d'utiliser une structure hiérarchique.

Un peu de vocabulaire

Un arbre est une structure de données hiérarchique constituée de noeuds. Comme les listes, les arbres permettent de représenter un nombre variable de données, mais sont beaucoup plus adaptés à la recherche des données.

Les noeuds sont reliés entre eux par des arêtes. Un noeud peut avoir des enfants, qui sont eux mêmes des autres noeuds. Chaque noeud possède un parent unique, sauf le noeud le plus haut, appelé racine de l'arbre. Les noeuds sans enfants sont les feuilles de l'arbre. Une branche est une suite finie de noeuds consécutifs, de la racine vers une feuille.

Traditionnellement, on représente un arbre "à l'envers", avec la racine tout en haut et les feuilles tout en bas.

L'arbre ci-dessus possède les caractéristiques suivantes :

• Il se compose de 9 noeuds, nommés A,B,C,D,E,F,G,H et I. On dit alors que sa taille est égale à 9.
• Le noeud A est la racine de l'arbre.
• Le noeud A possède deux enfants : les noeuds B et C.
• Le noeud B est le parent des noeuds D,E et F.
• Les feuilles de l'arbre sont les noeuds D,E,F,H et I.

Chaque noeud possède une hauteur ou profondeur, définie comme le nombre d'arêtes entre ce noeud et la racine. Par exemple, la hauteur du noeud B est égale à 1, tandis que la hauteur du noeud H est égale à 3.

On définit alors la hauteur de l'arbre comme la plus grande des hauteurs des noeuds. Dans l'exemple ci-dessus, on a donc un arbre de hauteur 3.

Enfin, on définit l'arité d'un arbre comme le nombre maximal d'enfants qu'un noeud peut avoir. Dans l'exemple, c'est le noeud B qui possèdent le plus d'enfants : 3. L'arité de l'arbre est alors égale à 3.

Exemples courants

Parmi les exemples rencontrés dans la vie courante, on peut notamment citer les arborescences de fichiers :

ou encore l'arbre de la vie :

Arbres binaires

Nous allons maitenant considérer des arbres d'arité 2, que l'on appelle arbres binaires. Ces arbres sont constitués de noeuds possédant 0,1 ou 2 enfants. À partir d'un noeud, on définit deux sous-arbres disjoints : le sous-arbre gauche (abrégé SAG) et le sous-arbre droit (abrégé SAD).

Mesures sur les arbres binaires

Sur un arbre binaire $\alpha$, on peut "prendre des mesures" comme :

• la taille de l'arbre, notée $T(\alpha)$
• la hauteur d'un noeud $N$, notée $H(N)$
• la hauteur de l'arbre, notée $H(\alpha)$
• la longueur de cheminement de l'arbre, définie comme la somme des hauteurs de chacun des noeuds : $$ LC(\alpha) = \sum_{N \in \mathcal{N}(\alpha)} H(N) $$ où $\mathcal{N}(\alpha)$ est l'ensemble des noeuds de l'arbre $\alpha$
• la profondeur moyenne de l'arbre : $$ PM(\alpha) = \frac{LC(\alpha)}{T(\alpha)} $$

Pour l'exemple, reprenons l'arbre binaire précédent, que l'on appelera $\alpha$ :

• L'arbre possède 12 noeuds, donc : $$ T(\alpha) = 12 $$
• Les hauteurs de chaque noeud sont les suivantes :
  • $H(A) = 0$ (racine)
  • $H(B) = H(C) = 1$
  • $H(D) = H(E) = H(F) = H(G) = 2$
  • $H(H) = H(I) = H(J) = H(K) = H(L) = 3$
• La hauteur de l'arbre est le maximum des hauteurs des noeuds : $$ H(\alpha) = 3 $$
• La longueur de cheminement est la somme des hauteurs de chacun des noeuds : $$ LC(\alpha) = 1 \times 0 + 2 \times 1 + 4 \times 2 + 5 \times 3 = 25 $$
• La profondeur moyenne de l'arbre est : $$ PM(\alpha) = \frac{LC(\alpha)}{T(\alpha)} = \frac{25}{12} \simeq 2,08$$

Expressions arithmétiques

Une expression arithmétique peut être représentée sous la forme d'un arbre binaire en exprimant une opération dans les noeuds internes et les nombres dans les feuilles. Par exemple, l'expression $7 + (4+5) \times 8$ se représente avec l'arbre ci-dessous :

Noeuds et étiquettes

Terminons par une remarque : chaque noeud d'un arbre (binaire ou non) est repéré de manière unique par son identifiant, généralement une lettre ou un chiffre. Il est également commun de donner une étiquette à un noeud, qui représente sa valeur. Ainsi, un noeud est comme une variable, représenté par un nom (son identifiant) et associé à une valeur (son étiquette).

Ainsi, deux noeuds peuvent avoir la même étiquette, mais jamais le même identifiant.

Arbres binaires de recherche

Un arbre binaire de recherche est un arbre pour lequel l'étiquette d'un noeud est appelée clé. L'arbre binaire de recherche satisfait aux critères suivants :

• Les clés de tous les noeuds du sous-arbre gauche d'un noeud $N$ sont inférieures ou égales à la clé de $N$
• Les clés de tous les noeuds du sous-arbre droit d'un noeud $N$ sont strictement supérieures à la clé de $N$

Un arbre binaire de recherche est dit équilibré si la différence de longueur entre la branche la plus longue et la branche la moins longue est au plus égale à 1.

Nous verrons en Algorithmique que la recherche d'un élément est bien plus rapide sur un arbre binaire de recherche équilibré.

Représentations d'un arbre binaire

Il existe différentes manières de représenter un arbre binaire. Voici les principales.

Sous forme d'un tableau

Représentation contigüe

Une autre façon de représenter un arbre binaire est un tableau à 1 dimension !
Le tableau, noté $T$, est ordonné de sorte que la case $T_i$ représente l'étiquette du noeud $i$.

• $T_1$ représente la racine
• $T_2$ est le fils gauche de la racine $T_1$
• $T_3$ est le fils droit de la racine $T_1$
• $T_4$ est le fils gauche de $T_2$, le fils gauche de la racine
• $T_5$ est le fils droit de $T_2$, le fils gauche de la racine
• $T_6$ est le fils gauche de $T_3$, le fils droit de la racine
• $T_7$ est le fils droit de $T_3$, le fils droit de la racine
• $T_8$ est le fils gauche de $T_4$, le fils gauche du fils gauche de la racine (!)
• ...etc...

Plus généralement, les enfants du noeud $i$ ont pour étiquettes $T_{2i}$ et $T_{2i+1}$.

Arbre et tableau contigu correspondant

Représentation abstraite

On peut définir un arbre de manière récursive, les sous-arbres d'un noeud étant encore des arbres !

Formellement, on considère les trois opérations de base suivantes :

• ARBRE_VIDE() : retourne un arbre vide
• FEUILLE(etiquette) : retourne un arbre sans enfants, avec l'étiquette etiquette
• ARBRE(etiquette, fils_gauche, fils_droit) : retourne un arbre défini par une étiquette et deux fils gauche et droit

Ces trois opérations élémentaires permettent de représenter n'importe quel arbre.

# Exemple d'implémentation
            
A = FEUILLE(5)
B = FEUILLE(4)
C = ARBRE(3, B, A)
D = FEUILLE(2)
E = ARBRE(1, D, C)

Ci-dessous, le détail de chaque arbre ainsi créé :

A = FEUILLE(20)
B = ARBRE(15, A, ARBRE_VIDE())
C = FEUILLE(3)
D = ARBRE(8,C,B)
E = FEUILLE(4)
F = ARBRE(5, ARBRE_VIDE(), E)
G = ARBRE(10, D, F)