Chapitre : Structure de données (2) : les arbres.¶
Les structures de données que nous avons vu jusqu'ici (tableaux, listes chaînées, piles et files) sont dites linéaires, c'est à dire qu'elles stockents les éléments les uns à la suite des autres : on peut les représenter comme des éléments placés sur une droite, un peu comme des oiseaux sur un fil électrique où chaque oiseau a au plus deux voisins.
Sans en donner de définition formelle, on a déjà vu des arbres en informatique (tout comme dans la vie réelle).
Par exemple : l'arbre généalogique (la flèche signifie "a pour enfant") :
ou en informatique, l’arborescence de fichiers stockés sur un ordinateur ou le DOM (qui représente la structure d'un document HTML):
Un arbre est un type qui représente une structure de données hiérarchique (contrairement aux tableaux, listes, piles, et files qui sont des structures linéaires) formée d'éléments connectés entre eux appelés nœuds.
Définition récursive : Une façon "simple" de définir un arbre est récursive (c'est à dire qu'on utilise la notion d'arbre pour définir la notion d'arbre) : soit il est vide (il est alors noté NIL) soit il est composé d'un nœud racine 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 : Un arbre est composé de nœuds connectés entre eux : le nœud à l'origine est appelé père (ou parent) et le nœud destination est appelé fils (ou enfant). Le seul nœud à ne pas avoir de père (à l'origine de tous les autres nœuds) est la racine.
Vocabulaire : :
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 :
Parmi tous les arbres possibles, on distingue une classe importante : les arbres binaires.
Définition : Un arbre binaire est un arbre dont chaque nœud a au plus 2 enfants : on distingue alors 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 soit il est composé d'une racine ayant un sous-arbre gauche et un sous-arbre droit qui sont tous les deux des arbres binaires.
Remarques :
À chaque noeud d'un arbre binaire, on associe une clé (ou une valeur).
On peut définir une feuille comme étant un nœud qui possède l’arbre vide (Nil) comme enfants gauche et droit.
On peut démontrer que tout arbre peut "se transformer" en arbre binaire (mais ce n'est pas au 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 a 2 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és nœuds internes.
Vocabulaire :
La profondeur d'un nœud dans un arbre est le nombre de nœuds du chemin qui va de la racine à ce nœud. On prendra comme convention que la racine d'un arbre est à une profondeur de 1. la profondeur d'un noeud est égale à la profondeur de son parent plus 1.
La hauteur d'un arbre est la profondeur maximale des nœuds de l'arbre. En considérant que la profondeur de la racine est 1 alors l'arbre vide a une hauteur de 0, et l'arbre réduit à sa 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 le nœud 2).
Remarque : Certains auteurs utilisent une autre convention pour calculer la hauteur d'un noeud : la racine a pour hauteur 0 et non 1 et donc l'arbre nul (NIL) a alors pour hauteur -1. Les 2 définitions sont valables, il faut donc préciser si on choisit que la profondeur de la racine est 1 ou 0.
Remarques mathématiques :
Intuitivement, le nombre maximal de feuilles est de $2^{h-1}$. On peut le démontrer proprement par récurrence.
Soit h un entier naturel strictement positif, montrons par récurrence, qu'un arbre binaire de hauteur h > 0 a au plus $2^{h-1}$ feuilles.
Si h = 1 alors l'arbre binaire a une seule feuille (donc $2^0$) qui est la racine, donc la récurrence est initialisée.
Soit un entier naturel h > 0, supposons qu'un arbre binaire de taille h ait au plus $2^{h-1}$ feuilles et montrons alors qu'un arbre binaire de hauteur h + 1 a au plus $2^h$ feuilles.
Par définition, un arbre binaire de hauteur de hauteur h + 1 est formé d'un arbre gauche de hauteur h qui a donc, par hypothèse de récurrence, au plus $2^{h-1}$ feuilles et d'un arbre droit de hauteur h qui a donc au plus $2^{h-1}$ feuilles. Au total un arbre de hauteur h + 1 a donc au plus $2\times2^{h-1}$ soit $2^h$ feuilles.
Par principe de récurrence, un arbre binaire de hauteur h > 0 a donc au plus $2^{h-1}$ feuilles.
Tout comme dans le cas précédent, intuitivement, on constate qu'un arbre binaire de hauteur h a au plus $2^h-1$ nœuds. On peut démontrer ce résultat par récurrence.
Soit h un entier naturel strictement positif, montrons par récurrence, qu'un arbre binaire de hauteur h a au plus $2^h-1$ nœuds.
Si h=1 alors l'arbre binaire est réduit à sa racine, il a donc 1 nœud et $1=2^1-1$ donc la récurrence est initialisée.
Soit h un entier naturel, supposons qu'un arbre binaire de hauteur h ait au plus $2^h-1$ nœuds et montrons alors qu'un arbre binaire de hauteur h + 1 a au plus $2^{h+1}-1$ nœuds.
Par définition, un arbre binaire de hauteur de hauteur h + 1 est formé d'un arbre gauche de hauteur h qui a donc, par hypothèse de récurrence, au plus $2^h-1$ nœuds, d'un arbre droit de hauteur h qui a donc au plus $2^h-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\times (2^h-1)+1=2^{h+1}-2+1=2^{h+1}-1$ nœuds.
Par principe de récurrence, un arbre binaire de hauteur h > 0 a donc bien au plus $2^h-1$ nœuds.
D'après la question précédente, un arbre de hauteur h a au plus $2^h-1$ nœuds. Soit $n$ le nombre de nœuds d'un arbre. On a donc $n\leq 2^h-1$ donc $n+1\leq 2^h$ donc $log_2(n+1)\leq h$. La hauteur minimale d'un arbre de $n$ nœuds est donc de $log_2(n+1)$.
Définitions :
Un arbre binaire filiforme ou dégénéré est un arbre dans lequel tous les nœuds internes n’ont qu’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 exactement deux fils. (Autrement dit, un arbre binaire localement complet est un arbre dont chaque nœud possède zéro ou 2 fils. L’arbre vide n’est pas localement complet.)
Un arbre binaire complet est un arbre binaire localement complet dans lequel toutes les feuilles sont à la même profondeur. (Il s’agit d’un arbre dont tous les niveaux sont remplis.)
Nativement Python ne propose pas l'implémentation des arbres binaires, nous allons donc implémenter des arbres binaires en Python en utilisant la programmation orientée objet en TP.
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-arbre gauche et le sous-arbre droit.
On peut écrire cet algorithme en pseudo-langage :
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 exemple hauteur(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".
Tout comme pour le calcul de la hauteur, pour calculer la taille d'un arbre binaire, on se base sur un 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-arbre droit.
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 A est une feuille, retourne 1".
Pour toute cette partie, on utilisera l'arbre binaire suivant :
À partir de ce contour, on définit trois parcours des sommets de l’arbre. Ces trois parcours s’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èrise ces 3 différents parcours.
On notera un arbre (r, g, d) (avec r = racine, g = sous-arbre gauche et d = sous-arbre droit).
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.
Ce qui revient à dire qu'on affiche donc la valeur de chaque nœud la première fois qu’on le rencontre lors du parcours de gauche à droite.
Ce qui donne ici : r, a, c, h, d, i, j, l, b, e, k, f.
Dans le parcours postfixe (on dit aussi suffixe), on commence 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 de chacun de ses fils.
Ce qui donne ici : h, c, i, l, j, d, a, k, e, f, b, r.
Dans le parcours infixe, on commence par parcourir le sous-arbre g, puis on liste r, et on termine par le sous-arbre d.
Ce qui revient à dire qu'on affiche la valeur de chaque nœud ayant un fils gauche la seconde fois qu’on le voit et de chaque nœud sans fils gauche la première fois qu’on le voit.
Ce qui donne ici : c, h, a, i, d, l, j, r, k, e, b, f.
On reprend les 3 algorithmes précédents en utilisant leur structure récursive pour les écrire facilement 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)
}
}
Nous allons aborder un type de parcours un peu plus compliqué à programmer alors que c'est naturellement 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 passe ensuite 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 noeud jusqu'à ce qu'on s'intéresse au fils du noeud.
L’algorithme de parcours largeur utilise une File pour mémoriser les descendants directs de chaque noeud rencontré. Ce qui permet à la hauteur suivante de les récupérer dans l'ordre de rencontre.
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 de sa racine et on place dans la file chacun de ses deux sous-arbres s'ils ne sont pas vides.
fonction PARCOURS-LARGEUR(T : arbre) {
f = file()
f.enfiler(A) #on place A dans la file
tant que f non vide :{
x ← defiler(f)
affiche x.racine #on affiche la racine
si x.gauche ≠ NIL : { #si fils gauche non vide on l'enfile dans f
enfiler(x.gauche)}
si x.droit ≠ 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
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 fiche 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 fiche 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 fiche 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 fiche droit donc on n'enfile rien
f est vide
Un arbre binaire de recherche est un arbre binaire formé de noeuds dont les valeurs 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 ⩽ x.valeur
Si y est un noeud du sous-arbre droit de x, il faut alors que x.valeur ⩽ 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 descendre sur le fils gauche (resp. sur le fils droit) autant que possible. Le dernier noeud visité, qui n’a pas de fils gauche (resp. droit), porte la valeur la plus petite (resp. la plus grande) de l’arbre.
Le parcours infixe trie la liste. Les éléments de gauche sont en effet, par construction, plus petits qu’un noeud et sont affichés avant le nœud dans l’ordre infixe et les éléments de droite qui 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.
Nous allons maintenant étudier un algorithme permettant de rechercher une valeur k dans un arbre binaire de recherche. Si k est bien présent dans l'arbre binaire de recherche, l'algorithme renvoie vrai, dans le cas contraire, il renvoie faux.
Un arbre binaire de recherche est fait pour faciliter la recherche d’informations.
La recherche d’un noeud particulier de l’arbre peut être définie simplement de manière récursive :
Soit un sous-arbre de racine $n_i$,
noeud recherché.
termine.
si la valeur recherchée est plus grande que celle de la racine alors on explore le sous-arbre de droite c’est à dire que l’on remplace $n_i$ par son noeud fils de droite et que l’on relance la procé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 $n_i$, on remplace $n_i$ 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)}
}
Cet algorithme de recherche d'une valeur dans un arbre binaire de recherche ressemble beaucoup à la recherche dichotomique vue en première dans le cas où l'arbre binaire de recherche traité est équilibré.
La complexité en temps dans le pire des cas de l'algorithme de recherche d'une valeur dans un arbre binaire de recherche équilibré est donc $O(log_2(n))$ Dans le cas où l'arbre est filiforme, la complexité est $O(n)$. Rappelons qu'un algorithme en $O(log_2(n))$ est plus "efficace" qu'un algorithme en $O(n)$.