table des matières

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.

  2. Arbres binaires

    3. 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

  3. Parcours d'un arbre binaire

    4. 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

  4. Implémentation du type arbreBinaire

    5. 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

  5. Retour sur les arbres planaires

    6. On peut définir un type abstrait sommetArbrePlanaire par les primitives suivantes: Un arbre planaire est de type ^sommetArbrePlanaire. C'est un curseur.

  6. Parcours d'un arbre planaire

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

  7. Implémentation du type arbrePlanaire

    8. 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.