Kha-tastrophe.net

Le site kha-tastrophique de Kha

> Cours > Informatique> Algorithmique et Analyse > Arbres

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)

Arbre : quelques descendants mâles de Noé

Catalogue arborescent

Arbre : catalogue arborescent

  • les feuilles sont des fichiers (ou des "directories" vides)
  • les nœuds internes sont des "directories"

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 !

Un arbre est un ensemble fini T de 1 ou plusieurs nœuds tel que :

  • il existe un nœud particulier appelé "racine de T"
  • les autres nœuds sont répartis en m Symbole : supérieur et égal O ensembles disjoints T1, T2 ... Tm (appelés sous-arbre de la racine) qui sont eux-mêmes des arbres (définition récursive)

N.B. On peut étendre cette définition en admettant le concept d'arbre "vide" : il n'y a même pas de nœud racine.

  • 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)) Symbole : inférieur et égal 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 :

TYPE
    ty_noeud = agrégat_de
        clé : ty_clé;         /* au moins une */
        fils : liste de pointeurs sur ty_noeud;
        autres : "autres informations"          /* éventuellement */
    fin_agrégat ty_noeud;

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 , 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

1. Il faut préciser ce qu'on entend par "clé". On pense souvent à un simple champ d'agrégat ("Nom d'étudiant" par exemple) qui peut, en cas de besoin, être complété par des clés "secondaires" (prénom, date de naissance...) ; nous considérerons que c'est l'exemple de ces informations qui constitue la clé.

fermer cette précision

Ici encore, il faut choisir "<" ou "Symbole : inférieur et égal". 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)...

2. Rappelons une fois encore que les structures étudiées dans ce cours n'ont pas d'existence intrinsèque, elles ne sont que des exemples ; leurs réalisations réelles dépendent des problèmes particuliers traités.

fermer cette précision

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 :

TYPE
    ty_noeud = agrégat_de
        clé : ty_clé;
        f_gauche, f_droit : pointeurs sur ty_noeud;
        autres : "autres informations"
    fin_agrégat ty_noeud;
    
    ty_côté = (gauche, droite) ;

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"

Exemple de construction d'un arbre binaire de recherche

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

/* on suppose connaître :
    un arbre binaire de recherche, désigné par un pointeur sur la racine,
    on cherche la place, dans cet arbre, de "x"  de type ty_clé, c.-à-d.
    - soit
        la valeur du pointeur "p" tel que clé (p) = x
    - soit
        les valeurs du pointeur "p_père" et de "côté" telles que fils(côté, p_père) = NIL
        et que clé (p_père) < x si côté = droite ou clé (p_père) < x si côté = gauche
*/

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

procédure trouver_noeud (
    x : ty_clé, Entrée;
    p_root : pointeur sur ty_noeud, Entrée; /* pointe sur la racine */
    p, p_père : pointeurs sur ty_noeud, Sortie; /* pointeurs sur l'élément et son père */
    côté : ty_côté, Sortie) /* le fils intéressant de ty_noeud(p_père) */

Etape 2 : le cœur de la recherche

/* on suppose que : le pointeur courant "p" pointe sur un noeud */
si x Symbole : différent clé(p) alors
    si x < clé (p) alors      /* on doit chercher dans le sous-arbre à gauche */
        p Symbole : affectation f_gauche (p)
    sinon       /* on doit chercher dans le sous-arbre à droite */
        p Symbole : affectation f_droit (p)
    fin_si
sinon
    /* on a trouvé ... */
fin_si

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

Etape 3 : procédure définitive

procédure trouver_noeud (
    x : ty_clé, Entrée;
    p_root : pointeur sur ty_noeud, Entrée; /* pointe sur la racine */
    p, p_père : pointeurs sur ty_noeud, Sortie; /* pointeurs sur l'élément et son père */
    côté : ty_côté, Sortie) /* le fils intéressant de ty_noeud(p_père) */
    x Symbole : affectation root;
    p_père Symbole : affectation NIL;
    répéter
        tant_que p Symbole : différent NIL
        jusqu'à clé(p) = x
            p_père Symbole : affectation p;
            si x < clé (p) alors      /* on doit chercher dans le sous-arbre à gauche */
                p Symbole : affectation f_gauche (p)
                côté Symbole : affectation gauche
            sinon       /* on doit chercher dans le sous-arbre à droite */
                p Symbole : affectation f_droit (p)
                côté Symbole : affectation droite
            fin_si
    fin_répéter
fin_procédure trouver_noeud

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 Symbole : différent NIL
  • fils (côté, p_père) = NIL
procédure ajouter_noeud ( /* ne réalise que les connexions ! */
    p_nouveau : pointeur sur ty_noeud, Entrée; /* sur nouveau noeud */
    p_père : pointeur sur ty_noeud, Entrée; /* pointeur sur futur père du nouveau noeud */
    côté : ty_côté, Entrée; /* où placer p_nouveau */
    p_root : pointeur sur ty_noeud, Entrée/Sortie; /* pointe sur la racine */
/* on suppose que fils (côté, p_père) = NIL */
    f_gauche(p_nouveau) Symbole : affectation NIL        seulement si on n'ajoute qu'un nœud feuille (pas un sous-arbre)
    f_droit(p_nouveau) Symbole : affectation NIL         idem ...
    si p_père Symbole : différent NIL alors
        si côté = droite alors
            f_droit (p_père) Symbole : affectation p_nouveau
        sinon
            f_gauche (p_père) Symbole : affectation p_nouveau
        fin_si
    sinon
        p_root Symbole : affectation p_nouveau
    fin_si

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) Symbole : différent 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 Symbole : différent 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

Schéma illustrant des tentatives 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 :

Différents mode de parcours d'un arbre binaire

Schéma illustrant la traversée de l'arbre

arbre associé à l'expression a - b (c/d + e/f)

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

(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 :

procédure parcourir_rameau (p_rameau : pointeur sur ty_noeud /* la racine */)
    /* procédure récursive, parcours "infixe" */
    p Symbole : affectation p_rameau
    si f_gauche(p) Symbole : différent NIL alors
        parcourir_rameau (f_gauche(p))
    fin_si
    traiter ty_noeud(p)
    si f_droit(p) Symbole : différent NIL alors
        parcourir_rameau (f_droit(p))
    fin_si
fin_procédure parcourir_rameau

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.