D’après le cours de Denis Gautier - CITE SCOLAIRE J.H. FABRE – CARPENTRAS

1. Introduction

Les structures de type listes chaînées, piles et files vues précédemment sont efficaces lorsqu’il s’agit de structurer des données qui devront être parcourue séquentiellement.

Quand il s’agit d’accéder à une donnée qui est à une position quelconque, ces structures ne sont plus adaptées puisqu’il faut parcourir toutes les données précédentes avant d’atteindre la donnée recherchée. Le temps moyen d’accès à une donnée est en général proportionnel au nombre de données à parcourir.

Les structures arborescentes sont une autre famille de données chaînées qui réduisent le temps d’accès aux données en les organisant différemment.

lumni

2. Structures arborescentes

Ces structures sont largement utilisées en informatique, pour l’arborescence des fichiers par exemple. Ci-dessous l’arborescence du système de fichier Unix que l’on retrouve sur les MAC, sur Linux, Android, etc..

fichiers

3. Les arbres binaires

  • Un arbre binaire est une des formes existantes de structures arborescentes.

  • Dans ce cas particulier, chaque position appelée nœud ouvre sur deux branches appelées sous-arbre de gauche et sous arbre de droite.

  • Chaque nœud peut rejoindre un autre nœud qui continuera lui même avec deux branches.

  • Lorsqu’un nœud a ses deux branches vides, on l’appelle une feuille
arbre binaire

4. Définitions

Vocabulaire

  • Racine, nœud, branche, feuille :

    • un arbre est un ensemble organisé de nœuds dans lequel chaque nœud a un père, sauf un nœud que l’on appelle la racine.

    • Si le nœud n’a pas de fils, on dit que c’est une feuille.

    • Les nœuds sont reliés par des branches.
Mesures

  • Taille d’un arbre : la taille d’un arbre est égale au nombre de nœuds de l’arbre. Ci-dessus l’arbre est de taille 4.

  • Hauteur d’un nœud : la hauteur (ou profondeur ou niveau ) d’un nœud est égale au nombre d’arêtes qu’il faut parcourir à partir de la racine pour aller jusqu’au nœud en question.

  • Hauteur d’un arbre :

    • un arbre est vide lorsqu’il ne contient aucun nœud.

    • Un arbre vide a une hauteur 0.

    • Un arbre non vide a une hauteur égale au plus grand nombre de nœuds rencontrés en descendant de la racine jusqu’à une feuille. Ci-dessus nous avons un arbre binaire de hauteur 3.

Si \( N \) désigne la taille d’un arbre ( son nombre de nœuds) et \(h\) sa hauteur, pour un arbre binaire, on a l’inégalité suivante :

\(h ≤ N ≤ 2^{h} -1 \)

Ci-dessous, un arbre binaire parfait où toutes les feuilles sont à la même profondeur : \( N = 2^{h} -1 \) ici \( 7 = 2^3 -1 \)

equilibre
Cas particulier

  • Les peignes : un arbre dont le sous arbre non vide est toujours du même côté est appelé un peigne.

5. Intéret d’un arbre

L’intérêt d’un arbre est de stocker de l’information. Ci-dessous l’arbre binaire du codage de la compression de Huffman où chaque feuille est étiquetée et chaque branche pondérée:

huffman

Codage des caractères :

  • R = 00

  • P = 01

  • E = 1

5.1. Travail à faire : Décoder le mot codé

Le mot codé est : 011001

  • PEER
  • PERE
  • REPE
  • ERPE

5.2. Travail à faire : Construction d’un arbre et mesures

On considère le type abstrait Arbre qui possède les opérations suivantes :

  • creer_arbre(v,g,d) : cette opération renvoie un objet Arbre, dont la valeur du nœud est v, la valeur du fils gauche g et celle du fils droit est d.

  • creer_arbre_feuille(v) : cette opération renvoie un objet Arbre, dont la valeur du nœud est v et le nœud n’a pas d’enfants.

On utilise ce type abstrait pour construire l’arbre suivant :

A = creer_arbre_feuille( 5)
B = creer_arbre_feuille( 4)
C = creer_arbre(3,B,A)
D = creer_arbre_feuille( 2)
E = creer_arbre(1,D,C)

  • Dessiner l’arbre correspondant.

Correction 
  1__
 /   \
2     3
     / \
    4   5

  • Quelle est la taille de l’arbre

  • 2
  • 3
  • 4
  • 5

  • Quelle est la hauteur de l’arbre

  • 2
  • 3
  • 4
  • 5

  • Qui est le père du nœud 4 ?

  • 1
  • 2
  • 3
  • 4
  • 5

  • Combien a-t-il de frères ?

  • 1
  • 2
  • 3
  • 4
  • 5

  • Combien d’enfants possède la racine ?

  • 1
  • 2
  • 3
  • 4
  • 5

5.3. Travail à faire : Construction à partir d’un tableau

On peut décrire un arbre sous la forme d’un tableau avec un numéro de nœud, un valeur v, le nœud fils du sous arbre à gauche (SAG) et le nœud fils du sous arbre à droite (SAD) :

Noeud Valeur v Noeud SAG Noeud SAD

1

*

2

3

2

+

4

5

3

-

6

7

4

3

5

/

8

9

6

8

7

*

10

11

8

4

9

2

10

2

11

3

  • Dessiner l’arbre correspondant.

Correction 
    ___*___
   /       \
  +         -
 / \       / \
3  '/'    8   *
    / \      / \
   4   2    2   3

  • Quelle est la hauteur de cet arbre ?

  • 0
  • 1
  • 3
  • 4
  • 8

  • Cet arbre est-il binaire ?

Correction

Oui cet arbre est binaire, chaque nœud à maximum deux enfants

  • Sachant que cet arbre permet un calcul mathématique, quel est le résultat obtenu ?

Correction

\( [(4/2) + 3] * [ 8 – ( 2*3) ] = 5 * 2 = 10 \)

6. Codage en python

6.1. Codage de l’arbre

Il y a plusieurs façons de coder un arbre binaire, on peut par exemple utiliser des objets reliés à partir d’une classe appelée Noeud.

class Noeud:
    def __init__(self, g,v,d):
        self.gauche= g
        self.valeur = v
        self.droite=d

Utilisation pour l’arbre ci-dessous :

arbre abcd 
arbre = Noeud( Noeud(None, 'B', Noeud(None, 'C', None)), 'A', Noeud(None, 'D', None))

6.2. Codage des mesures

Des fonctions extérieures à la classe peuvent calculer la taille et la hauteur de manière récursive :

def taille(arbre):
   """ nombre de noeuds de l'arbre"""
   if arbre is None:
      return 0
   return 1 + taille(arbre.gauche) + taille(arbre.droite)

def hauteur(arbre):
   """ hauteur de l'arbre"""
   if arbre is None:
      return 0
   return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droite))

6.3. Parcours d’un arbre binaire

Pour le calcul de la hauteur et de la taille, le sens du parcours en premier par le sous-arbre de gauche ou celui de droite n’a pas d’importance.

Par contre quand il s’agit de parcourir l’arbre pour en extraire les valeurs, on peut définir plusieurs façons, appelées :

  • infixe

  • préfixe

  • postfixe

  • en largeur.

Selon la méthode choisie, l’algorithme du parcours sera différent.

arbre 1 9

Dans cet abre binaire, les différents parcours donnent :

  • Préfixe : 1 → 2 → 4 → 5 → 7 → 8 → 3 → 6 → 9

  • Postfixe : 4 → 7 → 8 → 5 → 2 → 9 → 6 → 3 → 1

  • Infixe : 4 → 2 → 7 → 5 → 8 → 1 → 3 → 9 → 6

  • En largeur : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9

6.4. Codage d’un parcours infixe

def parcours_infixe(arbre):
   if arbre is None:
      return

parcours_infixe(arbre.gauche)
print(arbre.valeur)
parcours_infixe(arbre.droite)

6.5. Travail à faire : Description et parcours d’un arbre binaire

On vous donne l’arbre suivant:

NouvelElement177

Q1) Mesures

  • Quelle est la taille de cet arbre?

  • Quel est sa hauteur?

  • Combien cet arbre a-t-il de feuilles ?

  • Cet arbre est-il équilibré ?

Correction

  • Taille : 9

  • Hauteur : 3

  • Nombre de feuilles : 4 (4, 7, 8, 9)

  • Cet arbre n’est pas équilibré

Q2) On décide de coder cet arbre à partir d’objets de la classe Noeud :

class Noeud:
   def __init__(self, g,v,d):
      self.gauche = g
      self.valeur = v
      self.droite = d

  • Coder cet arbre à partir d’objets de la classe Noeud.

Correction 
mon_arbre = Noeud( Noeud( Noeud( None,4, None) ,2, Noeud( Noeud( None,7, None) ,5, Noeud( None,8, None))), 1 , Noeud( None,3, Noeud( Noeud( None,9, None),6, None)) )

Q3) Obtenir la hauteur et la taille

  • Ecrire les fonctions python calcule_taille(arbre) et mesure_hauteur(arbre) qui permettent de déterminer la taille et la hauteur d’un arbre binaire.

  • Vérifier que vous obtenez bien les mêmes valeurs qu’à la question 1.

Correction 
def taille(arbre):
   """ nombre de noeuds de l'arbre"""
   if arbre is None:
      return 0
   return 1 + taille(arbre.gauche) + taille(arbre.droite)

def hauteur(arbre):
   """ hauteur de l'arbre"""
   if arbre is None:
      return 0
   return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droite))

Q4) Parcours en profondeur infixe :

Dans un parcours en profondeur infixe, on liste chaque nœud ayant un fils à gauche la seconde fois qu’on le voit et chaque nœud sans fils à gauche la première fois qu’on le voit, on commence par parcourir le sous-arbre de gauche.

Les numéros sur les segments de l’arbre ci-dessous vous montre le sens parcours :

  • la valeur 4 (sans fils à gauche) est affichée la première fois qu’elle est rencontrée soit à l’étape 2 du parcours,

  • la valeur 2 qui a un fils à gauche sera affichée, la seconde fois qu’on le parcourt, au retour de l’étape 2 soit à l’étape 3.

Pour l’arbre ci-dessous, on obtiendra l’ordre d’affichage: 4;2;7;5;8;1;3;9;6

1

  • On vous donne le programme python qui réalise ce parcours :

def parcours_infixe(arbre):
   if arbre is None:
      return
   parcours_infixe(arbre.gauche)
   print(arbre.valeur, end =";")
   parcours_infixe(arbre.droite)

  • Tester le code du parcours infixe sur l’arbre de la figure 1 et comparer avec les valeurs sous la figure 2.

  • Que se passe-t-il après un return suite à un test évalué True de if arbre is None ?

Q5) Parcours en profondeur préfixe :

Dans ce cas de parcours en profondeur, on liste chaque sommet la première fois qu’on le rencontre dans le parcours.

Cela donne l’affichage: 1;2;4;5;7;8;3;6;9 pour l’arbre étudié.
pseudo code:
ParcoursPréfixe(arbre_binaire):
   si arbre_binaire est vide:
      retourner
   Afficher valeur
   ParcoursPréfixe( sous arbre_binaire gauche)
   ParcoursPréfixe( sous arbre_binaire droit)

  • Coder en python le pseudo code du parcours préfixe et tester le code.

Correction 
def parcours_prefixe(arbre):
   if arbre is None:
      return
   print(arbre.valeur, end=";")
   parcours_prefixe(arbre.gauche)
   parcours_prefixe(arbre.droite)

Q6) Parcours en profondeur postfixe :

Dans ce cas de parcours en profondeur, on liste chaque sommet la dernière fois qu’on le rencontre.

Cela donne l’affichage: 4;7;8;5;2;9;6;3;1 pour l’arbre étudié.
pseudo code:
ParcoursPostfixe(arbre_binaire):
   si arbre_binaire est vide:
      retourner

ParcoursPostfixe( sous arbre_binaire gauche)
ParcoursPostfixe( sous arbre_binaire droit)
Afficher valeur

  • Coder en python le pseudo code du parcours postfixe et tester le code.

Correction 
def parcours_postfixe(arbre):
   if arbre is None:
      return
   parcours_postfixe(arbre.gauche)
   parcours_postfixe(arbre.droite)
   print(arbre.valeur, end=";")

Q7) Parcours en largeur :

Le parcours d’un arbre en largeur consiste à partir de la racine puis visiter le fils gauche puis le fils droit, puis le fils gauche du fils gauche, puis le fils droit du fils droit, puis leurs enfants, etc..

Cela donne l’affichage: 123456789 pour l’arbre étudié.
Principe
* On utilise une File f passée en paramètre de la fonction de parcours.
* On passe également en paramètre de la fonction l’arbre à parcourir.
* On met l’arbre à parcourir dans la file f.
* Tant que la file n’est pas vide:
*   On enlève un element de la file
*   Si l'élément enlevé ne vaut pas `None`
*     On affiche la valeur du nœud de l'élément
*     On met dans la file son fils gauche
*     On met dans la file son fils droit
Implémentation
# classe cellule permet de construire un élément de la File
class Cellule :
   """ construit une cellule de liste chaînée """
   def  __init__( self, valeur, adresse_cellule_suivante) :
      self.valeur=valeur
      self.suite_liste = adresse_cellule_suivante

class File:
   def __init__(self):
      self.tete = None
      self.queue = None

   def est_vide(self):
      return self.tete is None

   def ajouter(self, valeur):
      # on crée un objet cellule qui contient la valeur à ajouter
      cell = Cellule( valeur, None)
      # on teste si c’est le premier élément ajouté
      if self.tete is None:
         self.tete = cell
      # s’il y a déjà une cellule, on rajoute en queue
      else:
         self.queue.suite_liste = cell
      self.queue = cell

   def retirer(self):
      if self.est_vide():
         raise IndexError (" la file est vide")
      # on enlève le premier élement de la file
      la_valeur_a_retirer =  self.tete.valeur
      # on fixe l’élément suivant en tête
      self.tete = self.tete.suite_liste
      # s’il n’y a plus d’élément en tête, la file est vide
      if self.tete is None:
         self.queue = None
      # on renvoie la valeur retirée.
      return la_valeur_a_retirer


def parcours_en_largeur(un_arbre, f):
   f.ajouter(un_arbre)
   while not f.est_vide():
      arbre=f.retirer()
      if arbre is not None:
         print(arbre.valeur, end= ";")
         f.ajouter(arbre.gauche)
         f.ajouter(arbre.droite)


mon_arbre = Noeud( Noeud( Noeud( None,4, None) ,2, Noeud( Noeud( None,7, None) ,5, Noeud( None,8, None))), 1 , Noeud( None,3, Noeud( Noeud( None,9, None),6, None)) )
une_file = File()
parcours_en_largeur(mon_arbre, une_file)

  • Tester le code. Détailler les étapes d’exécution de la fonction parcours_en_largeur(..) ce qui vous permettra de comprendre le code de la fonction.

7. Arbres binaires de recherche (ABR)

Un arbre binaire de recherche appelé ABR est un arbre dont les nœuds contiennent des valeurs qui peuvent être comparées entre elles (des nombres, des caractères par exemples).

Pour tout nœud de l’arbre :

  • toutes les valeurs situées dans son sous arbre de gauche sont plus petites que lui

  • toutes les valeurs situées dans son sous arbre de droite sont plus grandes que lui.
abr

7.1. Travail à faire : Reconnaitre un ABR

exercice abr

  • Peut-on classer cet arbre comme ABR ?

Correction

Non ce n’est pas un ABR sinon le fils gauche du nœud 3 aurait une valeur inférieur à ce dernier, or elle est de 4.

7.2. Recherche d’un élément

Un ABR permet une recherche optimisée, on abandonne le parcours de la sous branche qui ne correspond pas au critère de recherche.

Par exemple écrivons une fonction qui indique si un nombre appartient à l’arbre de recherche.

Un ABR permet une recherche optimisée, on abandonne le parcours de la sous branche qui ne correspond pas au critère de recherche.

Algorithme
fonction appartient(nbre, arbre):
   // determine si nbre est dans arbre
   si arbre est vide:
      retourner Faux
   si nbre < arbre.valeur:
      retourner appartient(nbre, arbre.gauche)
   si nbre > arbre.valeur:
      retourner appartient(nbre, arbre.droite)
   returner Vrai

7.3. Travail à faire : Recherche d’un élément

Soit l’abre binaire de recherche suivant :

NouvelElement182

Q1) Quelle propriété possède un ABR ?

Correction

Pour tout nœud de l’arbre :

  • toutes les valeurs situées dans son sous arbre de gauche sont plus petites que lui

  • toutes les valeurs situées dans son sous arbre de droite sont plus grandes que lui.

Q2) Mesures

  • Quelle est la taille de cet arbre?

  • Quel est sa hauteur?

  • Combien cet arbre a-t-il de feuilles ?

Correction

  • Taille : 9

  • Hauteur : 3

  • Nombre de feuilles : 3 (2, 6, 8)

Q3) Ecrire une fonction qui permette de déterminer si un nombre appartient ou pas à l’arbre.

Correction 
def appartient(valeur, arbre):
    """determine si valeur est dans arbre"""
    if arbre is None:
        return False
    if valeur < arbre.valeur:
        return appartient(valeur, arbre.gauche)
    elif valeur > arbre.valeur:
        return appartient(valeur, arbre.droite)
    else:
        return True

Q4) Quelle est la classe de complexité d’une recherche dans un ABR ?

  1.  \(\mathcal{O}(1)\)    
  2.  \(\mathcal{O}(\log(n))\)     
  3.  \(\mathcal{O}(n)\)     
  4.  \(\mathcal{O}(n\log(n))\)    
  5.  \(\mathcal{O}(n^{2})\)

Correction

Le coût de la recherche et de l’ajout dépend de la structure de l’ABR, la hauteur \( h \) de l’arbre a son influence et l’équilibre des nœuds de l’arbre impactent le temps de parcours.

Un arbre très mal équilibré (de type peigne par exemple) aura un coût linéraire, c’est l’équivalent d’une liste, le temps de parcours est proportionnel au nombre \( N \) de noeuds.

Si l’arbre est conçu équilibré ce qui demande des techniques hors programme de terminale, on obtient un coût logarithmique : \( h \leqslant C \log(N) \) avec \( C \) une constante.

7.4. Ajout d’une valeur dans un ABR

On utilise aussi une fonction récursive, l’exemple suivant montre la construction obtenue.

def ajoute(nbre, arbre):
   """ajoute nbre dans l'arbre de recherche existant et renvoie un nouvel arbre"""
   if arbre is None:
      return Noeud( None, nbre, None)
   if nbre < arbre.valeur:
      return Noeud( ajoute(nbre, arbre.gauche), arbre.valeur, arbre.droite)
   return Noeud( arbre.gauche, arbre.valeur, ajoute(nbre, arbre.droite))

# Utilisation
mon_arbre = Noeud( None, 1, None)
mon_arbre = ajoute( 3,  mon_arbre)
mon_arbre = ajoute(2, mon_arbre)
mon_arbre = ajoute( 4, mon_arbre)
mon_arbre = ajoute( 3, mon_arbre)
arbre1 4
the_end.jpg