Aller au contenu

🎄Arbre⚓︎

Exemples introductifs⚓︎

Arbre syntaxique⚓︎

  • Une page web, un document xml, ou bien un programme informatique peut être représenté par un arbre.

expressioncorps_1Corpsaffectation_1Affectationcorps_1->affectation_1boucle_for_1Boucle forcorps_1->boucle_for_1Fonction printFonction printcorps_1->Fonction printy_1yaffectation_1->y_113371337affectation_1->1337iiboucle_for_1->irange_1Itérable rangeboucle_for_1->range_1corps_2Corpsboucle_for_1->corps_24242range_1->42affectation_2Affectationcorps_2->affectation_2y_2yaffectation_2->y_2××affectation_2->×y_3y×->y_322×->2yyFonction print->y

Cet arbre pourrait représenter le programme suivant :

🐍 Script Python
y = 1337
for i in range(42):
    y = y * 2
print(y)

L'interpréteur Python, quand il lit un programme, commence par le traduire en arbre syntaxique en suivant la grammaire du langage. Il peut détecter à cette occasion une erreur de syntaxe avant même le début de l'exécution du programme.

Exercice 1

Chercher lesquels parmi les formats de fichiers suivants peuvent être lus et représentés par un arbre syntaxique.

  • Fichier document (.odt)
  • Fichier image vectorielle (.svg)
  • Fichier web (.html)
  • Fichier image matricielle (.jpg)

Expression littérale⚓︎

expressionNil_1nilNil_2nilNil_3nilNil_4nilNil_5nilNil_6nilNil_7nilNil_8nilNil_9nil++××+->×÷÷+->÷--×->-yy×->yxx÷->x22÷->2-->Nil_133-->33->Nil_23->Nil_3y->Nil_4y->Nil_5x->Nil_6x->Nil_72->Nil_82->Nil_9

Cet arbre binaire est une représentation de l'expression \(-3y + \frac x 2\).

Exercice 2

Dessiner un arbre représentant l'expression \((-x+7)×(y-2) + (5-x^2)\).

On pourra ne pas dessiner nil.

Définitions⚓︎

Arbre enraciné⚓︎

Nœud⚓︎

Un nœud contient

  • Un élément
  • et des enfants (qui sont d'autres nœuds : zéro, un ou plusieurs).

Arbre enraciné⚓︎

Un arbre enraciné est un ensemble fini non vide de nœuds, avec un nœud en particulier : la racine de l'arbre. Les nœuds sont organisés de manière hiérarchique dans un graphe :

  • Tout nœud est issu de la racine ; le graphe est connexe (il est d'un seul tenant).
  • Un nœud ne possède qu'un seul parent ; le graphe est sans cycle (pas de boucle).

Arbre binaire⚓︎

Nœud⚓︎

Dans un arbre binaire, un nœud contient un élément et deux enfants, qui sont d'autres arbres binaires.

Dans l'exemple précédent, +, ×, 3, x, et les autres sont des nœuds, sauf les nil qui représentent l'absence de nœud.

Arbre binaire⚓︎

Un arbre binaire est un ensemble fini de nœuds qui ont exactement deux enfants, un à gauche, un à droite ; les enfants sont des nœuds ou éventuellement nil (une absence de nœud) et que l'on pourra alors omettre.

Une définition récursive est alors :

  • Un arbre binaire peut avoir zéro nœud, il est alors vide, on le note nil.
  • Un arbre binaire non vide possède un nœud particulier, sa racine, et deux enfants, un à gauche et un à droite, qui sont des arbres binaires.

Exemple

L'arbre binaire ci-dessous est un sous-arbre de l'exemple précédent. On a, cette fois, omis les nil.

expression÷÷xx÷->x22÷->2

Les arbres binaires sont presque des cas particuliers d'arbres enracinés.

  • Un arbre binaire peut être vide, mais pas un arbre enraciné.
  • Sinon, un arbre binaire non vide est un exemple d'arbre enraciné.

Un arbre binaire est aussi un graphe connexe, sans cycle.

Feuille⚓︎

  • Pour un arbre enraciné, une feuille est un nœud sans enfant.
  • Pour un arbre binaire, une feuille est un nœud qui possède deux sous-arbres vides.

Les feuilles sont les extrémités de l'arbre.

Dans le premier exemple, 3, y, x, et 2 sont des feuilles.

Taille d'un arbre⚓︎

La taille d'un arbre est son nombre de nœuds.

L'exemple de l'arbre de l'expression littérale est un arbre de taille \(8\), dont \(4\) feuilles. (Il y a donc \(8-4\) nœuds intérieurs.)

Hauteur d'un arbre⚓︎

Définition variable

⚠ La définition de hauteur n'est pas la même partout. Vérifier celle du document que vous lisez.

  • Un arbre vide a une hauteur nulle.
  • La hauteur d'un arbre non vide est le nombre maximal de nœuds de la racine jusqu'à une feuille. C'est aussi le nombre maximal de liens pour joindre la racine à nil.

L'arbre suivant est de hauteur \(4\) ; la branche la plus profonde possède les nœuds +, ×, -, 3.

expressionNil_1nilNil_2nilNil_3nilNil_4nilNil_5nilNil_6nilNil_7nilNil_8nilNil_9nil++××+->×÷÷+->÷--×->-yy×->yxx÷->x22÷->2-->Nil_133-->33->Nil_23->Nil_3y->Nil_4y->Nil_5x->Nil_6x->Nil_72->Nil_82->Nil_9

Dans l'autre définition très commune, un arbre vide a pour hauteur \(-1\), et s'il est non vide, c'est le nombre maximal de liens pour joindre la racine à une feuille.

Quelle importance ?

Même si l'autre définition est assez répandue, nous préfèrerons la définition où l'arbre vide est de hauteur nulle. Cette définition et l'autre ne diffère que de \(1\).

La hauteur \(h\) est une notion importante pour le calcul de la complexité d'un algorithme. De nombreux algorithmes ont une complexité en \(\mathcal O(h)\), et ainsi, un décalage de \(1\) dans la définition est absolument sans importance.

Arbre peigne⚓︎

Un arbre binaire peigne est un cas particulier extrême d'arbre binaire, tous les nœuds intérieurs ont un seul enfant qui est non vide, et toujours du même côté. Techniquement, c'est une liste chainée.

expressionArbre peigne gauche de hauteur 4010->11d0->1d21->22d1->2d32->33d2->3d43->44d3->4d

Un arbre peigne montre une situation extrême où certains algorithmes sur les arbres que nous verrons ne seront pas efficaces. Avec un arbre peigne, la hauteur est égale à la taille ; on ne peut pas obtenir une plus grande hauteur à taille fixée.

Arbre parfait⚓︎

Un arbre binaire parfait possède des nœuds intérieurs qui ont tous exactement deux enfants non vides. C'est l'arbre idéal pour certains algorithmes... Une taille maximale pour une hauteur minimale.

expressionArbre parfait de hauteur 3121->231->342->452->563->673->784->894->9105->10115->11126->12136->13147->14157->15

Arbre équilibré⚓︎

Un arbre binaire est équilibré si pour chaque nœud, son sous-arbre gauche et son sous-arbre droit ont une hauteur qui ne diffère que de \(1\) au plus.

Autres façons de le voir

Un arbre est équilibré quand tous les nœuds intérieurs ont deux enfants non vides, sauf les plus éloignés.

Un arbre équilibré peut devenir parfait uniquement en complétant avec des feuilles au dernier niveau.

expressionArbre équilibré121->231->342->452->563->673->784->894->9126->12136->13147->14157->15

Arbre presque complet (à gauche)⚓︎

Un arbre binaire est presque complet (à gauche) s'il est équilibré et qu'à la profondeur maximale les feuilles sont entassées du même côté (à gauche).

expressionArbre presque complet121->231->342->452->563->673->784->894->9105->10115->11

⚠ les définitions de (presque) complet et équilibré varient parfois, de même en anglais. Vérifier avec le document que vous utilisez.

Représentation en Python⚓︎

Prenons par exemple, l'expression numérique \(A = 6×5 - (3+(7+6))\) qui peut être représentée par l'arbre binaire suivant. (nil non dessinés.)

expressionsix_16--××-->×+_1+-->+_1×->six_155×->533+_1->3+++_1->+77+->7six_26+->six_2

Avec un tuple à trois éléments⚓︎

Un arbre binaire peut être représenté par un ensemble de nœuds de la forme (enfant_gauche, élément, enfant_droit) et avec None pour désigner nil.

Notre exemple peut être alors représenté par :

🐍 Script Python
six_1 = (None, "6", None)
cinq_1 = (None, "5", None)
produit_1 = (six_1, "×", cinq_1)

trois_1 = (None, "3", None)

sept_1 = (None, "7", None)
six_2 = (None, "6", None)
somme_1 = (sept_1, "+", six_2)

somme_2 = (trois_1, "+", somme_1)
expr_A = (produit_1, "-", somme_2)

Remarque

On notera la numérotation des nœuds afin d'avoir deux nœuds étiquetés "six_?" différents. De même, plusieurs sommes le composent, l'objectif étant de sécuriser l'éventuel partage de données, même si c'est possible en faisant très attention...

Avec cette représentation on peut donner le code de certaines fonctions.

🐍 Script Python
def est_vide(arbre):
    return arbre is None

def somme(arbre):
    """On suppose ici que l'arbre binaire ne comporte
    que des valeurs numériques.
    """
    if est_vide(arbre):
        return 0
    else:
        # la somme du sous arbre gauche : somme(arbre[0])
        # la valeur de l'élément du nœud : arbre[1]
        # la somme du sous arbre droite : somme(arbre[2])
        return somme(arbre[0]) + arbre[1] + somme(arbre[2])

def taille(arbre):
    if est_vide(arbre):
        return 0
    else:
        return taille(arbre[0]) + 1 + taille(arbre[2])

def hauteur(arbre):
    if est_vide(arbre):
        return 0
    else:
        return 1 + max(hauteur(arbre[0]), hauteur(arbre[2]))

def est_peigne_gauche(arbre):
    if est_vide(arbre):
        return True
    else:
        return est_vide(arbre[2]) and est_peigne_gauche(arbre[0])
    # variante une ligne
    return est_vide(arbre) or (est_vide(arbre[2])
                               and est_peigne_gauche(arbre[0]))
    # l'évaluation paresseuse permet de rester efficace,
    # on traîte le cas difficile en dernier !


if __name__ == '__main__':
    # test
    six_1 = (None, "6", None)
    cinq_1 = (None, "5", None)
    produit_1 = (six_1, "×", cinq_1)

    trois_1 = (None, "3", None)

    sept_1 = (None, "7", None)
    six_2 = (None, "6", None)
    somme_1 = (sept_1, "+", six_2)

    somme_2 = (trois_1, "+", somme_1)
    expr_A = (produit_1, "-", somme_2)

    assert taille(expr_A) == 9
    assert hauteur(expr_A) == 4, hauteur(expr_A)

    assert not est_peigne_gauche(expr_A) # Il y a un not !!!
    assert est_peigne_gauche(trois_1) # comme toute feuille

On remarquera que ce code est bien moins lisible que les suivants. Nous n'utiliserons plus les tuples avec les indices pour accéder aux champs de données !

Avec une classe Nœud⚓︎

🐍 Script Python
class Nœud:
    def __init__(self, gauche, élément, droite):
        self.gauche = gauche
        self.élément = élément
        self.droite = droite


def est_vide(arbre):
    return arbre is None

def somme(arbre):
    """On suppose ici que l'arbre binaire ne comporte
    que des valeurs numériques.
    """
    if est_vide(arbre):
        return 0
    else:
        return somme(arbre.gauche) + arbre.élément + somme(arbre.droite)

def taille(arbre):
    if est_vide(arbre):
        return 0
    else:
        return taille(arbre.gauche) + 1 + taille(arbre.droite)

def hauteur(arbre):
    if est_vide(arbre):
        return 0
    else:
        return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droite))

def est_peigne_gauche(arbre):
    if est_vide(arbre):
        return True
    else:
        return est_vide(arbre.droite) and est_peigne_gauche(arbre.gauche)
    # variante une ligne
    return est_vide(arbre) or (est_vide(arbre.droite)
                               and est_peigne_gauche(arbre.gauche))
    # l'évaluation paresseuse permet de rester efficace,
    # on traîte le cas difficile en dernier !

if __name__ == '__main__':
    # test
    six_1 = Nœud(None, "6", None)
    cinq_1 = Nœud(None, "5", None)
    produit_1 = Nœud(six_1, "×", cinq_1)

    trois_1 = Nœud(None, "3", None)

    sept_1 = Nœud(None, "7", None)
    six_2 = Nœud(None, "6", None)
    somme_1 = Nœud(sept_1, "+", six_2)

    somme_2 = Nœud(trois_1, "+", somme_1)
    expr_A = Nœud(produit_1, "-", somme_2)

    assert taille(expr_A) == 9
    assert hauteur(expr_A) == 4, hauteur(expr_A)

    assert not est_peigne_gauche(expr_A) # Il y a un not !!!
    assert est_peigne_gauche(trois_1) # comme toute feuille

On remarque un code bien plus lisible et extensible à volonté. Très bon choix.

Avec un tuple nommé⚓︎

Le type tuple nommé est peu connu en Python, c'est pourtant un type recommandé au sein du programme de NSI ; il permet d'avoir la légèreté du tuple en ayant une part de l'expressivité de la POO.

Lire la documentation officielle ; On constatera ici, qu'après la redéfinition de Nœud, la suite du code est inchangée !

🐍 Script Python
import collections
Nœud = collections.namedtuple('Nœud', ['gauche', 'élément', 'droite'])


def est_vide(arbre):
    return arbre is None

def somme(arbre):
    """On suppose ici que l'arbre binaire ne comporte
    que des valeurs numériques."""
    if est_vide(arbre):
        return 0
    else:
        return somme(arbre.gauche) + arbre.élément + somme(arbre.droite)

def taille(arbre):
    if est_vide(arbre):
        return 0
    else:
        return taille(arbre.gauche) + 1 + taille(arbre.droite)

def hauteur(arbre):
    if est_vide(arbre):
        return 0
    else:
        return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droite))

def est_peigne_gauche(arbre):
    if est_vide(arbre):
        return True
    else:
        return est_vide(arbre.droite) and est_peigne_gauche(arbre.gauche)
    # variante une ligne
    return est_vide(arbre) or (est_vide(arbre.droite)
                               and est_peigne_gauche(arbre.gauche))
    # l'évaluation paresseuse permet de rester efficace,
    # on traîte le cas difficile en dernier !

if __name__ == '__main__':
    # test
    six_1 = Nœud(None, "6", None)
    cinq_1 = Nœud(None, "5", None)
    produit_1 = Nœud(six_1, "×", cinq_1)

    trois_1 = Nœud(None, "3", None)

    sept_1 = Nœud(None, "7", None)
    six_2 = Nœud(None, "6", None)
    somme_1 = Nœud(sept_1, "+", six_2)

    somme_2 = Nœud(trois_1, "+", somme_1)
    expr_A = Nœud(produit_1, "-", somme_2)

    assert taille(expr_A) == 9
    assert hauteur(expr_A) == 4, hauteur(expr_A)

    assert not est_peigne_gauche(expr_A) # Il y a un not !!!
    assert est_peigne_gauche(trois_1) # comme toute feuille

On remarque un code aussi clair, moins extensible, mais plus léger en empreinte mémoire. À utiliser en cas de volonté d'optimisation temporelle, mais surtout mémoire. (Ou alors pour préparer une initiation à la POO ???)

Nous utiliserons la POO pour la suite, pour sa lisibilité, son extensibilité. Nous ne cherchons pas ici les performances.

Parcours en profondeur d'un arbre binaire⚓︎

Question motivante

Les fonctions que nous avons découvertes utilisaient des opérateurs commutatifs, en effet on a

  • max(a, b) == max(b, a) et
  • 1 + x + y == x + 1 + y == x + y + 1.

Mais que se passe-t-il avec des fonctions non commutatives ?

Si on conserve une action à gauche avant celle de droite, alors il reste trois positions pour appliquer l'action sur le nœud en cours.

  • On fait l'action sur le nœud,
  • puis l'action sur le sous arbre gauche,
  • puis l'action sur le sous arbre droite.
  • On fait l'action sur le sous arbre gauche,
  • puis l'action sur le nœud,
  • puis l'action sur le sous arbre droite.
  • On fait l'action sur le sous arbre gauche,
  • puis l'action sur le sous arbre droite.
  • puis l'action sur le nœud.

Exercice 3

Appliquer les fonctions suivantes. Vous ferez sur papier les parcours avec action définie comme « afficher le nœud en cours », sur l'arbre de notre exemple.

🐍 Script Python
def parcours_préfixe(arbre, action):
    if not est_vide(arbre):
        action(arbre)
        parcours_préfixe(arbre.gauche)
        parcours_préfixe(arbre.droite)

def parcours_infixe(arbre, action):
    if not est_vide(arbre):
        parcours_infixe(arbre.gauche)
        action(arbre)
        parcours_infixe(arbre.droite)

def parcours_postfixe(arbre, action):
    if not est_vide(arbre):
        parcours_postfixe(arbre.gauche)
        parcours_postfixe(arbre.droite)
        action(arbre)

Humour

Ceci est un dessin humoristique lié aux parcours d'arbre.

https://xkcd.com/2407/

Exercices sur les arbres binaires⚓︎

Exercice 4 - Dessiner des arbres

Dessiner à la main tous les arbres binaires ayant trois ou quatre nœuds.

Exercice 5 - Dénombrement des arbres binaires

  • Il y a \(1\) arbre binaire ayant \(0\) nœud, l'arbre vide.
  • Il y a \(1\) arbre binaire ayant \(1\) nœud.
  • Il y a \(2\) arbres binaires ayant \(2\) nœuds.
  • Il y a \(5\) arbres binaires ayant \(3\) nœuds.
  • Il y a \(14\) arbres binaires ayant \(4\) nœuds.

Combien y a-t-il d'arbres binaires ayant \(5\) nœuds. (Ne pas tous les dessiner ; trouver juste le moyen de tous les dénombrer.)

Exercice 6 - Parcours infixe

On considère l'arbre binaire suivant :

expressionexemple_6AABBA->BDDA->DBgB->BgCCB->CDgD->DgDdD->DdCgC->CgCdC->Cd

  1. Construire sa représentation interne en Python à l'aide de la classe Nœud.
  2. Écrire une fonction affichage définie par :
    • sur un arbre vide, ne rien faire ;
    • sur un arbre non vide,
      • afficher (, puis
      • afficher (récursivement) le sous-arbre gauche, puis
      • afficher la racine, puis
      • afficher (récursivement) le sous-arbre droite, puis
      • afficher )
  3. Vérifier que affichage(exemple_6) produit '((B(C))A(D))'.
  4. Dessiner un arbre dont affichage(arbre) produit '(1((2)3))'.
  5. De manière générale, expliquer comment retrouver un arbre dont l'affichage est donné.

Exercice 7 - Parcours en largeur

  • Pour afficher (ou faire une autre action) un arbre avec un parcours en largeur :
    • On utilise une file initialement vide.
    • On enfile l'arbre (son nœud racine, ou nil) dans la file.
    • Tant que la file est non vide :
      • On défile un arbre.
      • S'il n'est pas nil, c'est un nœud et :
        • On affiche (ou on traite suivant une action) l'élément du nœud.
        • On enfile le sous-arbre gauche (puis droit).
  • Écrire une fonction de parcours en largeur.
  • Tester votre fonction.
  • Vérifier qu'elle consiste à lire l'arbre étage par étage en commençant par la racine, puis de gauche à droite pour chaque étage.
  • Modifier votre fonction pour qu'une étiquette soit affichée avec son niveau. La racine est au niveau 0.
Réponse
🐍 Script Python
# On suppose que l'on dispose d'une classe File
# avec les méthodes enfile et défile.

def parcours_largeur(arbre):
    suite = File()
    suite.enfile(arbre)
    while not suite.est_vide():
        nœud = suite.défile()
        if nœud is not None:
            print(nœud.élément)
            suite.enfile(nœud.gauche)
            suite.enfile(nœud.droite)

def parcours_largeur(arbre):
    # Avec les niveaux
    suite = File()
    suite.enfile((arbre, 0))
    while not suite.est_vide():
        nœud, niveau = suite.défile()
        if nœud is not None:
            print(nœud.élément, niveau)
            suite.enfile((nœud.gauche, niveau + 1))
            suite.enfile((nœud.droite, niveau + 1))

Exercice 8 - Reconstruire un arbre

Un arbre binaire est étiqueté avec des lettres.

  • Un parcours préfixe donne un affichage ALORHGIMET.
  • Un parcours infixe donne un affichage OLHRAMIEGT.

  • Reconstruire l'arbre qui a produit ces affichages.

  • Qu'obtient-on avec un parcours en largeur ?
  • Qu'obtient-on avec un parcours postfixe ?
Réponse
  1. Le parcours préfixe commence par un A, donc la racine est étiquetée A. Il n'y a qu'un seul A, on déduit alors aussi que :

    • Le sous-arbre gauche est composé des étiquettes OLHR en infixe, et donc LORH en préfixe.
    • Le sous-arbre droite est composé des étiquettes MIEGT en infixe, et donc GIMET en préfixe.
  2. La racine du sous arbre gauche est donc L, et G à droite.

    • Sous-arbre gauche :
      • Son sous-arbre gauche : O en préfixe comme en infixe.
      • Son sous-arbre droite : RH en préfixe et HR en infixe.
    • Sous-arbre droite :
      • Son sous-arbre gauche : IME en préfixe et MIE en infixe.
      • Son sous-arbre droite : T en préfixe comme en infixe.
  3. On déduit ensuite que le parcours en largeur est ALGORITHME.