Aller au contenu principal
Physique, Chimie et Informatique > Terminales Spé. NSI

Structures hiérarchiques : les arbres

Au programme

…de la partie « Structures de données »

Contenus Capacités attendues Commentaires
- Arbres : structures hiérarchiques.
- Arbres binaires : nœuds, racines, feuilles, sous-arbres gauches, sous-arbres droits.
- Identifier des situations nécessitant une structure de données arborescente.
- Évaluer quelques mesures des arbres binaires (taille, encadrement de la hauteur, etc.).
- On fait le lien avec la rubrique « algorithmique ».

…de la partie « Algorithmique »

Contenus Capacités attendues Commentaires
- Algorithmes sur les arbres binaires et sur les arbres binaires de recherche. - Calculer la taille et la hauteur d’un arbre. Parcourir un arbre de différentes façons (ordres infixe, préfixe ou suffixe ; ordre en largeur d’abord). Rechercher une clé dans un arbre de recherche, insérer une clé. - Une structure de données récursive adaptée est utilisée. L’exemple des arbres permet d’illustrer la programmation par classe. La recherche dans un arbre de recherche équilibré est de coût logarithmique.

Documents

4 nov. 2020

Sous-sections de Structures hiérarchiques : les arbres

Physique, Chimie et Informatique > Terminales Spé. NSI > Structures hiérarchiques : les arbres

Structures de données abstraites arborescentes : les arbres

La notion de listes chaînées est parfaite pour structurer un ensemble d’élements destinés à être énumérés séquentiellement. Elle permet aussi d’implémenter les structures de piles et de files. Elle n’est cependant pas adaptée aux accès spécifiques à des positions données dans la séquence, puisqu’il faut alors parcourir toutes les cellules depuis le début de la liste jusqu’à la position souhaitée (complexité en O(N)O(N)).

Document de référence pour ce cours

Structures arborescentes

Lorsqu’on manipule une information présentant une certaine hiérarchie, il est commun de la représenter graphiquement :

Arbre généalogique

graph TD
    A(Jules) --> B(Mireille)
    A(Jules) --> C(Gérard)
    A(Jules) --> D(Guy)
    B --> E(David)
    E --> F(Gabriel)
    E --> G(Louise)
    C --> H(Fabien)
    D --> I(Sandra)
    D --> J(Marion)

Arborescence d’un système de fichier

graph TD
  A(/) --> B(bin)
  A --> C(root)
  A --> D(home)
  A --> F(etc)
  A --> G(var)
  A --> H(usr)
  A --> I(tmp)
  D --> J(mats)
  J --> K(Documents)
  J --> L(Images)
  J --> M(Vidéos)
  K --> N(Terminale)
  N --> O(NSI)
  N --> P(PC)

Expression mathématique

graph TD
  A(+) --> B(*)
  B --> C(3)
  B --> D(8)
  A --> E(6)

Exercice

écrire l’expression mathématique représentée par l’arbre ci-dessus.

Réponse

3×8+63 \times 8 + 6

Exercice

écrire l’arbre représentant l’expression mathématique a sin(2πTt)a\, sin( \dfrac{2\pi}{T}t).

Réponse

Arbre lexicographique

Un arbre lexicographique, ou arbre en parties communes, ou dictionnaire, représente un ensemble de mots. Les préfixes communs à plusieurs mots n’apparaissent qu’une seule fois dans l’arbre.

graph TD
  A(.) --> B(m)
  B --> C(a)
  C --> D(i)
  D --> E(s)
  E --> F(o)
  F --> G(n)
  D --> H(t)
  H --> I(r)
  I --> J(i)
  J --> K(s)
  K --> L(e)
  L --> M(r)
  C --> N(t)
  N --> O(e)
  O --> P(l)
  P --> Q(a)
  Q --> R(t)
  P --> S(o)
  S --> T(t)
  A --> U(v)
  U --> V(a)
  V --> W(l)
  W --> X(i)
  X --> Y(s)
  Y --> Z(e)
Exercice

Quels sont les mots représentés dans l’arbre ?

Exercice

Ajouter les mots « matériel » et « vallon ».

Remarque : ne pas différencier les lettres é et e.

Réponse

Définitions et vocabulaire

Arbre (enraciné)

À retenir
  • Un arbre (nom complet arbre enraciné) est une structure de données abstraite arborescente dans laquelle les données sont hiérarchisées depuis un nœud racine.

  • Un arbre dont tous les nœuds sont nommés est dit étiqueté. L’étiquette (ou nom du sommet) représente la « valeur » du nœud ou bien l’information associée au nœud.

Racine, noeud, branche, feuille

À retenir
  • 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 le nœud 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.

Exercice
  • Nommer les nœuds puis les feuilles dans l’arbre représenté ci-dessous.
  • Compter le nombre de branches.
graph TD
  A(a) --> B(b)
  A --> C(c)
  B --> D(d)
  B --> E(e)
  E --> F(f)
  E --> G(g)
  B --> H(h)
  H --> I(i)
Réponses
  • Nœuds internes: a (racine), b, e, h et feuilles : c, d, f, g, i.
  • 8 branches.

Profondeur d’un nœud, hauteur d’un nœud

À retenir

La profondeur d’un nœud est sa distance à la racine.
La profondeur d’un nœud dans un arbre est donc le nombre d’arrêtes qu’il faut parcourir, depuis la racine, pour parvenir au nœud.

À retenir

La hauteur d’un nœud est sa distance à la feuille la plus profonde ayant une relation de descendance avec lui.
La hauteur d’un nœud dans un arbre est donc le nombre d’arrêtes qu’il faut parcourir, depuis ce nœud jusqu’à la feuille la plus profonde ayant une relation de descendance avec lui.

Profondeur d’un arbre

À retenir

La hauteur (ou profondeur) d’un arbre est égale à la profondeur du nœud le plus profond.

Info

La hauteur d’un arbre est très importante. En effet, la plupart des algorithmes que nous verrons dans la suite ont une complexité qui dépend de la hauteur de l’arbre. Ainsi plus l’arbre aura une hauteur élevée, plus l’algorithme mettra de temps à s’exécuter.

Avertissement

Tous les auteurs n’utilisent pas la convention choisie dans ce cours !
Pour certains, la profondeur d’un nœud est égale au nombre de nœuds qu’il faut parcourir à partir de la racine (incluse) pour parvenir au nœud ; la hauteur de la racine est alors de 1.

Exercice
  • Donner la profondeur du nœud e dans l’arbre représenté ci-dessus.
  • Donner la hauteur du nœud e dans l’arbre représenté ci-dessus.
  • Quelle est la profondeur de cet arbre ?
Réponses
  • Profondeur de e : 2.
  • Hauteur de e : 1.
  • Profondeur de l’arbre : 3.

Taille d’un arbre

À retenir

La taille d’un arbre est égale au nombre de nœuds de l’arbre (nœuds internes et feuilles).

Exercice
  • Indiquer la taille de l’arbre représenté ci-dessus.
Réponses
  • Taille de l’arbre : 9.

Degré d’un noeud, degré d’un arbre

À retenir
  • Le degré d’un nœud est égal au nombre de ses descendants (fils).
  • Le degré d’un arbre est égal au plus grand des degrés de ses nœuds.

Exercice
  • Quel est le degré du nœud b dans l’arbre représenté ci-dessus ?
  • Quel est le degré du nœud a ?
  • Quel est le degré de l’arbre ?
Réponses
  • Degré de b : 3.
  • Degré de a : 2.
  • Degré de l’arbre : 3.

Relation entre les liste et les arbres

À retenir

Un arbre dont tous les nœuds n’ont qu’un seul fils est en fait une liste.

Physique, Chimie et Informatique > Terminales Spé. NSI > Structures hiérarchiques : les arbres

Les arbres binaires

Arbres binaires

Définition

À retenir

Un arbre binaire est une structure de données abstraite formée d’un ensemble de nœuds organisés hiérarchiquement selon la définition par récurrence suivante :

Un arbre binaire est :

  • soit un arbre vide, noté EE, ne contenant aucun nœud ;
  • soit un nœud, appelé racine, relié à exactement deux arbres binaires gg et dd, respectivement appelés sous-arbres gauche et sous-arbre droit.

On note T(r,g,d)T(r,g,d) l’arbre non vide dont la racine rr (on peut aussi indiquer l’étiquette de cette racine).

Vocabulaire et remarques

  • Un nœud dont les deux sous-arbres sont vides est appelé une feuille.
  • Un nœud qui n’est pas une feuille est un nœud interne.
  • Un arbre binaire est dit parfait si toutes les feuilles sont à la même profondeur.
  • La racine d’un arbre TT est le seul nœud de TT sans parent.

Propriétés

Position des sous-arbres
  • La position des sous-arbres gauche et droite est fondamentale : T(r,g,d)≠T(r,d,g)T(r,g,d) \neq T(r,d,g)
Taille d’un arbre
  • La taille d’un arbre est égale au nombre de nœuds qu’il comporte.
  • Le nombre de nœuds d’un arbre binaire TT, noté n(T)n(T), se calcule récursivement :
    • n(E)=0n(E)=0
    • n(T)=1+n(g)+n(d)n(T)=1+n(g)+n(d)
Profondeur d’un nœud
  • La profondeur d’un nœud nn, notée h(n)h(n), est sa distance à la racine.
  • La profondeur d’un nœud nn, notée h(n)h(n), est définie récursivement par :
    • h(racine)=0h(\text{racine})=0
    • h(n)=1+h(parent de n)h(n)=1+h(\text{parent de }n)
  • La profondeur d’un nœud dans un arbre est donc le nombre d’arrêtes qu’il faut parcourir, depuis la racine, pour parvenir au nœud.
Avertissement

La définition de la profondeur d’un nœud peut varier ! Il est impératif de vérifier celle choisie avant tout travail.

Hauteur d’un arbre
  • La hauteur d’un arbre est la profondeur du nœud le plus éloigné de la racine.
    La hauteur d’un arbre est aussi sa profondeur.
  • La hauteur d’un arbre binaire TT, notée h(T)h(T) est définie récursivement par :
    • h(E)=−1h(E)=-1 si l’arbre est vide ;
    • h(T)=1+max(h(g),h(d))h(T)=1+\mathrm{max}(h(g), h(d))

Remarque

On peut aussi définir la hauteur d’un nœud : la hauteur d’un nœud est la distance entre ce nœud et la feuille la plus profonde ayant une relation de descendance avec ce nœud.

Avertissement

La définition de la hauteur d’un arbre peut varier ! Il est impératif de vérifier celle choisie avant tout travail.

Relation entre le nombre de nœuds nn et la hauteur d’un arbre
  • Soit TT un arbre binaire, nn son nombre de nœuds et hh sa hauteur. Ces grandeurs sont liées par les relations suivantes :

  • h+1≤n≤2h+1−1h + 1 \leq n \leq 2^{h+1} - 1

  • le nombre de sous-arbres vides de TT est n+1n+1.

  1. Dans quel cas a-t-on N=h+1N = h+1 ?

    Réponse

    On a N=h+1N = h+1 lorsque chaque nœud ne possède qu’un seul nœud fils. Il s’agit donc d’une structure linéaire (liste).

  2. Dans quel cas a-t-on N=2h+1−1N = 2^{h+1} - 1 ?

    Réponse

    On a N=2h+1−1N = 2^{h+1} - 1 lorsque l’arbre binaire est parfait, c’est à dire lorsque toutes les feuilles ont la même profondeur.

Spécification d’un arbre binaire

À retenir
  • Créer un nœud (type) :
    • fonction : creer_nœud() ⟶\longrightarrow retourne un nœud  ;
    • fils_gauche et fils_droit sont automatiquement initialisés à None ;;
    • complexité : O(0)O(0) (pas tout à fait vrai mais suffisant pour comprendre la suite).
  • Lire dans le champ valeur :
    • fonction : lire_valeur(n: Noeud[T]) ⟶\longrightarrow T ;
    • complexité : 1 opération élémentaire.
  • Écrire dans le champ valeur :
    • fonction : modifier_valeur(n: Noeud[T], valeur: T) ⟶\longrightarrow None ;
    • complexité : 1 opération élémentaire.
  • Lire dans le champ fils_gauche :
    • fonction : lire_filsG(n: Noeud[T]) ⟶\longrightarrow Noeud[T] ;
    • complexité : 1 opération élémentaire.
  • Écrire dans le champ fils_gauche :
    • fonction : modifier_filsG(n: Noeud[T], m: Noeud[T]) ⟶\longrightarrow None ;
    • complexité : 1 opération élémentaire.
  • Lire dans le champ fils_droit :
    • fonction : lire_filsD(n: Noeud[T]) ⟶\longrightarrow Noeud[T] ;
    • complexité : 1 opération élémentaire.
  • Écrire dans le champ fils_droit :
    • fonction : modifier_filsD(n: Noeud[T], m: Noeud[T]) ⟶\longrightarrow None ;
    • complexité : 1 opération élémentaire.
Avertissement

Tout comme on a désigné les listes chaînées par leur première cellule, on va désigner les arbres par leur nœud racine.

Implémentation de la spécification en Python à l’aide d’une classe

Il existe de nombreuses façons de d’implémenter la structure d’arbre en Python. Dans cette partie on va utiliser une classe.

Avertissement

Le paradigme de programmation utilisé ci-dessous est le paradigme impératif : on crée dans un premier temps une structure élémentaire qui ne sert qu’à stocker les différentes valeurs et on définit ensuite des fonctions qui manipulent cette structure.

La structure utilisée peut être :

  • Une classe qui définit trois attributs valeur, gauche et droit et aucune méthode ;
  • Une liste Python de trois éléments ;
  • Un dictionnaire comportant trois clés : valeur, gauche et droit.

On peut même imaginer utiliser un tableau ou une liste chaînée !

On ne créera pas de structure « arbre binaire » (accompagnée de méthodes) dans ce document.

  1. Écrire le code de la classe Noeud respectant la spécification. Les trois attributs seront nommés valeur, gauche, droit.
Réponse
from __future__ import annotations


class Noeud:
    """
    Structure de stockage pour créer des arbres binaires.
    """

    def __init__(self: Noeud, val: str, g: Noeud = None, d: Noeud = None) -> None:
        """Initialisation de l'objet."""
        self.valeur = val
        self.gauche = g
        self.droit = d
  1. Écrire le code permettant de construire l’arbre :
    graph TD
      A("A") --- B("B")
      B --- G(None)
      B --- C("C")
      C --- H(None)
      C --- I(None)
      A --- D("D")
      D --- E(None)
      D --- F(None)
    
Réponse
arbre_1 = Noeud("A", Noeud("B", None, Noeud("C")), Noeud("D"))

ou

abr1 = Noeud("A")
abr1.gauche = Noeud("B")
abr1.droit = Noeud("D")
abr1.gauche.droit = Noeud("C")
  1. Quel arbre correspond à ce code ?
abr = Noeud(
    "r",
    Noeud(
        "a",
        Noeud("c", None, Noeud("h")),
        Noeud("d", Noeud("i"), Noeud("j", Noeud("m"), None)),
    ),
    Noeud("b", Noeud("e", Noeud("k", None, None), None), Noeud("f")),
)
Réponse

Écrire le code différemment en créant les nœuds les uns après les autres.

Réponse
abr = Noeud("r")
abr.gauche = Noeud("a")
abr.droit = Noeud("b")
abr.gauche.gauche = Noeud("c")
abr.gauche.droit = Noeud("d")
abr.gauche.gauche.droit = Noeud("h")
abr.gauche.droit.gauche = Noeud("i")
abr.gauche.droit.droit = Noeud("j")
abr.gauche.droit.droit.gauche = Noeud("m")
abr.droit.gauche = Noeud("e")
abr.droit.gauche.gauche = Noeud("k")
abr.droit.droit = Noeud("f")
  1. Écrire le code de la fonction est_vide dont la spécification est :
def est_vide(n: Noeud) -> bool:
    """
    Teste si un arbre est vide.
    """
Réponse
def est_vide(n: Noeud) -> bool:
    """
    Teste si un arbre est vide.
    """
    return n == None
  1. Écrire le code de la fonction ajoute_filsG dont la spécification est :
def ajoute_filsG(n: Noeud, valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils gauche.
    """
Réponse
def ajoute_filsG(n: Noeud, valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils gauche.
    """
    if est_vide(n.gauche):
        n.gauche = Noeud(valeur)
    else:
        raise Exception("Le nœud possède déjà un fils gauche !")
  1. Écrire le code de la fonction ajoute_filsD dont la spécification est :
def ajoute_filsD(n: Noeud, valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils droit.
    """
Réponse
def ajoute_filsD(n: Noeud, valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils droit.
    """
    if est_vide(n.droit):
        n.droit = Noeud(valeur)
    else:
        raise Exception("Le nœud possède déjà un fils droit !")
  1. Écrire le code de la fonction est_feuille dont la spécification est :
def est_feuille(n: Noeud) -> bool:
    """
    Teste si un noeud est une feuille.
    """
Réponse
def est_feuille(n: Noeud) -> bool:
    """
    Teste si un noeud est une feuille.
    """
    return est_vide(n.gauche) and est_vide(n.droit)
  1. Écrire le code de la fonction degre_noeud dont la spécification est :
def degre_noeud(n: Noeud) -> int:
    """
    Détermine le degré du noeud passé en argument.
    """

Quelques algorithmes de manipulation des arbres binaires

Tous les algorithmes qui suivent sont récursifs.

  1. Écrire le code de la fonction taille dont la spécification est :
def taille(n: Noeud) -> int:
    """
    Retourne le nombre de noeud dans l'arbre.
    """
Réponse
def taille(n: Noeud) -> int:
    """
    Retourne le nombre de noeud dans l'arbre.
    """
    if est_vide(n):
        # Cas de base : un arbre vide ne contient aucun noeud.
        return 0
    else:
        # Recherche récursive dans les sous-arbres gauche et droit.
        taille_gauche = taille(n.gauche)
        taille_droit = taille(n.droit)

        # Calcul de la taille
        return 1 + taille_gauche + taille_droit
  1. Écrire le code de la fonction profondeur dont la spécification est :
def profondeur(n: Noeud) -> int:
    """
    Retourne la profondeur de l'arbre.
    """
Réponse
def profondeur(n: Noeud) -> int:
    """
    Retourne la profondeur de l'arbre.
    """
    if est_vide(n):
        # Cas de base : si le nœud est vide, il n'est pas dans l'arbre.
        return -1
    else:
        # Recherche récursive dans les sous-arbres gauche et droit.
        arbre_gauche = profondeur(n.gauche)
        arbre_droit = profondeur(n.droit)

        # Détermine la profondeur
        return 1 + max(arbre_gauche, arbre_droit)
  1. Écrire le code de la fonction nbre_feuilles dont la spécification est :
def nbre_feuilles(n: Noeud) -> int:
    """
    Détermine le nombre de feuilles dans l'arbre.
    """
Réponse
def nbre_feuilles(n: Noeud) -> int:
    """
    Détermine le nombre de feuilles dans l'arbre.
    """
    if est_vide(n):
        # Cas de base : un arbre vide ne contient aucune feuille
        return 0
    elif est_feuille(n):
        # Cas de base : on ajoute 1 au total dès qu'on rencontre une feuille
        return 1
    else:
        # Recherche récursive dans les sous-arbres gauche et droit.
        nbre_feuilles_gauche = nbre_feuilles(n.gauche)
        nbre_feuilles_droit = nbre_feuilles(n.droit)

        # Calcul du nombre de feuilles
        return nbre_feuilles_gauche + nbre_feuilles_droit
  1. Écrire le code de la fonction profondeur_noeud dont la spécification est :
def profondeur_noeud(n: Noeud, val: str, prof: int = 0) -> int:
    """
    Détermine la profondeur du noeud de valeur val.
    """
Réponse
def profondeur_noeud(n: Noeud, val: str, prof: int = 0) -> int:
    """
    Détermine la profondeur du noeud de valeur val.
    Retourne -1 si le noeud n'est pas dans l'arbre.

    prof est la profondeur.
    """
    if est_vide(n):
        # Cas de base : si le nœud est vide, il n'est pas dans l'arbre.
        return -1
    elif n.valeur == val:
        # On a trouvé le noeud
        return prof
    else:
        # Recherche récursive dans les sous-arbres gauche et droit.
        # Incrémente la profondeur
        prof_gauche = profondeur_noeud(n.gauche, val, prof + 1)
        prof_droite = profondeur_noeud(n.droit, val, prof + 1)

        # Valeur retournée
        return max(prof_gauche, prof_droite)

Exemple : recherche de la profondeur du nœud de valeur 3

Les nœuds passés en argument sont repérés par la notation 1n, 2n, …

p(1n, 3, 0)
    p(2n, 3, 1)           -> -1
        p(4n, 3, 2)       -> -1
            p(None, 3, 3) -> -1
            p(None, 3, 3) -> -1
        p(5n, 3, 2)       -> -1
            p(None, 3, 3) -> -1
            p(None, 3, 3) -> -1
    p(3n, 3, 1)           -> 1 
  1. Écrire le code de la fonction remplace dont la spécification est :
def remplace(n: Noeud, val_ini: str, val_fin: str) -> None:
    """
    Cherche tous les noeuds de valeur val_ini et remplace ces
    dernières par val_fin.
    """
Réponse
def remplace(n: Noeud, val_ini: str, val_fin: str) -> None:
    """
    Cherche tous les noeuds de valeur val_ini et remplace ces
    dernières par val_fin.
    """
    if est_vide(n):
        return None
    elif n.valeur == val_ini:
        n.valeur = val_fin
    else:
        remplace(n.gauche, val_ini, val_fin)
        remplace(n.droit, val_ini, val_fin)
  1. Écrire le code de la fonction ajoute dont la spécification est :
def ajoute(n: Noeud, parent: str, enfant: str, gauche: bool) -> None:
    """
    Ajoute un noeud de valeur enfant comme enfant du noeud de valeur
    parent.
    Le noeud enfant est placé par défaut à gauche.

    HYPOTHÈSE : Le noeud de valeur parent existe.
    """
Réponse
def ajoute(n: Noeud, parent: str, enfant: str, gauche: bool) -> None:
    """
    Ajoute un noeud de valeur enfant comme enfant du noeud de valeur
    parent.
    Le noeud enfant est placé par défaut à gauche.

    HYPOTHÈSE : Le noeud de valeur parent existe.
    """
    if est_vide(n):
        return None
    elif n.valeur == parent:
        if gauche and not est_vide(n.gauche):
            raise Exception("Le noeud enfant gauche existe déjà !")
        if not gauche and not est_vide(n.droit):
            raise Exception("Le noeud enfant droit existe déjà !")
        if gauche:
            n.gauche = Noeud(enfant)
        else:
            n.droit = Noeud(enfant)
    else:
        ajoute(n.gauche, parent, enfant, gauche)
        ajoute(n.droit, parent, enfant, gauche)
  1. Écrire le code de la fonction supprime dont la spécification est :
def supprime(n: Noeud, val: str) -> None:
    """
    Supprime le noeud de valeur val ainsi que tous ses descendants.
    """
Réponse
def supprime(n: Noeud, val: str) -> None:
    """
    Supprime le noeud de valeur val ainsi que tous ses descendants.
    """
    if est_vide(n):
        return None
    elif est_feuille(n):
        return None
    elif n.gauche.valeur == val:
        n.gauche = None
    elif n.droit.valeur == val:
        n.droit = None
    else:
        supprime(n.gauche, val)
        supprime(n.droit, val)
  1. Quelles sont les complexités des algorithmes implémentés dans cette section ?
    Réponse

    Les algorithmes parcourent une fois chaque nœud de l’arbre. La complexité est donc proportionnelle au nombre de nœuds.

Parcours en profondeur d’un arbre

Les fonction écrites jusqu’à présent parcourent en profondeur tous les nœuds des arbres sans que l’ordre dans lequel ce parcourt est effectué ait la moindre importance.

À retenir

Si on souhaite donner un affichage de l’arbre, la façon dont on le parcourt prend alors une grande importance. On peut :

  • Parcourir le sous-arbre gauche, afficher la valeur du nœud racine puis enfin parcourir le sous-arbre droit. On parle d’un parcours infixe.
  • Afficher la valeur du nœud racine avant de parcourir le sous-arbre gauche puis le sous-arbre droit. On parle d’un parcours préfixe.
  • Parcourir le sous-arbre gauche, le sous-arbre droit puis afficher les valeurs. On parle d’un parcours suffixe.
  1. Pour l’arbre ci-dessous, donner les parcours préfixe, infixe et suffixe.

    graph TD
        0(0) --- 1(1)
        0 --- 8(8)
        1 --- 2(2)
        2 --- 3(3)
        1 --- 4(4)
        4 --- 5(5)
        4 --- 6(6)
        6 --- 7(7)
        8 --- 9(9)
        8 --- 13(13)
        9 --- 10(10)
        10 --- 11(11)
        10 --- 12(12)
        13 --- 14(14)
        13 --- 15(15)
    
    Réponses
    • Préfixe : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
    • Infixe : 3, 2, 1, 5, 4, 6, 7, 0, 11, 10, 12, 9, 8, 14, 13, 15
    • Suffixe : 3, 2, 5, 7, 6, 4, 1, 11, 12, 10, 9, 14, 15, 13, 8, 0

  2. Écrire le code des fonctions parcours_infixe, parcours_prefixe et parcours_suffixe dont les spécifications sont :

def parcours_infixe(n: Noeud) -> str:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    Retourne le parcours sous forme d'une chaîne de caractères.
    """
Réponse
def parcours_infixe(n: Noeud) -> str:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    Retourne le parcours sous forme d'une chaîne de caractères.
    """
    if est_vide(n):
        return ""
    else:
        chaine = parcours_infixe(n.gauche)
        chaine += str(n.valeur)
        chaine += parcours_infixe(n.droit)
        return chaine
def parcours_prefixe(n: Noeud) -> None:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    Retourne le parcours sous forme d'une chaîne de caractères.
    """
Réponse
def parcours_prefixe(n: Noeud) -> None:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    Retourne le parcours sous forme d'une chaîne de caractères.
    """
    if est_vide(n):
        return ""
    else:
        chaine = str(n.valeur)
        chaine += parcours_prefixe(n.gauche)
        chaine += parcours_prefixe(n.droit)
        return chaine
def parcours_suffixe(n: Noeud) -> None:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    Retourne le parcours sous forme d'une chaîne de caractères.
    """
Réponse
def parcours_suffixe(n: Noeud) -> None:
    """
    Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
    Retourne le parcours sous forme d'une chaîne de caractères.
    """
    if est_vide(n):
        return ""
    else:
        chaine = parcours_suffixe(n.gauche)
        chaine += parcours_suffixe(n.droit)
        chaine += str(n.valeur)
        return chaine

Algorithmes itératifs — Parcours d’un arbre à l’aide d’une file ou d’une pile

Parcours en largeur d’un arbre

  1. Décrire le fonctionnement de l’algorithme suivant et montrer qu’il réalise un parcours en largeur d’un arbre.
Fonction parcours_largeur(racine: Noeud):
    File f = File()
    f.enfiler(racine)
    TantQue non f.est_vide():
        n = f.defiler()
        print(n.valeur)
        Si non est_vide(n.filsG):
            f.enfiler(n.filsG)
        FinSi
        Si non est_vide(n.filsD):
            f.enfiler(n.filsD)
        FinSi
    FinTantQue
FinFonction
  1. Implémenter en Python cet algorithme.
Réponse
def parcours_largeur(n: Noeud) -> str:
    """Réalise le parcours en largeur d'un arbre binaire."""
    message = ""

    f = File()
    f.enfiler(n)
    while not f.est_vide():
        n = f.defiler()
        message += str(n.valeur)
        if not est_vide(n.gauche):
            f.enfiler(n.gauche)
        if not est_vide(n.droit):
            f.enfiler(n.droit)

    return message

Parcours en profondeur d’un arbre

  1. Décrire le fonctionnement de l’algorithme suivant et montrer qu’il réalise un parcours en profondeur d’un arbre.
    De quel type de parcours en profondeur s’agit-il ?
Fonction parcours_profondeur(racine: Noeud):
    Pile p = Pile()
    p.empiler(racine)
    TantQue non p.est_vide():
        n = p.depiler()
        print(n)
        Si non est_vide(n.filsG):
            p.empiler(n.filsG)
        FinSi
        Si non est_vide(n.filsD):
            p.empiler(n.filsD)
        FinSi
    FinTantQue
FinFonction
Réponse

L’algorithme semble realiser un parcours préfixe mais en explorant d’abord le sous-arbre droit au lieu d’explorer le sous-arbre gauche.

Modifier l’algorithme de telle sorte qu’il réalise le parcours préfixe.

Réponse
Fonction parcours_profondeur(racine: Noeud):
    Pile p = Pile()
    p.empiler(racine)
    TantQue non p.est_vide():
        n = p.depiler()
        print(n)
        Si non est_vide(n.filsD):
            p.empiler(n.filsD)
        FinSi
        Si non est_vide(n.filsG):
            p.empiler(n.filsG)
        FinSi
    FinTantQue
FinFonction
  1. Implémenter en Python cet algorithme.
Réponse
def parcours_prefixe_iter(n: Noeud) -> str:
    """
    Réalise un parcours préfixe à l'aide d'une pile.
    """
    message = ""

    p = Pile()
    p.empiler(n)
    while not p.est_vide():
        n = p.depiler()
        message += str(n.valeur)
        if not est_vide(n.gauche):
            p.empiler(n.gauche)
        if not est_vide(n.droit):
            p.empiler(n.droit)
    return message

Implémentation de la spécification en Python à l’aide d’une liste Python

  1. Reprendre toutes les fonctions de ce document en n’utilisant pas la classe Noeud mais une liste à trois éléments. Le premier est la « valeur » du noeud, le second l’adresse du fils gauche, le troisième l’adresse du fils droit.
Réponse
"""
Implémentation d'un arbre binaire en utilisant le
paradigme impératif et des listes.

Structure d'un noeud : [valeur, gauche, droit]
"""


def est_vide(n: list[str, list, list]) -> bool:
    """
    Teste si un arbre est vide.
    """
    return n is None


def ajoute_filsG(n: list[str, list, list], valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils gauche.
    """
    if est_vide(n[1]):
        n[1] = [valeur, None, None]
    else:
        raise Exception("Le nœud possède déjà un fils gauche !")


def ajoute_filsD(n: list[str, list, list], valeur: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils droit.
    """
    if est_vide(n[2]):
        n[2] = [valeur, None, None]
    else:
        raise Exception("Le nœud possède déjà un fils droit !")


def est_feuille(n: list[str, list, list]) -> bool:
    """
    Teste si un noeud est une feuille.
    """
    return est_vide(n[1]) and est_vide(n[2])


def degre_noeud(n: list[str, list, list]) -> int:
    """
    Détermine le degré du noeud passé en argument.
    """
    if est_vide(n):
        raise Exception("Le nœud est vide !")

    nbre = 0
    if not est_vide(n[1]):
        nbre += 1
    if not est_vide(n[2]):
        nbre += 1

    return nbre


def taille(n: list[str, list, list]) -> int:
    """
    Retourne le nombre de noeud dans l'arbre.
    """
    if est_vide(n):
        return 0
    else:
        return 1 + taille(n[1]) + taille(n[2])


def profondeur(n: list[str, list, list]) -> int:
    """
    Retourne la profondeur de l'arbre.
    """
    if est_vide(n):
        return -1
    else:
        return 1 + max(profondeur(n[1]), profondeur(n[2]))


def nbre_feuilles(n: list[str, list, list]) -> int:
    """
    Détermine le nombre de feuilles dans l'arbre.
    """
    if est_vide(n):
        return 0
    elif est_feuille(n):
        return 1
    else:
        return nbre_feuilles(n[1]) + nbre_feuilles(n[2])


def parcours_pref(n: list[str, list, list]) -> str:
    """Parcours en profondeur préfixe d'un arbre binaire."""
    if est_vide(n):
        return ""
    else:
        chaine = str(n[0])
        chaine += parcours_pref(n[1])
        chaine += parcours_pref(n[2])
        return chaine


def parcours_inf(n: list[str, list, list]) -> str:
    """Parcours en profondeur infixe d'un arbre binaire."""
    if est_vide(n):
        return ""
    else:
        chaine = parcours_inf(n[1])
        chaine += str(n[0])
        chaine += parcours_inf(n[2])
        return chaine


def parcours_suf(n: list[str, list, list]) -> str:
    """Parcours en profondeur infixe d'un arbre binaire."""
    if est_vide(n):
        return ""
    else:
        chaine = parcours_suf(n[1])
        chaine += parcours_suf(n[2])
        chaine += str(n[0])
        return chaine


if __name__ == "__main__":
    arb = [
        "A",
        ["B", ["C", None, None], ["D", None, None]],
        ["E", ["F", None, None], ["G", ["H", None, None], None]],
    ]
    print(est_vide(arb))
    print(f"Taille de l'arbre : {taille(arb)}")
    print(f"Profondeur (hauteur) de l'arbre : {profondeur(arb)}")
    print(f"Préfixe : {parcours_pref(arb)}")
    print(f"Infixe : {parcours_inf(arb)}")
    print(f"Suffixe : {parcours_suf(arb)}")

Implémentation de la spécification en Python à l’aide d’un dictionnaire

  1. Reprendre toutes les fonctions de ce document en n’utilisant pas la classe Noeud mais un dictionnaire à trois clés : valeur, gauche et droit pour stocker la « valeur » du noeud, l’adresse du fils gauche et l’adresse du fils droit.
Réponse
"""
Implémentation du type arbre binaire en utilisant
le paradigme impératif et des dictionnaires.
"""


def est_vide(n: dict[str, dict, dict]) -> bool:
    """
    Teste si un arbre est vide.
    """
    return n == None


def ajoute_filsG(n: dict[str, dict, dict], val: str) -> None:
    """
    Ajoute un noeud d'étiquette val comme fils gauche.
    """
    if est_vide(n["gauche"]):
        n["gauche"] = {"valeur": val, "gauche": None, "droit": None}
    else:
        raise Exception("Le nœud possède déjà un fils gauche !")


def ajoute_filsD(n: dict[str, dict, dict], val: str) -> None:
    """
    Ajoute un noeud d'étiquette valeur comme fils droit.
    """
    if est_vide(n["droit"]):
        n["droit"] = {"valeur": val, "gauche": None, "droit": None}
    else:
        raise Exception("Le nœud possède déjà un fils droit !")


def est_feuille(n: dict[str, dict, dict]) -> bool:
    """
    Teste si un noeud est une feuille.
    """
    return est_vide(n["gauche"]) and est_vide(n["droit"])


def degre_noeud(n: dict[str, dict, dict]) -> int:
    """
    Détermine le degré du noeud passé en argument.
    """
    if est_vide(n):
        raise Exception("Le nœud est vide !")

    nbre = 0
    if not est_vide(n["gauche"]):
        nbre += 1
    if not est_vide(n["droit"]):
        nbre += 1

    return nbre


def taille(n: dict[str, dict, dict]) -> int:
    """
    Retourne le nombre de noeud dans l'arbre.
    """
    if est_vide(n):
        return 0
    else:
        return 1 + taille(n["gauche"]) + taille(n["droit"])


def profondeur(n: dict[str, dict, dict]) -> int:
    """
    Retourne la profondeur de l'arbre.
    """
    if est_vide(n):
        return -1
    else:
        return 1 + max(profondeur(n["gauche"]), profondeur(n["droit"]))


def nbre_feuilles(n: dict[str, dict, dict]) -> int:
    """
    Détermine le nombre de feuilles dans l'arbre.
    """
    if est_vide(n):
        return 0
    elif est_feuille(n):
        return 1
    else:
        return nbre_feuilles(n["gauche"]) + nbre_feuilles(n["droit"])


def parcours_pref(n: dict[str, dict, dict]) -> str:
    """Parcours en profondeur préfixe d'un arbre binaire."""
    if est_vide(n):
        return ""
    else:
        return str(n["valeur"]) + parcours_pref(n["gauche"]) + parcours_pref(n["droit"])


def parcours_inf(n: dict[str, dict, dict]) -> str:
    """Parcours en profondeur infixe d'un arbre binaire."""
    if est_vide(n):
        return ""
    else:
        return parcours_inf(n["gauche"]) + str(n["valeur"]) + parcours_inf(n["droit"])


def parcours_suf(n: dict[str, dict, dict]) -> str:
    """Parcours en profondeur infixe d'un arbre binaire."""
    if est_vide(n):
        return ""
    else:
        return parcours_suf(n["gauche"]) + parcours_suf(n["droit"]) + str(n["valeur"])


if __name__ == "__main__":
    arb = {
        "valeur": "A",
        "gauche": None,
        "droit": {
            "valeur": "B",
            "gauche": {"valeur": "C", "gauche": None, "droit": None},
            "droit": {"valeur": "D", "gauche": None, "droit": None},
        },
    }
    print(est_vide(arb))
    print(parcours_inf(arb))

    arb2 = {"valeur": "A", "droit": None, "gauche": None}
    ajoute_filsG(arb2, "B")
    ajoute_filsD(arb2, "C")
    noeud_C = arb2["droit"]
    ajoute_filsD(noeud_C, "D")
    ajoute_filsG(noeud_C, "E")
    print(f"Taille de l'arbre : {taille(arb2)}")
    print(f"Profondeur (hauteur) de l'arbre : {profondeur(arb2)}")
    print(parcours_pref(arb2))
    print(parcours_inf(arb2))
    print(parcours_suf(arb2))

À retenir

À retenir

Un arbre binaire est un ensemble fini de nœuds, qui est soit vide (la valeur None est utilisée pour représenter l’arbre vide), soit structuré à partir d’un nœud particulier, appelé racine de l’arbre, et de deux sous-ensembles de nœuds formant récursivement un sous-arbre gauche et un sous-arbre droit.

Un arbre peut-être implémenté en Python avec un objet par nœud, d’une classe qui possède trois attributs : la valeur (ou étiquette) du nœud, le sous-arbre gauche et le sous-arbre droit. Il peut aussi être implémenté en utilisant une liste à trois éléments ou un dictionnaire à trois éléments.

Physique, Chimie et Informatique > Terminales Spé. NSI > Structures hiérarchiques : les arbres

Arbres Binaires Recherche

Introduction

Info

Quelle structure de données permet :

  • d’organiser les données selon un ordre donné (numérique, lexicographique, etc.) ;
  • d’effectuer des recherches le plus efficacement possible ;
  • d’accéder à, d’insérer ou de supprimer les données le plus efficacement possible.

Tableaux

Propriétés
  • On peut ordonner des données dans un tableau mais l’algorithme de tri le plus rapide, pour un jeu de données aléatoires, est en O(n  log⁡n)O(n \; \log n) ;
  • On peut accéder à une donnée en O(1)O(1) ;
  • On peut rechercher une valeur efficacement en utilisant la dichotomie (si le tableau est trié !) : O(log⁡n)O(\log n) ;
  • Supprimer ou insérer une valeur n’est pas très efficace : O(n)O(n) (sauf à la fin du tableau).

Dictionnaires

Propriétés
  • Accéder à, supprimer et insérer une valeur se fait très efficacement : O(1)O(1) ;
  • Les données ne sont pas ordonnées.
Remarque
Dans la suite de ce document, on considérera que les valeurs des nœuds sont des entiers.
À retenir

Un arbre binaire de recherche, ou ABR, est un arbre binaire avec la propriété suivante : quel que soit le nœud xx, tous les nœuds situés dans le sous-arbre gauche de xx ont une valeur inférieure à la valeur du nœud xx, et tous ceux situés dans son sous-arbre droit ont une valeur supérieure à la valeur du nœud xx.

Remarque
La définition précédente est récursive.
  1. Cet arbre binaire est-il un arbre binaire de recherche ?

    graph TD
        A(3) --- B(1)
        B --- C(None)
        B --- D(2)
        D --- E(None)
        D --- F(None)
        A --- G(4)
        G --- H(None)
        G --- I(None)
    
    Réponse

    oui

  2. Cet arbre binaire est-il un arbre binaire de recherche ?

    graph TD
        A(3) --- B(2)
        B --- C(1)
        C --- D(None)
        C --- E(None)
        B --- F(None)
        A --- G(4)
        G --- H(None)
        G --- I(None)
    
    Réponse

    oui

  3. Cet arbre binaire est-il un arbre binaire de recherche ?

    graph TD
       A(3) --- B(2)
        B --- C(None)
        B --- D(1)
        D --- E(None)
        D --- F(None)
        A --- G(4)
        G --- H(None)
        G --- I(None)
    

Réponse

Non ! La propriété est bien vérifiée pour la racine mais pas pour le sous-arbre gauche.
La définition est récursive !

Info

Les ABR servent à maintenir un ensemble de valeurs ordonnées, avec une meilleure complexité qu’une liste chaînée par exemple. On commence par la recherche d’un élément. La structure de l’ABR permet d’éviter de le parcourir en entier.

Un ABR est un arbre binaire

Avertissement

Le paradigme de programmation utilisé ci-dessous est le paradigme impératif : on crée dans un premier temps une structure élémentaire à l’aide d’une classe et on définit ensuite des fonctions qui manipulent cette structure.
On ne crée pas de structure arbre binaire (accompagnée de méthodes).

  1. Pour représenter un ABR, on va à nouveau utiliser la classe Noeud. Écrire à nouveau le code de cette classe.
    Les contraintes sur les valeurs des nœuds ne sont pas codées dans la classe.

  2. À quel arbre binaire de recherche ce code correspond-il ?

# Création d'un arbre binaire de recherche
arbre = Noeud(10)
arbre.gauche = Noeud(5)
arbre.droit = Noeud(15)
arbre.gauche.gauche = Noeud(3)
arbre.gauche.droit = Noeud(8)
arbre.droit.gauche = Noeud(12)
arbre.droit.droit = Noeud(18)
Réponse
graph TD
    A(10) --- B(5)
    A --- C(15)
    B --- D(3)
    B --- E(8)
    C --- F(12)
    C --- I(18)
  1. Écrire à nouveau les spécifications des fonctions taille, hauteur et parcours (parcours infixe).
def est_vide(n: Noeud) -> bool:
    """
    Teste si le noeud passé en argument est vide ou pas.
    """
Réponse
def est_vide(n: Noeud) -> bool:
    """
    Teste si un arbre est vide.
    """
    return n == None
def hauteur(a: Noeud) -> int:
    """
    Retourne la hauteur de l'arbre binaire de recherche a.
    """
Réponse
def hauteur(n: Noeud) -> int:
    """
    Retourne la profondeur de l'arbre.
    """
    if est_vide(n):
        # Cas de base : si le nœud est vide, il n'est pas dans l'arbre.
        return -1
    else:
        # Recherche récursive dans les sous-arbres gauche et droit.
        arbre_gauche = hauteur(n.gauche)
        arbre_droit = hauteur(n.droit)

        # Détermine la profondeur
        return 1 + max(arbre_gauche, arbre_droit)
def taille(a: Noeud) -> int:
    """
    Retourne le nombre de noeuds dans l'arbre binaire de recherche.
    """
Réponse
def taille(n: Noeud) -> int:
    """
    Retourne le nombre de noeud dans l'arbre.
    """
    if est_vide(n):
        # Cas de base : un arbre vide ne contient aucun noeud.
        return 0
    else:
        # Recherche récursive dans les sous-arbres gauche et droit.
        taille_gauche = taille(n.gauche)
        taille_droit = taille(n.droit)

        # Calcul de la taille
        return 1 + taille_gauche + taille_droit
def parcours(n: Noeud) -> None:
    """
    Parcours infixe de l'arbre
    """
Réponse
def parcours_inf(n: Noeud) -> str:
    """Parcours en profondeur infixe d'un arbre binaire."""
    if est_vide(n):
        # Cas de base : On atteint un noeud vide
        return ""
    else:
        # Appel récursif à gauche, valeur du nœud, appel récursif à droite
        chaine = parcours_inf(n.gauche)
        chaine += str(n.valeur)
        chaine += parcours_inf(n.droit)
        return chaine
  1. Vérifier que la fonction parcours affiche les valeurs dans l’ordre croissant.
Avertissement
Rappel
On peut voir le parcours infixe comme la projection de l’arbre sur une droite.

Recherche dans un ABR

  1. Écrire le code de la fonction appartient dont la spécification est
def appartient(a: Noeud, x: int) -> bool:
    """
    Détermine si la valeur x apparaît dans l'arbre a.
    """
Réponse
def appartient(a: Noeud, x: int) -> bool:
    """
    Détermine si la valeur x apparaît dans l'abr a.
    """
    if est_vide(a):
        # Cas de base : on parvient à un noeud vide,
        # la valeur n'est pas présente
        return False
    elif a.valeur == x:
        # Cas de base : on parvient au noeud recherché
        return True
    # Appels récursifs
    elif a.valeur > x:
        return appartient(a.gauche, x)
    else:
        return appartient(a.droit, x)
  1. Quelle est la complexité de cette recherche ?
Réponse

La complexité du pire cas de la fonction appartient dépend de la hauteur de l’arbre binaire de recherche (ABR).

  • Dans le pire des cas, l’arbre peut être déséquilibré au point de ressembler à une liste chaînée. Dans un tel scénario, la complexité de la recherche est linéaire par rapport au nombre total de nœuds dans l’arbre.
    Complexité : O(n)O(n).
  • Si on écarte ce cas extrême, l’arbre binaire de recherche (ABR) est plus ou moins équilibré et la hauteur est de l’ordre du logrithme du nombre de nœuds.
    Complexité : O(log⁡n)O(\log n).

Ajout d’une valeur dans un ABR

  1. Envisager un ABR et, à la main, ajouter un élément.

  2. Quel peut-être le code de la fonction ajoute dont la spécification est

def ajoute(a: Noeud, x: int) -> None:
    """
    Ajoute x à l'arbre a (en place).

    HYPOTHÈSE : a n'est pas l'arbre vide.
    """
  1. Quelle est la complexité de cette fonction ?

  2. Pour résoudre le problème de l’ajout d’une valeur à un arbre initialement vide et/ou pour ne pas modifier un arbre déjà constitué, il est possible de programmer la fonction ajoute_copie dont la spécification est

def ajoute_copie(n: Noeud, x: int) -> Noeud:
    """
    Ajoute la valeur x à l'ABR n. Un nouvel arbre est créé.
    """

Écrire le code de cette fonction.

Utilisation d’un arbre binaire de recherche

  1. Créer la fonction plus_petit_element dont la spécification est
def plus_petit_element(a: Noeud) -> int:
    """
    Retourne le plus petit élément de l'arbre binaire de recherche a.

    Lève une exception si l'arbre est vide.
    """
  1. Créer la fonction plus_grand_element dont la spécification est
def plus_grand_element(a: Noeud) -> int:
    """
    Retourne le plus grand élément de l'arbre binaire de recherche a.

    Lève une exception si l'arbre est vide.
    """
  1. Créer la fonction est_abr dont la spécification est
def est_abr(a: Noeud) -> bool:
    """
    Détermine si l'arbre a est un arbre binaire de recherche.
    """

Corrigé

Corrigé de l'activité

À retenir

À retenir

Un arbre binaire de recherche est un arbre binaire contenant des valeurs ordonnées, tel que tout nœud contient une valeur plus grande (respectivement plus grande ou égale) que les valeurs de tous les nœuds situés dans son sous-arbre gauche. Cette organisation permet de procéder par dichotomie, en n’ayant à considérer qu’un seul sous-arbre pendant une opération. Lorsqu’ils sont équilibrés, les arbres binaires de recherche constituent une méthode très efficace pour stocker et rechercher de l’information.

Physique, Chimie et Informatique > Terminales Spé. NSI > Structures hiérarchiques : les arbres

Le codage de Huffman

Cette séance a pour objet l’étude d’une méthode de compression de données inventée par David Albert Huffman en 1952. Cette méthode permet de réduire la longueur du codage d’un alphabet et repose sur la création d’un arbre binaire.

Différents types de codages

Info

On appelle alphabet l’ensemble des symboles (caractères) composant la donnée de départ à compresser.

Dans la suite, nous utiliserons un alphabet composé seulement des 8 lettres A, B, C, D, E, F, G et H.

On cherche à coder chaque lettre de cet alphabet par une séquence de chiffres binaires.

  1. Combien de bits sont nécessaires pour coder chacune des 8 lettres de l’alphabet ?

    Réponse

    Il faut coder 8 caractères, on a donc besoin de 3 bits, puisque 23=82^3 = 8.

  2. Quelle est la longueur en octets d’un message de 1 000 caractères construit sur cet alphabet ?

    Réponse
    • 1000×3=30001000 \times 3 = 3000 bits sont nécessaires.
    • 30008=375\dfrac{3000}{8} = 375 octets sont nécessaires.

  3. Proposer un code de taille fixe pour chaque caractère de l’alphabet de 8 lettres.

    Réponse

    A : 000 ; B : 001 ; C : 010 ; D : 011 ; E : 100 ; F : 101 ; G : 110 et H : 111.

On considère maintenant le codage suivant, la longueur du code de chaque caractère étant variable.

Lettre A B C D E F G H
Code 10 001 000 1100 01 1101 1110 1111
Info

Ce type de code est dit préfixe, ce qui signifie qu’aucun code n’est le préfixe d’un autre (le code de A est 10 et aucun autre code ne commence par 10, le code de B est 001 et aucun autre code ne commence par 001). Cette propriété permet de séparer les caractères de manière non ambiguë.

  1. En utilisant la table précédente, donner le code du message : CACHE.

    Réponse

    CACHE : 00010000111101

  2. Quel est le message correspondant au code 001101100111001.

    Réponse

    001101100111001 : BADGE

Dans un texte, chacun des 8 caractères a un nombre d’apparitions différent. Cela est résumé dans le tableau suivant, construit à partir d’un texte de 1  000 caractères.

Lettre A B C D E F G H
Nombre 240 140 160 51 280 49 45 35
  1. En utilisant le code de taille fixe proposé à la question 3., quelle est la longueur en bits du message contenant les 1 000 caractères énumérés dans le tableau précédent ?

    Réponse

    Si on utilise 3 bits pour chaque caractère, il faut 1000×3=30001000 \times 3 = 3000 bits pour coder le message.

  2. En utilisant le code de la question 4., quelle est la longueur du même message en bits ?

    Réponse

    N=f(A)⋅l(A)+f(B)⋅l(B)+f(C)⋅l(C)+f(D)⋅l(D)+f(E)⋅l(E)+f(F)⋅l(F)+f(G)⋅l(G)+f(H)⋅l(H)N = f(A)\cdot l(A) + f(B)\cdot l(B) + f(C)\cdot l(C) + f(D)\cdot l(D) + f(E)\cdot l(E) + f(F)\cdot l(F) + f(G)\cdot l(G) + f(H)\cdot l(H) où f(xi)f(x_i) est la fréquence du caractère xix_i et l(xi)l(x_i) la longueur (en bits) du codage du caractère xix_i. A.N. N=240×2+140×3+160×3+51×4+280×2+49×4+45×4+35×4=2660N = 240 \times 2 + 140 \times 3 + 160 \times 3 + 51 \times 4 + 280 \times 2 + 49 \times 4 + 45 \times 4 + 35 \times 4 = 2660

Info

Ce type de codage réserve le codage le plus court aux caractères les plus fréquents.

Codage de Huffman

L’objectif du codage de Huffman est de trouver le codage proposé à la question 4.

Info

Le codage de Huffman minimise la taille en nombre de bits du message codé en se basant sur le nombre d’apparition de chaque caractère (un caractère qui apparaît souvent aura un code plutôt court).

  • Pour déterminer le code optimal, on considère 8 arbres, chacun réduit à une racine, contenant le symbole et son nombre d’apparitions.
graph TD
    A("A | 240")
    B("B | 140")
    C("C | 160")
    D("D | 51")
    E("E | 280")
    F("F | 49")
    G("G | 45")
    H("H | 35")
Info
  • On fusionne ensuite les deux arbres contenant les plus petits nombres d’apparitions (valeur inscrite sur la racine), et on affecte à ce nouvel arbre la somme des nombres d’apparitions de ses deux sous-arbres. Lors de la fusion des deux arbres, le choix de mettre l’un ou l’autre à gauche n’a pas d’importance. Nous choisissons ici de mettre le plus fréquent à gauche (s’il y a un cas d’égalité, nous faisons un choix arbitraire).
graph TD
    A("A | 240")
    B("B | 140")
    C("C | 160")
    D("D | 51")
    E("E | 280")
    F("F | 49")
    I("80") --> G
    I("80") --> H
    G("G | 45")
    H("H | 35")
Info
  • On recommence jusqu’à ce qu’il n’y ait plus qu’un seul arbre.

  1. Combien d’étapes (combien de fusions d’arbres) sont nécessaires pour que cet algorithme se termine ?

  2. En suivant l’algorithme précédent, construire l’arbre de Huffman.

Info

Le code à affecter à chaque lettre est déterminé par sa position dans l’arbre. Précisément, le code d’un symbole de l’alphabet décrit le chemin de la racine à la feuille qui le contient : un 0 indique qu’on descend par le fils gauche et un 1 indique qu’on descend par le fils droit.

graph TD
    A(" ") --> B(" ")
    B --> X("X")
    B --> Y("Y")
    A --> Z("Z")

Dans le cas de l’arbre ci-dessus le code de X est 00 (deux fois à gauche), le code de Y est 01, et celui de Z est 1.

  1. Sur chaque arête de l’arbre construit à la question 10., inscrire 0 ou 1 selon que l’arête joint un fils gauche ou un fils droit.

  2. Quel est le code de F ?

Le code suivant permet, à partir d’un fichier nommé texte.txt, de construire l’arbre de Huffman puis un dictionnaire qui associe à chaque caractère du fichier d’entrée son code sous forme d’une séquence de bits (liste de 0 et de 1).

Implémentation en Python de l’algorithme

  1. Écrire le code (et la spécification !) de la classe Noeud, nœud d’un arbre binaire. Par rapport à l’implémentation réalisée lors des TP précédenrs, ajouter le champ lettre initialisé à la chaîne de caractères vide et la méthode suivante :
def __lt__(self, n: Noeud):
    """
    Comparaison de deux noeuds = comparaison des valeurs
    """
    return self.valeur < n.valeur
Réponse
class Noeud:
    def __init__(self: Noeud, val: int, let: str = "") -> None:
        """
        Initialisation de l'objet.
        """
        self.valeur = val
        self.lettre = let
        self.gauche = None
        self.droit = None

    def __lt__(self: Noeud, n: Noeud) -> bool:
        """
        Comparaison de deux noeuds = comparaison des valeurs
        """
        return self.valeur < n.valeur
  1. Écrire les codes (et la spécification !) des fonctions est_vide, est_feuille, parcours_prefixe qui, respectivement teste si un nœud est vide, teste si un nœud est une feuille et finalement affiche l’arbre.

Réponse
def est_vide(n: Noeud) -> bool:
    """
    Détermine si l'arbre est vide.
    """
    return n is None


def est_feuille(n: Noeud) -> bool:
    """
    Détermine si le noeud est une feuille.
    """
    return (n.gauche is None) and (n.droit is None)


def parcours(n: Noeud) -> str:
    """
    Parcours en profondeur préfixe de l'arbre.
    """
    if n is None:
        return ""
    else:
        chaine = str(n.valeur)
        chaine += parcours(n.gauche)
        chaine += parcours(n.droit)
        return chaine
15. Écrire le code de la fonction creation_table_frequences dont la spécification est

def creation_table_frequences(message: str) -> dict[str, int]:
    """
    Établit la table des fréquences des caractères dans message.
    """

Tester la fonction avec l’instruction :

assert creation_table_frequences("ABRACADABRA") == {
    "A": 5,
    "B": 2,
    "R": 2,
    "C": 1,
    "D": 1,
}
Réponse
def creation_table_frequences(message: str) -> dict[str, int]:
    """
    Établit la table des fréquences des caractères dans message.
    """
    dic = {}
    for car in message:
        if car in dic.keys():
            dic[car] += 1
        else:
            dic[car] = 1
    return dic
  1. Lire le document sur les files de priorité.
    Écrire le code de la fonction construction_arbre_huffman dont la spécification est
def construction_arbre_huffman(dic_frequences: dict[str, int]) -> Noeud:
    """
    Construction de l'arbre de Huffman.
    """

et l’algorithme (cf. Cormen, Algorithmes)

Avertissement

Cet algorithme est un exemple d’algorithme glouton dans lequel on prend la décision qui semble la meilleure à un instant donné.

Réponse
def construction_arbre_huffman(dic_frequences: dict[str, int]) -> Noeud:
    """
    Construction de l'arbre de Huffman.
    """
    file = []

    # Création de tous les noeuds et insertion dans la file
    for lettre, frequence in dic_frequences.items():
        noeud = Noeud(frequence, lettre)
        heappush(file, noeud)

    # Construction de l'arbre
    for i in range(len(dic_frequences) - 1):
        noeud_droit = heappop(file)
        noeud_gauche = heappop(file)
        # Nouvel arbre
        nouvelle_valeur = noeud_droit.valeur + noeud_gauche.valeur
        noeud = Noeud(nouvelle_valeur)
        noeud.droit = noeud_droit
        noeud.gauche = noeud_gauche
        # Intégration à la file
        heappush(file, noeud)

    # Retour de l'arbre
    return heappop(file)
  1. Écrire une fonction nommée codes_huffman_parcours dont la spécification est :
def codes_huffman_parcours(a: Noeud, dic: dict[str, str], code: str) -> None:
    """
    Parcours de l'arbre et construction des codes et du dictionnaire passé en argument.
    Les lettres constituent les clés et les codes les valeurs.

    Algorithme récursif.
    """
Réponse
def codes_huffman_parcours(a: Noeud, dic: dict[str, str], code: str) -> None:
    """
    Parcours de l'arbre et construction des codes et du dictionnaire passé en argument.
    Les lettres constituent les clés et les codes les valeurs.

    Algorithme récursif.
    """
    if est_feuille(a):
        # Cas de base : on modifie le dictionnaire
        dic[a.lettre] = code
        return None
    else:
        codes_huffman_parcours(a.gauche, dic, code + "0")
        codes_huffman_parcours(a.droit, dic, code + "1")
  1. Écrire une fonction nommée encodage dont la spécification est :
def encodage(message: str, codes: dict[str, str]) -> str:
    """
    Retourne la chaîne de bits produite par le codage de Huffman pour la chaîne message.
    """
Réponse
def encodage(message: str, codes: dict[str, str]) -> str:
    """
    Retourne la chaîne de bits produite par le codage de Huffman pour la chaîne message.
    """
    message_code = ""
    for car in message:
        message_code += codes[car]
    return message_code
Avertissement

Il est impératif de savoir écrire le code de cette fonction !

  1. Écrire une fonction nommée decodage dont la spécification est :
def decodage(message_compresse: str, codes: dict[str, str]) -> str:
    """
    Retourne le message non compressé à partir du codage de Huffman.
    """
Réponse
def decodage(message_compresse: str, codes: dict[str, str]) -> str:
    """
    Retourne le message non compressé à partir du codage de Huffman.

    Étape intermédiaire : passer d'un dictionnaire 'A': '001' à
    '001' : 'A'
    """
    # Inversion clés - valeurs
    dic_inverse = {}
    for cle, valeur in codes.items():
        dic_inverse[valeur] = cle

    # Décodage
    resultat = ""
    code = ""
    for car in message_compresse:
        code += car
        if code in dic_inverse.keys():
            resultat += dic_inverse[code]
            code = ""
    return resultat
Avertissement

Il est impératif de savoir écrire le code de cette fonction !

Appels de toutes les fonctions dans la partie principale du programme

if __name__ == "__main__":
    arb = Noeud(12, "A")
    arb.gauche = Noeud(23, "B")
    arb.droit = Noeud(48, "C")
    arb.gauche.gauche = Noeud(49, "K")
    arb.droit.gauche = Noeud(9, "H")
    arb.droit.droit = Noeud(78, "X")

    print(parcours(arb))
    print(arb < Noeud(67, "E"))

    assert creation_table_frequences("ABRACADABRA") == {
        "A": 5,
        "B": 2,
        "R": 2,
        "C": 1,
        "D": 1,
    }

    message = "ABRACADABRA"

    # nom_fichier = "livre.txt"
    # with open(nom_fichier, 'r') as f:
    #    message = f.read()

    table_frequences = creation_table_frequences(message)
    arbre = construction_arbre_huffman(table_frequences)
    print(parcours(arbre))

    dic_codes = {}
    codes_huffman_parcours(arbre, dic_codes, "")
    print(dic_codes)

    message_code = encodage(message, dic_codes)
    print(message_code)
    message_decode = decodage(message_code, dic_codes)
    print(message_decode)