Université Bordeaux 1

Licence Semestre 3  - Algorithmes et structures de données 1

Dernière mise à jour effectuée le 23 Juin 2014


Arbres


  1. Arbre et arborescence
  2. Définition 4.1. Un arbre est un graphe connexe sans cycle.
    Un sous arbre est un sous graphe d'un arbre.
    Propriété 4.2. Si un arbre a n sommets alors il a n-1 arêtes.
    Idée de la démonstration
    Ceci s'appuie sur les deux propriétés suivantes des graphes connexes.
    • Tout graphe connexe ayant n sommets a au moins n-1 arêtes.
    • Tout graphe connexe ayant n sommet et au moins un cycle a au minimum n arêtes.
    La taille d'un arbre est le nombre de sommets de l'arbre.
    Propriété 4.3. Entre deux sommets quelconques d'un arbre, il existe une unique chaîne les reliant.
    Idée de la démonstration
    Pour deux sommets quelconques:
    • Il ne peut exister deux chaines différentes les reliant sinon il y aurait un cycle dans l'arbre.
    • Il existe au moins une chaine puisque un arbre est un graphe connexe.
    Définition 4.4. Une arborescence est définie à partir d'un arbre en choisissant un sommet appelé racine et en orientant les arêtes de sorte qu'il existe un chemin de la racine vers tous les autres sommets.
    On appele fils d'un sommet s tout sommet s' tel que (s,s') est une arête de l'arbre.
    On notera qu'une arborescence est un exemple d'ensemble partiellement ordonné (relation d'ordre "fils de").
    On appelle feuille de l'arbre un sommet qui n'a pas de successeur . Tout autre sommet est appelé sommet interne.
    On appelle hauteur d'un sommet de l'arbre la longueur du chemin de la racine à ce sommet.
    Définition 4.5. Un arbre planaire est défini en ordonnant les arêtes sortantes de chaque sommet.
    On notera qu'un arbre planaire est un exemple d'ensemble totalement ordonné (relation "est fils ou est frère à droite").
    Définition 4.6. Un arbre binaire est un arbre planaire dont chaque sommet a au plus deux fils.
    Définition 4.7. Un arbre binaire complet est un arbre binaire dont chaque sommet interne a exactement deux fils.
    Propriété 4.8. Tout sommet x d'un arbre binaire vérifie l'une des deux propriétés suivantes:
    • x est une feuille,
    • x a un sous arbre binaire dit gauche de racine G(x) et un sous arbre binaire droit de racine D(x).
    Définition 4.9. Un arbre binaire parfait est un arbre binaire complet dans lequel toutes les feuilles sont à la même hauteur dans l'arbre.
    Théorème 4.10Un arbre binaire de taille n a une hauteur est moyenne log2(n).
    Théorème 4.11 Il existe une bijection qui transforme un arbre planaire ayant n sommet en un arbre binaire complet ayant 2n+1 sommets.

  3. Arbres binaires
  4. Du fait de ce théorème, on ne considère dans un premier temps que le type arbre binaire que l'on nommera arbreBinaire. Chaque sommet permet d'accéder à deux sommets : le fils gauche et le fils droit. Ce type sera nommé sommet. Chaque sommet permet également d'accéder à l'objet qu'il stocke. Un arbre binaire peut être vu comme un curseur indiquant le sommet racine. De la même manière un sommet est un curseur. On a donc
    arbreBinaire=curseur;
    sommet=curseur;
    
    Le type sommet présente les primitives suivantes :

    Détection de feuille

    fonction estFeuille(val S:sommet):booléen;
      début
        retourner(filsGauche(S)==NIL et filsDroit(S)==NIL)
      fin
    

    Construction d'un arbre binaire à partir d'un tableau d'entiers

    On choisit de remplir l'arbre de haut en bas et de gauche à droite (parcours hiérarchique).
    fonction remplirTableauArbre(ref T:tableau[1..N] d'entier):
                    arbreBinaire d'entier;
      var A:arbreBinaire d'entier;
      var F: file de sommet;
      var s:sommet;
      var i:entier;
      début 
        créerFile(F);
        A=créerArbreBinaire(T[1]);
        enfiler(F,A);
        tmp=2;
        tantque 2*tmp-1<=N faire
          pour i=tmp à 2*tmp-1 par pas de 2 faire
            s=valeur(F);
            defiler(F);
            ajouterFilsGauche(s,T[i]);
            enfiler(filsGauche(s));
            ajouterFilsDroit(s,T[i+1]);
            enfiler(filsDroit(s));
          finpour;
          tmp=tmp*2;
        fintantque
        pour i=tmp à N par pas de 2 faire
          s=valeur(F);
          defiler(F);
          ajouterFilsGauche(s,T[i]);
          ajouterFilsDroit(s,T[i+1]);
        finpour;
        si N mod 2 !=0 alors
          ajouterFilsGauche(valeur(F),T[N])
        finsi
        detruireFile(F);
        retourner(A);
      fin
    

  5. Parcours d'un arbre binaire
  6. Le parcours d'un arbre binaire consiste à donner une liste de sommets dans l'arbre. Le prototype d'algorithme ci-dessous permet d'effectuer les parcours suivant les algorithmes associés aux traitements à partir d'un sommet de l'arbre.
    fonction parcoursArbreBinaire(val A:arbreBinaire d'objet):vide;
    //    Déclarations locales
        début
    //    traitement1; 
          si estFeuille(A)alors
    //      traitement2 
          sinon
    //      traitement3;
             si filsGauche(A)!=NIL alors
    //        traitement4;
              parcoursArbreBinaire(filsGauche(A));
    //        traitement5;
            finsi
    //      traitement6;
            si filsDroit(A)!=NIL alors
    //        traitement7
              parcoursArbreBinaire(filsDroit(A));
    //        traitement8;
            finsi
    //      traitement9;
          finsi
    //    traitement1O;
       fin
    
    Complexité: si le traitementi a pour complexité ci(n), soit
    .
    . La complexité intrinsèque de l'algorithme est O(n c(n)).

    On distingue quatre parcours qui conditionnent les algorithmes sur les arbres binaires. Le parcours hiérarchique (voir paragraphe précédent) ainsi que les suivants :
    Exemple
    • Parcours préfixe :7 5 9 8 4 6 2
    • Parcours infixe : 9 5 8 7 6 2 4
    • Parcours suffixe : 9 8 5 2 6 4 7

    Affichage des valeurs des sommets pour un parcours donné

    Soit un arbre étiquetté par des entiers. On considère que l'on dispose de la fonction suivante qui affiche un entier n sur le terminal
    fonction afficher(val n:entier):vide;

    Lister les étiquettes d'un arbre dans un tableau

    fonction arbre2Tableau(val A:arbreBinaire d'entier;ref T:tableau[1..N] d'entier;ref i:entier):vide;
        début
          i=i+1;
          T[i]=valeur(A);
          si !estFeuille(A)alors
             si filsGauche(A)!=NIL alors
              arbre2Tableau(filsGauche(A),T,i);
             finsi
             si filsDroit(A)!=NIL alors
              arbre2Tableau(filsDroit(A),T,i);
             finsi
          finsi
       fin
    

    Hauteur d'un arbre binaire

    fonction hauteurArbreBinaire(val s:sommet):entier
      début
        si estFeuille(s)alors
          retourner(0)
        sinon
          var tmp1,tmp2:entier;
          tmp1=0;
          tmp2=0;
          si filsGauche(s)!=NIL alors
            tmp1= hauteurArbreBinaire(filsGauche(s));
          finsi
          si filsDroit(s)!=NIL alors
            tmp2=hauteurArbreBinaire(filsDroit(s));
          finsi
          retourner(1+max(tmp1,tmp2));
        finsi
     fin
    
    Autre version
    fonction hauteurArbreBinaireSimp(val s:sommet):entier
      début
        si s==NILalors
          retourner(-1)
        sinon
          retourner(1+max(hauteurArbreBinaireSimp(filsGauche(s)),hauteurArbreBinaireSimp(filsDroit(s))));
       finsi
     fin
    
    Remarque : La fonction hauteurArbreSimp (même si elle est plus courte) a une complexité plus grande que la fonction hauteurArbreBinaire notamment en nombre d'appel récursif. Elle est moins performante.

    Taille d'un sous-arbre d'un arbre binaire complet.

    fonction tailleArbreBinaire(val A: arbreBinaire):entier;
      var tmp:entier;
      début
        si estFeuille(A) alors
          retourner(1)
        sinon
          retourner(1+tailleArbreBinaire(filsGauche(A))
                     +tailleArbreBinaire(filsDroit(A))
        finsi
      fin
    

  7. Implémentation du type arbreBinaire
  8. L'implémentation se fait par allocation dynamique. On définit
    cellule=structure 
             info:objet;
             gauche:sommet;
             droit:sommet;
             pere:sommet;
           finstructure
    sommet=^cellule;
    
    On a alors

  9. Retour sur les arbres planaires
  10. On peut définir un type abstrait sommetArbrePlanaire par les primitives suivantes: Un arbre planaire est de type ^sommetArbrePlanaire. C'est un curseur.

  11. Parcours d'un arbre planaire
  12. Le parcours d'un arbre planaire consiste à donner une liste de tous les sommets. Le prototype d'algorithme ci-dessous permet d'effectuer les parcours suivant les algorithmes associés aux traitements à partir d'un sommet de l'arbre planaire.
    fonction parcoursArbrePlanaire(val A:sommetArbrePlanaire):vide;
    //  Déclarations locales
       var f: sommetArbrePlanaire;
       début
    //    traitement1;
          f= premierFils(A);
          tant que f!=NIL faire
    //        traitement2;
              parcoursArbrePlanaire(f);
    //        traitement3;
              f=frere(f);
    //        traitement4
          fintantque
    //    traitement5
       fin
    
    On distingue trois parcours qui conditionnent les algorithmes sur les arbres planaires. Le parcours hiérarchique qui s'effectue grâce à une file ainsi que
    Exemple
    • Parcours préfixe : 0 5 8 4 3 10 6 1 7 9
    • Parcours suffixe : 8 4 5 3 1 6 7 9 10 0
    • Parcours hiérarchique : 0 5 3 10 8 4 6 7 9 1

  13. Implémentation du type arbrePlanaire
  14. Implémentation dans le type arbreBinaire

    L'implémentation dans le type arbreBinaire découle du théorème 4.11. On a alors
    arbrePlanaire=arbreBinaire. Pour un noeud donné :
    fonction pereArbrePlanaire(val S:sommetArbrePlanaire):sommetArbrePlanaire;
      var T: sommetArbrePlanaire;
      début
        T=filsGauche(pere(S));
        tant que T!=S faire
          S=pere(S)
          T=filsGauche(pere(S));
        fintantque
        retourner(pere(S))
      fin
    
    En utilisant le théorème 4.10, cette dernière primitive à une complexité moyenne O(log2n).

    Implémentation par allocation dynamique

    Cette implémentation permet de diminuer le temps d'accès au père.
    celluleAP=structure
             info:objet;
             premierFils:sommet;
    	 frère:sommet;
             père:sommet;
           finstructure
    
    Dans cette implémentation, on initialise parfois le champ frere du dernier frère à l'adresse du frère ainé. On peut vérifier aisément que les primitives sont toutes réalisables en O(1). L'espace mémoire est le même que celui occupé par une implémentation dans le type arbreBinaire.