> Quelques cours > Algorithmique et Analyse > 5. Arbres

Retour sur la page précédente

5. Arbres

5.1. Origine, notions intuitives, exemples

Arbre généalogique (ensemble des ascendants), lignée (ensemble des descendants). Cette structure ramifiée, calquée sur l'arbre de lignage, ne doit pas, à la différence d'arbres généalogiques réels, présenter d'interconnexions (mariages entre cousins, par exemple)

Quelques descendants mâles de Noé (Genèse 10)

5.2. Vocabulaire et définitions

Vocabulaire arboricole : arbre, racine, nœud, feuille, branche, hauteur ;

Vocabulaire généalogique : père, fils, frère ...

Remarque : les représentations graphiques, en contradiction avec le vocabulaire, placent presque toujours la racine en haut !

• feuille : nœud sans fils (par opposition à nœud interne) ;
• taille : nombre de nœuds ;
• hauteur (profondeur, niveau) d'un nœud : hauteur(arbre vide) = 0, hauteur(nœud) = 1 + hauteur(père(nœud)). hauteur d'un arbre : plus grande hauteur d'une feuille ;
• longueur d'un cheminement : somme des hauteurs de tous les nœuds
  (le cheminement externe ne prend en compte que les feuilles, le cheminement interne ne prend en compte que les nœuds internes) ;
• arbre dégénéré ;
• arbre complet : chaque niveau est complètement rempli (le nombre de fils de chaque nœud est donc nécessairement borné) ;
• arbre parfait : tous les niveaux, sauf le dernier, sont remplis. Sur le niveau non rempli, ne sont utilisés que les nœuds les plus à gauche ;
• arbre binaire : chaque nœud a, au plus, deux fils : fils gauche, fils droit ;
• arbre binaire de recherche = relation d'ordre clé(fils gauche) < clé(nœud) < clé(fils droit) ;
• arbre partiellement ordonné (A O V) = relation d'ordre plus faible max(clé(fils gauche), clé(fils droit)) clé(nœud)
• arbre équilibré : toutes les feuilles sont "à peu près" à la même profondeur, arbre AVL (Adelson-Velskii et Landis)
• arbres dont toutes les feuilles sont au même niveau (nombre de fils variable) : arbre 2-3-4, B-arbres (très utilisés dans la gestion des systèmes de fichiers) : chaque nœud possède un grand nombre de fils, toutes les feuilles sont à la même profondeur.

5.3. Représentation des arbres

Structure de données pour un nœud :

On remarquera que la structure ty_noeud dépend de la nature de l'arbre : soit le nombre de fils de chaque nœud est borné par une valeur simple (2 pour les nœuds de l'arbre généalogique) soit le nombre de fils n'est pas limité (nombre de descendants dans l'arbre de "lignage") ; dans le premier cas la liste des fils de chaque nœud peut être placé dans un tableau, dans le second cas il est nécessaire d'utiliser une liste.

Stockage implicite dans un tableau (particulièrement adapté au cas d'arbres parfaits ou complets) : si chaque nœud a m fils au plus, la première rangée de l'arbre contient 1 nœud, la deuxième m, la troisième m², etc. Si on range les nœuds possibles contiguëment dans un tableau, le kième nœud (numéroté de gauche à droite) du pième niveau est rangé dans l'élément de tableau de rang (mp-1- 1)/(m-1)+k. La position des fils d'un nœud est aisément calculée, on peut donc se contenter de stocker les clés (ou des pointeurs sur les clés), sans avoir à utiliser de pointeurs sur les fils.

5.4. Arbre binaire de recherche

5.4.1. Définitions

C'est un arbre binaire (chaque nœud a 2 fils au plus) ; pour chaque nœud qui n'est pas une feuille, les clés1 satisfont à une relation d'ordre de la forme :

clés de sous-arbre fils gauche < clé (nœud) < clés de sous-arbre fils droit

Ici encore, il faut choisir "<" ou "". Ce choix n'est pas arbitraire, il est lié au but de ce traitement arboricole2 : s'il est possible que le traitement amène à rencontrer plusieurs fois une même valeur de clé, doit-on stocker dans l'arbre un seul nœud comportant cette valeur de clé ou autant de nœuds que de fois où cette valeur de clé a été rencontrée ? De même, quels traitements envisage-t-on d'appliquer à l'arbre (ré-équilibrage, par exemple) ; quelle méthode utilisera-t-on pour parcourir l'arbre (en cas de clés de valeurs égales, laquelle souhaite-t-on récupérer en premier : la première introduite ou la dernière)...

Pour ce cours, nous supposerons que les clés stockées dans l'arbre sont uniques. Nous choisirons :

clés du sous-arbre fils gauche < clé(nœud) < clés du sous-arbre fils droit

Structure de données :

Nous introduisons aussi un type tu_côté qui peut permettre, lorsque cela est plus commode, une notation alternative à f_gauche ou f_droit : cette notation serait fils (gauche) ou fils (droite) ou même fils (côté) si côté est une variable de type ty_côté. On se permet ainsi d'écrire fils (côté, p_noeud) pour désigner un des deux fils du nœud pointé par p_noeud.

5.4.2. Exemple de construction d'un arbre binaire de recherche

Arbre associé au texte "Longtemps je me suis couché de bonne heure"

Les clés contiennent les mots du texte, les nœuds sont placés au fur et à mesure de leur introduction de telle sorte que, à chaque étape, soit vérifiée la relation clé (f_gauche) < clé (nœud) < clé (f_droit), les comparaisons sont faites au sens de l'ordre est l'ordre lexicographique. Les numéros placés à gauche des nœuds rappellent l'ordre d'introduction des nœuds.

5.5. Opérations élémentaires sur les arbres binaires de recherche

Par analogie avec le traitement des listes, nous allons considérer trois fonctions de base : trouver_noeud, ajouter_noeud et ôter_noeud. Nous commençons par donner les spécifications externes de ces procédures :

5.5.1. Première fonction : rechercher la position d'un noeud dont on connait la "clé"

Etape 0 : spécifications du problème et du comportement de la procédure

Cette procédure doit gérer le cas où l'arbre est vide. Dans tous les cas, les valeurs produites doivent être cohérentes : p = NIL si x n'est pas la clé d'un nœud de l'arbre, p_père = NIL si le nœud recherché est la racine.

Etape 1 : spécification de l'en-tête de la fonction

Etape 2 : le cœur de la recherche

Il faut aussi mettre à jour p_père et côté.

Etape 3 : procédure définitive

5.5.2. Seconde fonction : ajouter un noeud

(comme pour les listes, on se limite à la réalisation des connexions et on ne se préoccupe ni de l'allocation des nœuds ni de modification du champ "clé").

Spécifications du problème et du comportement de la procédure

On veut ajouter un nœud pointé par p_nouveau dans un arbre dont la racine est pointée par p_root ; le nœud sera une feuille, placé comme fils (du côté côté) du nœud pointé par p_père ; cette procédure doit gérer le cas où l'arbre est vide.

On suppose que les données ne sont pas incohérentes c.-à-d. :

• p_nouveau NIL
• fils (côté, p_père) = NIL

N.B. On aurait pu imaginer une fonction sensiblement différente : insérer_noeud qui gérerait le cas où fils(côté, p_père) NIL

5.5.3. Troisième fonction : supprimer un noeud

Spécifications du problème et du comportement de la procédure

On veut retirer un nœud placé comme un fils (du côté côté) du nœud pointé par p_père, dans l'arbe dont la racine est pointée par p_root. En sortie, le pointeur p_retiré devra contenir l'adresse du nœud retiré ; les sous-arbres fils du nœud devront être raccrochés convenablement à l'arbre. Cette procédure doit gérer le cas oú le nœud retiré est la racine (et même le cas où l'abre est vide). On suppose que les données ne sont pas incohérentes c.-à-d. que l'on a pas : p_root = NIL en mê me temps que p_père NIL

Il y a une difficulté, bien visible sur la partie basse de la figure ci-dessous : si le nœud à supprimer a 2 fils, comment les accrocher au père du nœud ? Pour la résoudre, on peut remarquer que les clés de tous les nœuds du sous-arbre fils-gauche sont inférieures à la clé de la racine du sous-arbre et que celles du sous-arbre fils droit sont supérieures à cette racine...

Tentative de suppression d'un nœud : on voit que l'on peut aisément supprimer le nœud n°2 mais qu'on ne peut supprimer le nœud n°5 sans modifier l'arbre de façon importante.

5.5.4. fonctions supplémentaires

On peut imaginer quantité de fonctions supplémentaires pour la gestion d'un arbre binaire : par exemple, déterminer la hauteur, la taille, le cheminement, le nœud de valeur de clé maximale/minimale ; déplacer un sous-arbre, équilibrer un arbre (diminuer sa hauteur).

5.6. Traversée de l'arbre

Parcourir tous les nœuds d'un arbre selon un ordre strict pour appliquer à chaque nœud le même traitement. L'exemple suivant illustre quelques modes de parcours d'un arbre binaire :

parcours infixe (notation algébrique) : a - b (c/d + e/f) parcours préfixe (LISP) : ( - a (* b (+ (/ c d) (/ e f)))) parcours postfixe (Forth, Postscript) : a b c d / ef / + * -s Différents mode de parcours d'un arbre binaire : arbre associé à l'expression a - b (c/d + e/f) (Attention cet arbre binaire n'est pas un arbre binaire de recherche)

Nous nous intéresserons au parcours "infixe" d'un arbre binaire : on applique, pour chaque nœud, "parcourir le sous-arbre fils_gauche, traiter le nœud, parcourir le sous-arbre fils_droit".

Voici le prototype de la procédure parcourir :

On voit qu'il y a appel à la procédure parcourir depuis l'intérieur de cette procédure : on est en présence d'une récursion.

Retour sur la page précédente