Chapitre : Structure de données (2) : les arbres.

Introduction.

Les structures de données que nous avons vu jusqu’ici (tableaux, listes chaînées, piles et files) sontdites linéaires, c’est à dire qu’elles stockent les éléments les uns à la suite des autres : on peutles représenter comme des éléments placés sur une droite, un peu comme des oiseaux sur un filélectrique et sur un fil électrique, chaque oiseau a deux voisins (au plus), c’est assez ennuyeuxet pas pratique pour discuter. . . L’arbre est une structure de données qui généralise la liste : unnœud d’une liste a un seul successeur (le nœud suivant) alors que dans un arbre il peut en avoirplusieurs.

Sans en donner de définition formelle, vous avez déjà vu des arbres, tout comme vous aviez déjàvu la notion de pile ou de file.

Exemple 1 : l’arbre généalogique (la flèche signifie "a pour enfant") :

Exemple 2 : Plus proche de l’informatique, il concerne l’arborescence de fichiers stockés sur unordinateur. Les systèmes de fichiers dans les systèmes de type Linux ont aussi une structure enarbre.

I. Définitions et vocabulaire.

Un arbre est une structure de données non-linéaire (contrairement aux tableaux, listes, piles, etfiles qui sont des structures linéaires).

1

Définition : Une façon "simple" de définir un arbre est récursive (c’est à dire qu’on utilise la notiond’arbre pour définir la notion d’arbre) : soit il est vide (il est alors noté NIL) soit il est composé d’uneracine et de sous-arbres, ces sous-arbres étant eux-même des arbres.

Une autre façon de définir un arbre est de le décrire en disant qu’il est composé de nœuds etque chaque nœud, excepté le nœud racine a un unique parent, aussi appelé père (le nœud racinen’ayant pas de parent). Un nœud n qui a un parent p est dit enfant de p (ou fils de p).

Une feuille est un nœud qui n’a pas d’enfant.

Un chemin allant de la racine à une feuille est une branche de l’arbre.

Une arête est le segment qui relie 2 nœuds.

Remarque : Un nœud a un unique parent mais un nœud peut par contre avoir plusieurs enfants.

Exemple :

Les sommets 4, 5 et 6 sont les enfants du sommet 1. De même, le sommet 3 est l’unique enfant dusommet 4. Les sommets 2, 3 et 5 n’ont pas d’enfants, ce sont des feuilles.

Parmi tous les arbres possibles, on distingue une classe importante en pratique : les arbres bi-naires.

Définition : Un arbre binaire est un arbre dont chaque nœud a au plus 2 enfants : on distinguealors d’ailleurs son enfant gauche de son enfant droit.

On peut alors en donner une définition récursive : Un arbre binaire est soit un arbre vide soitil est composé d’une racine avec un sous-arbre gauche et un sous-arbre droit qui sont tous lesdeux des arbres binaires.

Remarques :

• À chaque noeud d’un arbre binaire, on associe une "clé" (valeur associée au noeud on peutaussi utiliser le terme "valeur" à la place de clé).

2

• On peut définir une feuille comme étant un nœud qui possède l’arbre vide (Nil) commeenfants gauche et droit.

• On peut démontrer que tout arbre peut "se transformer" en arbre binaire (mais ce n’est pasau programme.

Exemple :

Dans cet arbre, la racine est le nœud (de clé ou de valeur) 1. Il a deux enfants : le sous-arbre qui a2 pour racine, et le sous-arbre droit qui a 3 pour racine.

L’arbre est ainsi formé de sa racine (le nœud 1), du sous-arbre gauche formé du nœud 2 (sa racine),du nœud 4 et du nœud 5 et du sous-arbre droit formé du nœud 3 (sa racine) et du nœud 6.

Les feuilles de l’arbre du dessus sont les nœuds de valeurs 4, 5 et 6. Les autres nœuds sont appelésnœuds internes.

Vocabulaire :

• La profondeur d’un nœud dans un arbre est le nombre de nœuds du chemin qui va de laracine à ce nœud. La racine d’un arbre est à une profondeur de 1 (vous pouvez trouver 0 danscertains cours). la profondeur d’un noeud est égale à la profondeur de son prédécesseur plus1.

• La hauteur d’un arbre est la profondeur maximale des nœuds de l’arbre. L’arbre vide a unehauteur de 0, et l’arbre réduit à une racine a une hauteur de 1.

• La taille d’un arbre est le nombre de nœuds de l’arbre.

Exemple : La hauteur de l’arbre précédent est 3. La profondeur du nœud 3 est 2 (tout comme lenœud 2).

Remarque : Il est possible de trouver des définitions différentes pour la profondeur et la hauteur.Certains ouvrages considèrent qu’un arbre réduit à sa racine a pour hauteur 0 et non 1 et quel’arbre nul (NIL) a alors pour hauteur -1.

Exercices (mathématiques) :

1. Quel est le nombre maximal de feuilles d’un arbre binaire de hauteur h>0 ?

Intuitivement, le nombre maximal de feuilles est de 2h−1. On peut le démontrer proprement parrécurrence. . .

Soit h un entier naturel strictement positif, montrons par récurrence, qu’un arbre binaire de hau-teur h>0 a au plus 2h−1 feuilles.

3

Si h=1 alors l’arbre binaire a une seule feuille (donc 20) qui est la racine, donc la récurrence estinitialisée.

Soit un entier naturel h>0, supposons qu’un arbre binaire de taille h ait au plus 2h−1 feuilles etmontrons alors qu’un arbre binaire de hauteur h + 1 a au plus 2h feuilles.

Par définition, un arbre binaire de hauteur de hauteur h + 1 est formé d’un arbre gauche de hauteurh qui a donc, par hypothèse de récurrence, au plus 2h−1 feuilles et d’un arbre droit de hauteur hqui a donc au plus 2h−1 feuilles. Au total un arbre de hauteur h + 1 a donc au plus 2× 2h−1 soit 2h

feuilles.

Par principe de récurrence, un arbre binaire de hauteur h>0 a donc au plus 2h−1 feuilles.

2. Quel est le nombre maximal de nœuds d’un arbre binaire de hauteur h>0 ?

Tout comme dans le cas précédent, intuitivement, on constate qu’un arbre binaire de hauteur h aau plus 2h − 1 nœuds. On peut démontrer ce résultat "facilement" par récurrence.

Soit h un entier naturel strictement positif, montrons par récurrence, qu’un arbre binaire de hau-teur h a au plus 2h − 1 nœuds.

Si h=1 alors l’arbre binaire est réduit à sa racine, il a donc 1 nœud et 1 = 21 − 1 donc la récurrenceest initialisée.

Soit h un entier naturel, supposons qu’un arbre binaire de hauteur h ait au plus 2h − 1 nœuds etmontrons alors qu’un arbre binaire de hauteur h + 1 a au plus 2h+1 − 1 nœuds.

Par définition, un arbre binaire de hauteur de hauteur h + 1 est formé d’un arbre gauche de hauteurh qui a donc, par hypothèse de récurrence, au plus 2h − 1 nœuds, d’un arbre droit de hauteur hqui a donc au plus 2h − 1 nœuds et de sa racine (qui est 1 nœud). Au total un arbre de hauteur h+ 1 a donc au plus 2× (2h − 1) + 1 = 2h+1 − 2 + 1 = 2h+1 − 1 nœuds.

Par principe de récurrence, un arbre binaire de hauteur h>0 a donc bien au plus 2h − 1 nœuds.

3. Quelle est la hauteur h minimale d’un arbre de n nœuds ?

D’après la question précédente, un arbre de hauteur h a au plus 2h − 1 nœuds. Soit n le nombrede nœuds d’un arbre. On a donc n ≤ 2h − 1 donc n + 1 ≤ 2h donc log2(n + 1) ≤ h. La hauteurminimale d’un arbre de n nœuds est donc de log2(n + 1).

Définitions :

Un arbre binaire filiforme ou dégénéré est un arbre dans lequel tous les nœuds internes n’ontqu’un seul fils. (Un arbre filiforme ne possède donc qu’une unique feuille.)

Un arbre binaire localement complet est un arbre dont tous les nœuds internes possèdent ex-actement deux fils. (Autrement dit, un arbre binaire localement complet est un arbre dont chaquenœud possède zéro ou 2 fils. L’arbre vide n’est pas localement complet.)

4

Un arbre binaire complet est un arbre binaire localement complet dans lequel toutes les feuillessont à la même profondeur. (Il s’agit d’un arbre dont tous les niveaux sont remplis.)

Il nous reste maintenant à voir un certains nombre d’algorithmes sur les arbres :

• Parcourir un arbre

• identifier les opérations primitives pour manipuler les arbres

• et découvrir les ABR (arbres binaires de recherche).

II. Algorithmes.

1. Déterminer la hauteur.

Pour calculer la hauteur d’un arbre binaire, nous allons nous baser sur cet algorithme récursif :

• un arbre vide est de hauteur 0

• un arbre non vide a pour hauteur 1 + la hauteur maximale entre ses 2 fils : le sous-arbregauche et le sous-arbre droit.

On peut écrire cet algorithme en pseudo-langage :

5

[ ]: fonction hauteur_arbre(A : arbre) {si A est vide {

retourne 0 }sinon {

retourne 1 + maximum(hauteur_arbre(sous-arbre gauche) ,␣↪→hauteur_arbre(sous-arbre droit))

}

Bien que l’algorithme soit simple à énoncer et à programmer, son utilisation n’est pas si facile

Exemple :

Les notations utilisées ci-dessous ne sont pas correctes, on désignera un arbre par sa racine, par exemplehauteur(B) designera la hauteur du demi-arbre gauche de l’arbre précédent.

Hauteur = 1 + max(hauteur(B) , hauteur(F))

hauteur(B) = 1 + max(hauteur(C), hauteur(D))

hauteur(C) = 1+ max(hauteur(E) , 0) (pas d’arbre droit issus de C = Nil)

hauteur(E) = 1 + max(0 , 0) = 1 (pas de sous-arbre issus de E)

hauteur(D) = 1 + max(0 , 0) = 1 (pas de sous-arbre issus de D)

donc hauteur(C) = 1 + max(1 , 0) = 2

donc hauteur(B) = 1 + max(2 , 1) = 3

On calcule de même que hauteur(F) = 3

donc Hauteur = 1 + max(3 , 3) = 4

Remarque : On peut remplacer "si A est vide retourne 0" par "si A est une feuille, retourne 1".

2. Calculer la taille.

Tout comme pour le calcul de la hauteur, pour calculer la taille d’un arbre binaire, on se base surun algorithme récursif :

• Si l’arbre est vide, renvoyer 0

• Sinon renvoyer 1 plus la somme du nombre de nœuds du sous-arbre gauche et du sous-arbredroit.

6

On peut écrire cet algorithme très facilement en pseudo-langage :

[ ]: fonction taille_arbre(A : arbre) {si A est vide {

retourne 0 }sinon {

retourne 1 + taille_arbre(sous-arbre gauche) + taille_arbre(sous-arbre␣↪→droit)

}

Exemple : En reprenant l’arbre précédent (et les notations)

Taille = 1 + taille(B) + taille(F)

taille(B) 1 + taille(C) + taille(D)

taille(C) = 1 + taille(E) + taille(Nil)

taille(D) = 1 + taille(Nil) + taille(Nil) = 1 + 0 + 0 = 1

taille(E) = 1 + taille(Nil) + taille(Nil) = 1 + 0 + 0 = 1

donc taille(C) = 1 + 1 = 2

donc taille(B) = 1 + 2 + 1 = 4

de même, on peut calculer taille(F) = 5

donc Taille = 1 + 4 + 5 = 10

Tout comme pour l’algorithme précédent, on peut remplacer "si A est vide retourne 0" par "si Aest une feuille, retourne 1".

3. Parcours d’un arbre binaire.

a. Parcours en profondeur.

Pour toute cette partie, on utilisera l’arbre binaire suivant :

7

On effectue un parcours autour de l’arbre en allant de la gauche vers la droite et en suivant lespointillés dans l’ordre des numéros indiqués (on dit qu’on traverse l’arbre en profondeur par lagauche) :

a-1. Différents parcours en profondeur.

À partir de ce contour, on définit trois parcours des sommets de l’arbre. Ces trois parcourss’appuient sur la structure récursive des arbres : on applique récursivement le parcours aux sous-arbres gauche et droit. C’est le moment où on liste la racine de chaque sous-arbre qui caractèriseces 3 différents parcours.

On notera un arbre (r, g, d) (avec r = racine, g = sous-arbre gauche et d = sous-arbre droit).

1. parcours préfixe : Dans le parcours préfixe d’un arbre (r, g, d), on commence par lister r,puis on parcourt le sous-arbre g et enfin le sous-arbre d.

on affiche donc la valeur de chaque nœud la première fois qu’on le rencontre lors du parcoursde gauche à droite décrit au début du 3.

Ce qui donne ici : r, a, c, h, d, i, j, l, b, e, k, f.

2. parcours postfixe (ou suffixe) : Dans le parcours postfixe (on dit aussi suffixe), on com-mence par parcourir les deux sous-arbres g et d et on termine en listant r.

Ce qui revient à dire qu’on affiche la valeur de chaque nœud après avoir affiché la valeur dechacun de ses fils.

Ce qui donne ici : h, c, i, l, j, d, a, k, e, f, b, r.

3. parcours infixe :

Dans le parcours infixe, on commence par parcourir le sous-arbre g, puis on liste r, et on terminepar le sous-arbre d.

Ce qui revient à dire qu’on affiche la valeur de chaque nœud ayant un fils gauche la seconde foisqu’on le voit et de chaque nœud sans fils gauche la première fois qu’on le voit.

8

Ce qui donne ici : c, h, a, i, d, l, j, r, k, e, b, f.

a-2. Les algorithmes en pseudo-langage.

On reprend les 3 algorithmes précédents en utilisant leur structure récursive pour les écrire facile-ment en pseudo-langage.

Parcours préfixe :

[ ]: fonction parcours_prefixe(A : arbre) {Si A non vide {

afficher(valeur de A.racine)parcours_prefixe(A.gauche)parcours_prefixe(A.droit)

}}

Parcours postfixe :

[ ]: fonction parcours_postfixe(A : arbre) {Si A non vide {

parcours_postfixe(A.gauche)parcours_postfixe(A.droit)afficher(valeur de A.racine)

}}

Parcours infixe :

[ ]: fonction parcours_infixe(A : arbre) {Si A non vide {

parcours_infixe(A.gauche)afficher(valeur de A.racine)parcours_prefixe(A.droit)

}}

b. Parcours en largeur.

Nous allons aborder un type de parcours un peu plus compliqué à programmer alors que c’estnaturellement le plus simple : le parcours en largeur. (BFS pour Breadth-First Search en anglais).

Il s’agit d’un parcours dans lequel, on traite les noeuds un par un sur un même niveau. On passeensuite sur le niveau suivant, et ainsi de suite.

Le parcours en largeur de l’arbre du a. est : r, a, b, c, d, e, f, h, i, j, k, l.

Par récurrence ou itération ça ne marche pas. . . La difficulté est de garder le pointeur sur un noeudjusqu’à ce qu’on s’intéresse au fils du noeud.

9

L’algorithme de parcours largeur utilise une File pour mémoriser les descendants directs dechaque noeud rencontré. Ce qui permet à la hauteur suivante de les récupérer dans l’ordre derencontre.

Cela donne l’algorithme itératif suivant :

On suppose l’arbre non vide.

• On place l’arbre dans la file.

• Tant que la file n’est pas vide, on défile un élément qui est un arbre, on affiche la valeur desa racine et on place dans la file chacun de ses deux sous-arbres s’ils ne sont pas vides.

[ ]: fonction PARCOURS-LARGEUR(A : arbre) {f = file()enfiler(A) dans f #on place A dans la filetant que f non vide :{

x ← defiler(f)affiche x.racine #on affiche la racinesi x.gauche is not NIL : { #si fils gauche non vide on l'enfile dans f

enfiler(x.gauche)}si x.droit is not NIL : { #si fils droit non vide on l'enfile dans f

enfiler(x.droit)}}

}

Exemple :

L’algorithme donne donc :

On désigne l’arbre de racine A par (A).

On enfile (A) -> f : A

f non vide donc on défile f et on affiche A -> f : _

on enfile (B) et (C) -> f : C , B

f non vide, on défile f et on affiche B -> f : C

10

on enfile (D) et (E) -> f : E, D, C

f non vide donc on défile f et on affiche C -> f : E, D

on enfile (F) et (G) -> f : G, F, E, D

f non vide donc on défile f et on affiche D -> f : G, F, E

D n’a pas de fils gauche ni de fils droit donc on n’enfile rien

f non vide donc on défile f et on affiche E

E n’a pas de fils gauche ni de fils droit donc on n’enfile rien

f non vide donc on défile f et on affiche F

F n’a pas de fils gauche ni de fils droit donc on n’enfile rien

f non vide donc on défile f et on affiche G

G n’a pas de fils gauche ni de fils droit donc on n’enfile rien

f est vide

4. Arbre binaire de recherche.

a. Définition : Un arbre binaire de recherche est un arbre binaire formé de noeuds dont lesvaleurs sont ordonnables (qui peuvent être classées) et qui vérifie la propriété :

Pour tout noeud x de cet arbre :

- Si y est un noeud du sous-arbre gauche de x, alors il faut que y.valeur 6 x.valeur

- Si y est un noeud du sous-arbre droit de x, il faut alors que x.valeur 6 y.valeur

Exemple :

Exercice :

Écrire le parcours infixe de l’arbre précédent. Que remarquez-vous ?

Remarques :

• Pour accéder à la valeur la plus petite (resp. la plus grande) dans un ABR il suffit de descen-dre sur le fils gauche (resp. sur le fils droit) autant que possible. Le dernier noeud visité, quin’a pas de fils gauche (resp. droit), porte la valeur la plus petite (resp. la plus grande) del’arbre.

11

• Le parcours infixe trie la liste. Les éléments de gauche sont en effet, par construction, pluspetits qu’un noeud et sont affichés avant le nœud dans l’ordre infixe et les éléments de droitequi sont, par construction, plus grands sont affichés dans l’ordre infixe après le nœud. Par"récurrence", on a donc un affichage des éléments de la liste dans l’ordre.

b. Recherche d’une clé dans un arbre binaire de recherche Nous allons maintenant étudier unalgorithme permettant de rechercher une valeur k dans un arbre binaire de recherche. Si k estbien présent dans l’arbre binaire de recherche, l’algorithme renvoie vrai, dans le cas contraire, ilrenvoie faux.

Un arbre binaire de recherche est fait pour faciliter la recherche d’informations.

La recherche de la valeur particulière d’un noeud de l’arbre de recherche peut être définie simple-ment de manière récursive :

Soit un sous-arbre de racine ni,

• si la valeur recherchée est celle de la racine ni, alors la recherche est terminée. On a trouvé lenoeud recherché.

• sinon, si ni est une feuille (pas de fils) alors la recherche est infructueuse et l’algorithme setermine.

• si la valeur recherchée est plus grande que celle de la racine alors on explore le sous-arbrede droite c’est à dire que l’on remplace ni par son noeud fils de droite et que l’on relance laprocédure de recherche à partir de cette nouvelle racine.

• de la même manière, si la valeur recherchée est plus petite que la valeur de ni, on remplaceni par son noeud fils de gauche avant de relancer la procédure.

Ce qui donne en pseudo-code :

[ ]: fonction rechercheABR(A : arbre,n : valeur){si n == racine de A {

retourner Vrai }si A est une feuille {

retourner Faux}si n < racine {

retourner rechercheABR(fils gauche,n) }si n > racine:{

retourner rechercheABR(fils droit,n)}}

Remarque : Cet algorithme de recherche d’une valeur dans un arbre binaire de recherche ressem-ble à la recherche dichotomique vue en première.

L’intérêt des ABR réside dans le fait que, s’ils sont équilibrés, c’est-à-dire si chaque nœud a à peuprès autant de descendants gauches que de descendants droits, alors la recherche d’un élémentest dichotomique (c.-à-d. : à chaque étape la moitié des clés restant à examiner sont éliminées),et demande donc log2(n) itérations ; l’insertion consécutive à une recherche a un coût nul. Lacomplexité en temps, dans le pire des cas, de l’algorithme de recherche d’une valeur dans un

12

arbre binaire de recherche équilibré est donc O(log2(n)). Dans le cas où l’arbre est filiforme, lacomplexité est O(n) (un algorithme en O(log2(n)) est plus "efficace" qu’un algorithme en O(n)).

13