Les Arbres en NSI

Avertissement

Cet article n'est pas un cours sur les arbres. Son contenu n'est pas montrable directement aux élèves, ne serait-ce que pour les définitions de D. Knuth laissées sous leurs formes originales, en anglais.

Il s'agit d'une réflexion sur quelques définitions et implémentations trouvées dans des ressources officielles et dans un livre référence (on peut ne pas être d'accord avec tout ce que dit D. Knuth mais on ne peut nier qu'il s'agit d'une référence internationale en Informatique et en Algorithmique en particulier).

Cet article donne des définitions formelles d'arbre. Mais doit-on le faire dans un cours de NSI ? Ou préfère-t-on donner une définition informelle et quelques exemples pour que l'élève ait une idée suffisamment claire de ce qu'est un arbre, et profiter de cette introduction informelle pour introduire les termes nœud, feuille, racine, branche, chemin etc.

Chaque enseignant.e à sa réponse et c'est très bien comme ça.

L'article n'aborde pas certains points, comme par exemple le lien entre la hauteur et la taille d'un arbre binaire. Pourtant cette question est souvent traités dans les sujets. Mais l'article est déjà assez long et cette double inégalité ne pose pas de souci particulier.

I. Introduction

Le concept d'arbre est mentionné à deux endroits dans le programme de Tle NSI :

Structures de données

Contenus	Capacités attendues	Commentaires
Arbres : structures hiérarchiques Arbres binaires : nœuds, racines, feuilles, sous-arbre gauche, sous-arbre droit	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 ».

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.

D'autre part, on retrouve ce thème très souvent dans les sujets de l'écrit du Bac (6 exercices en 2021 et 9 en 2022). Mais lorsqu'on regarde les cours de collègues et les sujets du Bac, on se rend compte d'une grande diversité à la fois sur le vocabulaire employé, les définitions et les implémentations.

Dans cet article, nous revenons sur les définitions, en particulier nous mettons en parallèle ce que propose le site officiel d'Éduscol et les définitions de D. E. Knuth. Nous traitons plus avant les arbres binaires et les arbres binaires de recherche pour lesquels nous donnons une implémentation à l'aide de classes à fois simple et cohérente.

Nous terminons par quelques exemples d'exercices donnés à l'épreuve écrite du Bac.

Dans la suite de l'article nous utilisons des encadrés colorés pour guider le lecteur sur la pertinence des contenus dans le programme NSI :

Les encadrés rouge

Dans ces encadrés nous donnons des contenus (définitions ou implémentations) qui, pour une raison ou pour une autre devraient être évités en NSI. Par exemple parce que trop compliqué.

Les encadrés vert

Pour du contenu adapté à un niveau Tle NSI.

Les encadrés exemples

Neutres, ces encadrés ne font que présenter des exemples.

Les encadrés remarques

Relativement neutre, ils attirent l'attention sur un point particulier ou un complément d'information.

II. Exemples

Commençons par présenter quelques exemples où une structure arborescente semble se dessiner. Les termes sont ici employés de façon tout à fait informel, d'où l'usage de l'italique. Ces exemples sont bien souvent présents dans les introductions des cours de NSI des collègues.

Exemple 1. Une arborescence de fichiers

Voici ce qu'affiche la commande Unix tree (il s'agit ici d'un partie du répertoire mkdocs pour la construction de ce site) :

.
├── docs
│   ├── 01_Graphes
│   │   ├── agreg_2022_sujet0_ep2.ipynb
│   │   ├── coloration.md
│   │   ├── extrait
│   │   ├── index.md
│   ├── 02_Dessins
│   ├── 03_Didactique
│   ├── assets
│   ├── downloads
│   ├── includes
│   ├── index.md
│   ├── javascripts
│   └── stylesheets
├── main.py
├── mkdocs.yml
└── overrides

Exemple 2. Un arbre syntaxique

Le Document Object Model est la modélisation d'un document HTML manipulée par le navigateur, il s'agit d'un exemple d'arbre syntaxique. Considérons le petit document HTML ci-dessous :

<html lang="fr">
    <head>
        <meta charset="UTF-8">
        <title>Exemple</title>
    </head>
    <body>
        <h1>Un titre</h1>
        <p>Bonjour !</p>
        <table>
            <tr>
                <td>Case 1</td>
                <td>Case 2</td>
            </tr>
        </table>
    </body>
</html>

Voici le DOM associé :

Exemple emprunté à [Nativel2022]

Exemple 3. L'arbre d'une expression littérale

L'expression littérale suivante :

\[-3y + \frac{x}{2}\]

Donne l'arbre suivant :

Exemple emprunté à [Chambon2022]

Exemple 4. Un arbre généalogique

Cet exemple est intéressant puisque justement, formellement, nous verrons que les arbres généalogiques ne sont en réalité pas des arbres au sens informatique du terme¹.

Ci-dessous les ancêtres d'un certain Antoine de Gargan :

Exemple emprunté à [Progalgo2022], l'image est extraite de wikimédia : Antoine de Gragan

Exemple 5. L'arbre des configurations d'un jeu

Là encore, il ne s'agit pas tout à fait d'un arbre, mais plutôt d'un graphe : un nœud pouvant avoir plusieurs parents.

Exemple emprunté à [Progalgo2022]

Exemple 6. Les arbres de suffixes/préfixes

Cette structure permet de manipuler efficacement de très longues chaines de caractères (voir par exemple [Knuth1968]). Elle est à la base de structures comme les tries utilisées en bio-informatique.

III. Définitions

Arbre

Le site Éduscol propose trois ressources sur le thème des arbres :

• Arbres binaires de recherche [Eduscol2021a]
• Implémentation des arbres binaires de recherche à l'aide de la POO [Eduscol2021b]
• Généralités sur les arbres [Eduscol2021c] c'est dans ce dernier document qu'on trouve les définitions.

Arbre libre -- [Eduscol2021c]

On appelle arbre libre un graphe \(A\) non orienté, connexe et acyclique.

Cette définition est à rapprocher de celle de D. Knuth [Knuth1997] :

Free tree -- [Knuth1997]

A free tree or "unrooted tree" is defined to be a connected graph with no cycles.

Ces définitions viennent de la théorie des graphes. Elles sont intéressantes mais le thème graphe ne faisant pas partie des entrées prépondérantes (voir [DGESCO2021]), présenter les arbres sous cet angle n'a que peu d'intérêt en NSI.

On gardera par contre les définitions de nœud et de taille :

nœud, taille -- [Eduscol2021c]

Les sommets de \(A\) sont communément appelés nœuds. Le nombre de nœuds est appelé la taille de \(A\).

La vision structure de données des arbres est celle évoquée dans le programme de NSI il s'agit en fait de la notion d'arbre enraciné (néanmoins, on pourra abandonner le qualificatif enraciné, c'est ce que font d'ailleurs Éduscol et D. Knuth). La définition proposée par Éduscol manque de précision :

Arbre (enraciné), racine -- [Eduscol2021c]

On appelle arbre enraciné, ou tout simplement arbre, un arbre libre dans lequel l'un des sommets se distingue des autres. Ce sommet particulier est appelé racine de l'arbre.

Cette définition nous semble incomplète, on n'y parle pas de sous-arbre ni de ce que deviennent les autres sommets. Le document Éduscol continue par le concept de dessin d'un arbre. Nous reviendrons plus tard sur la représentation graphique.

Nous lui préférons celle de [Knuth1997] qui dans sa version originale ne passe pas (encadré rouge) :

Tree, root, subtree

A tree is a finite set \(T\) of one or more nodes such that :

1. there is one specially designated node called the root of the tree ;
2. the remaining nodes (excluding the root) are partitionned into \(m\geq 0\) disjoint sets \(T_1,\ldots,T_m\) and each of these sets in turn is a tree. The trees \(T_1,\ldots,T_m\) are called the subtrees of the root.

Mais qui, adapté en français avec une notation moins mathématique et l'introduction de la notion d'organisation hiérarchique donne :

Arbre, racine, sous-arbre

Un arbre \(A\) est un ensemble fini de un ou plusieurs nœuds organisés de façon hiérarchique :

1. un nœud spécial est désigné comme la racine de \(A\) ;
2. les autres sont organisés dans plusieurs (éventuellement aucun) arbres disjoints qui sont les sous-arbres de \(A\).

[Eduscol2021c] propose aussi une définition récursive similaire qu'il semble plus opportun d'utiliser dans le cadre NSI :

Définition récursive d'arbre

Il est souvent utile de voir un arbre (enraciné) comme une structure de données récursive :

• cas de base : un nœud unique \(r\) est un arbre de racine \(r\) ;
• récurrence : un arbre avec au moins deux nœuds est constitué d'une racine \(r\) et d'une suite de sous-arbres \(A_1,\ldots, A_k\) dont les racines \(r_1,\ldots, r_k\) sont les successeurs de \(r\).

On constate qu'en plus de la notion d'arbre, apparait celle de nœud ou sommet. Cet élément constitutif des arbres facilite les descriptions et preuves algorithmiques. Néanmoins, nous verrons aussi que lors des implémentations l'existence des deux objets peut conduire à des complications.

Remarque

Attention les définitions ci-dessus sont quand même très mathématiques dans leurs notations. En fonction du contexte il pourrait être judicieux de ne pas en parler aux élèves et rester sur une définition informelle, accompagnée d'exemples.

Sous-arbre, ancêtre, descendant etc.

L'avantage de la définition de D. Knuth c'est qu'elle introduit aussi celle de sous-arbre (de façon récursive). Éduscol doit définir les sous-arbres d'un arbre comme les arbres induit par les descendants de la racine de l'arbre.

Dans les définitions des relations entre les nœuds, on ne parle plus d'arbre, mais bien que des nœuds. Ainsi, si on part de la racine d'un arbre, les nœuds qui lui sont rattachés sont des enfants (ou fils ; on trouve les deux terminologies). La relation duale est celle de parent (ou père). Deux nœuds qui partagent le même parent sont frères.

Un nœud sans enfant est appelé feuille (ou nœud externe). Les autres sont des nœuds internes.

Les ancêtres d'un nœud \(x\) sont tous les nœuds exceptés \(x\) lui-même du chemin simple (au sens la plus direct possible) qui va de la racine à \(x\). De façon duale, les descendants d'un nœuds sont tous les nœuds dont \(x\) est l'ancêtre.

Niveau, hauteur, profondeur

Ces définitions sont explicitement au programme, elles font souvent l'objet de questions à l'épreuve du Bac.

Définitions -- [Eduscol2021c]

Soit \(A\) un arbre de racine \(r\), On appelle :

• profondeur d'un nœud \(n\) la longueur du chemin simple (soit le nombre d'arêtes) entre \(r\) et \(n\) ;
• niveau l'ensemble de tous les nœuds de même profondeur ;

La définition de hauteur nous pose problème :

Double définition de hauteur selon [Eduscol2021c]

• la hauteur d'un nœud \(n\) est la longueur du chemin simple le plus long qui relie \(n\) à une feuille dont il est l'ancêtre ;
• la hauteur de \(A\) la hauteur de sa racine \(r\)

Mais cette définition de hauteur donnée par Éduscol n'est pas satisfaisante pour deux raisons :

• Elle oblige à définir deux notions : la hauteur d'un nœud (qui est pour le moins étrange) et la hauteur d'un arbre
• Elle ne fait pas état des deux définitions possibles (et que l'ont trouve effectivement dans les sujets ou les divers cours sur les arbres)

Définitions de la hauteur d'un arbre

Pour définir la hauteur d'un arbre, on considère le plus long chemin simple allant de la racine à une feuille. Dès lors, une définition consiste à compter le nombre de nœuds de ce chemin ; tandis que l'autre s'intéresse au nombre d'arêtes.

Note : Cela ne fait qu'une différence de \(1\) et les sujets d'examens préciseront toujours la définition adoptée.

Hauteurs de l'exemple 3

Si on considère l'arbre de l'exemple 3, sa hauteur est \(3\) si on compte les arêtes et \(4\) si on compte les nœuds.

La hauteur de l'arbre vide

Il faudrait, pour compléter ce point sur la hauteur, parler de la hauteur de l'arbre vide. Puisque dans les faits, le calcul de la hauteur sera récursif avec comme cas de base l'arbre vide justement. Suivant le choix fait (comptage des nœuds ou comptage de arêtes) cette hauteur de base est \(0\) ou \(-1\).

Une hauteur de \(-1\) est difficile à concevoir. La justification pourrait se faire en parlant d'abord de la hauteur d'un arbre réduit à sa racine :

• si on compte les nœuds c'est clairement \(1\)
• si on compte les arêtes, il n'y en a pas donc c'est clairement \(0\)

Si on admet que pour l'arbre vide la hauteur doit être \(1\) de moins que pour l'arbre possédant un nœud unique alors naturellement on obtient \(0\) et \(-1\).

IV. Représentations

Si on rapproche les concepts d'arbre et de racine informatiques à leurs homologues du monde réel alors tout naturellement la représentation qui nous vient est celle où la racine est en bas :

Représentation montante d'un arbre

graph TD G(("G")) --- F(("F")) D(("D")) --- C(("C")) E(("E")) --- C F --- C B(("B")) --- A(("A")) C --- A

Cette représentation est utilisée dans l'arbre généalogique de l'exemple 4. Dans son livre, D. Knuth [Knuth1997] consacre plusieurs pages à la représentation des arbres. On y trouve notamment des représentations horizontales (gauche-droite ou droite-gauche) comme celle utilisée dans l'exemple 1 de l'arborescence de fichier affichée par la commande tree.

L'auteur présente d'autres formes de représentations plus exotiques :

Exemple 7. Quelques représentations exotiques

L'auteur reconnait que dans 80% des cas les arbres sont représentés dans les ouvrages avec la racine en haut (c'est le cas des exemples 2, 3, 5 et 6 de l'introduction). Une des raisons est bien sûr le sens descendant de notre processus de rédaction.

Cette différence avec les vrais arbres donne lieu à des blagues d'informaticien :

Finally after years of search I found a real tree

Emprunté à [Lassus2022]

V. Arbre binaire, Arbre binaire de recherche (ABR)

Les arbres quelconques sont assez peu exploités en NSI, où le focus est fait sur les arbres binaires et les arbres binaires de recherche.

Eduscol ne donne aucune définition d'arbre binaire, considérant probablement qu'il s'agit d'un cas particulier d'arbre. Ce n'est pas l'avis de D. Knuth qui définit les arbres binaires :

Arbre binaire -- [Knuth1997]

A binary tree is a finite set of nodes that either is empty, or consists of a root and the elements of two disjoint binary trees called the left and right subtrees of the root.

Et l'auteur précise quelques lignes plus loin :

D. Knuth

Notice that a binary tree is not a special case of a tree.

En effet, contrairement aux arbres, les arbres binaires peuvent être vides (et nous verrons que cette particularité va nous faciliter la vie lors de l'implémentation).

Si on considère les deux arbres suivants :

Exemple 8. Deux arbres binaires

\(\quad\)

En tant qu'arbres binaires ils sont bien différents : l'un possède un sous-arbre gauche vide. Mais si on les considère comme des arbres, ils sont identiques.

Remarque

Avant de poursuivre sur les arbres binaires de recherche, revenons sur le nom donné aux sous-arbres.

Concernant les noms des attributs on trouve :

• fils_gauche, fils_droit qui semblent trop genrés
• sous_arbre_gauche, sous_arbre_droit trop longs
• gauche, droit seraient de bons candidats... mais droit ou droite ? Le plus répandu est droit et l'argument avancé est : "comme on dit le bras droit", sauf que lorsqu'on désigne le bras droit d'un individu, on parle du bras qui se trouve à la droite de l'individu. Hors pour les arbres, on désigne le sous-arbre que l'on dessine à notre droite. Il serait donc plus juste de parler du sous-arbre à gauche et du sous-arbre à droite et donc de faire le choix de gauche et droite.

Néanmoins, dans les phrases dire sous-arbre à droite est parfois maladroit e.g. :

def droite(a):
    """renvoie le sous-arbre à droite de a"""

On a l'impression qu'on parle du sous-arbre qui se trouve à droite de l'arbre ce qui n'a pas de sens.

Mais sous-arbre droite sonne comme une faute d'accord. Finalement, nous prenons le parti d'utiliser droit dans le reste de l'article. Sachant que cela désigne bien le sous-arbre que nous dessinons à notre droite.

Les arbres binaires de recherche sont bien des cas particuliers d'arbres binaires :

Arbre Binaire de Recherche ou ABR

Un ABR \(A\) est un arbre binaire construit sur un ensemble totalement ordonné. Si \(A\) n'est pas vide notons :

• \(v\) la valeur associée à la racine de \(A\),
• \(V_G\) l'ensemble des valeurs associées au sous-arbre gauche \(G\)
• \(V_D\) l'ensemble des valeurs associées au sous-arbre droit \(D\)

Alors on a les propriétés suivantes :

• \(G\) est un ABR et \(\forall v' \in V_G, v' \lt v\)
• \(D\) est un ABR et \(\forall v' \in V_D, v' \gt v\)

Remarques

1. Certains sujets (ou auteurs) autorisent une inégalité large du côté droit, ce qui permet d'avoir plusieurs fois la même valeur dans l'ABR. Mais cela complique les choses notamment pour les insertions de nouvelles valeurs.
2. Là encore cette définition peut sembler trop mathématique et devra donner lieu à une adaptation par chacun.e dans son cours.

Exemple 9. Un ABR

On pourrait alléger la représentation en omettant les arbres vides ici symbolisés par le caractère ø

VI. Interface

Avant de nous lancer dans l'implémentation, nous donnons l'interface des arbres binaires. Cette interface sera de type fonctionnelle et non objet, ce qui autorise à l'utiliser aussi pour une implémentation non POO. Dans la suite nous donnerons parfois des méthodes équivalentes suivant le besoin (par exemple la méthode est_vide(self)). Nous noterons AB le type arbre binaire, nœud le type nœud et ELT le type des valeurs des nœuds.

def arbre_vide() -> AB
    """renvoie un arbre binaire vide"""

def arbre_bin(v: ELT, g: nœud, d: nœud) -> AB
    """contruit et renvoie l'arbre binaire dont la racine est le nœud formé 
    à partir de la valeur v et des nœuds g et d."""

def est_vide(a: AB) -> bool
    """renvoie True si l'arbre a est vide, et False sinon"""

def valeur(a: AB) -> ELT
    """renvoie la valeur de la racine de l'arbre a (provoque une erreur si a est vide)"""

def gauche(a: AB) -> AB
    """renvoie le sous-arbre à gauche de a (provoque une erreur si a est vide)"""

def droit(a: AB) -> AB
    """renvoie  le sous-arbre droit de a (provoque une erreur si a est vide)"""

VII. Implémentations

Nous nous intéressons ici uniquement aux implémentations orientées objet pour les raisons suivantes :

• il s'agit d'une occasion de pratiquer la POO de manière simple
• le commentaire explicite du programme officiel :

  L’exemple des arbres permet d’illustrer la programmation par classe

• dans le cadre d'un format du baccalauréat avec 3 exercices pour l'épreuve écrite, un exercice sur les arbres (binaires et/ou de recherche) associé à la POO et des algorithmes récursifs permet de balayer trois thèmes important du programme.

Puisque les définitions semblent mettre en avant l'existence de deux entités : les nœuds et les arbres, commençons par une implémentation d'arbre binaire à l'aide de deux classes (nous reviendrons sur les ABR dans un deuxième temps).

Arbre binaire à base de deux classes

Un nœud est donc constitué d'une valeur et de \(0\), \(1\) ou \(2\) nœuds successeurs. L'absence de nœud est matérialisée par l'utilisation de l'objet particulier None :

La classe Noeud

class Noeud:

    def __init__(self, valeur, gauche=None, droit=None):
        self.valeur = valeur
        self.gauche = gauche if isinstance(gauche, Noeud) else None
        self.droit = droit if isinstance(droit, Noeud) else None

On peut alors créer un ensemble de nœuds, liés les uns autres ou pas :

Exemple 10. Création de quelques nœuds

>>> d = Noeud('D')
>>> e = Noeud('E')
>>> c = Noeud('C', None, e)

d est un nœud sans successeur, dont la valeur associée est la lettre D. c n'a pas de successeur à gauche mais un à droite : le nœud e.

Un arbre binaire est donc caractérisé par une racine qui peut être absente ie None l'arbre est alors l'arbre vide. S'il n'est pas vide, sa racine est un Noeud et il possède deux sous-arbres. Ces sous-arbres sont éventuellement vides. Quand un sous-arbre n'est pas vide sa racine est un successeur du nœud racine.

La classe AB

class AB:

    def __init__(self, racine=None):
        self.racine = racine if isinstance(racine, Noeud) else None
        if self.racine is not None:
            self.gauche = AB(self.racine.gauche)
            self.droit = AB(self.racine.droit)

Maintenant que nous avons nos deux classes, nous pouvons définir les fonctions de l'interface :

Les fonctions de l'interface

def arbre_vide():
    return AB()

def arbre_bin(valeur, gauche=None, droit=None):
    return AB(Noeud(valeur, gauche, droit))

def est_vide(arbre):
    return arbre.racine is None

def valeur(arbre):
    return arbre.racine.valeur

def gauche(arbre):
    return arbre.gauche

def droit(arbre):
    return arbre.droit

Exemple 11. Création d'un arbre binaire

>>> k = Noeud('K')
>>> i = Noeud('I')
>>> d = Noeud('D')
>>> e = Noeud('E')
>>> c = Noeud('C', None, e)
>>> b = Noeud('B', c, d)
>>> g = Noeud('G', i, None)
>>> j = Noeud('J', k, None)
>>> h = Noeud('H', j, None)
>>> f = Noeud('F', g, h)
>>> a = arbre_bin('A', b, f)

Représentation de l'arbre

Et voici une visualisation possible, où on ne représente pas l'arbre vide mais les racines des arbres sont colorés : bleu pour le sous-arbre gauche et rouge pour le droit :

Cohérence

Dans l'implémentation précédente, on a bien fait attention à ce que les successeurs d'un nœud lorsqu'ils existent sont des nœuds et les sous-arbres d'un arbre binaire sont bien des arbres binaires (éventuellement vides).

Le fait d'avoir un arbre vide qui soit bien de type AB est important : si on crée des méthodes comme par exemple une méthode taille qui donne le nombre de nœuds d'un arbre binaire, alors on peut écrire la méthode simplement, sans se soucier de savoir en amont si on est en train de traiter l'objet None :

Une méthode

def taille(self):
    if self.est_vide():
        return 0
    else:
        return 1 + self.gauche.taille() + self.droit.taille()

Cohérence entre arbre et nœud

On a ici une cohérence totale entre les arbres et les nœuds : quelque soit l'arbre non vide \(a\) qu'on considère, la racine du sous-arbre gauche si elle existe est égale au successeur gauche de la racine de \(a\) (et on a le résultat dual pour le côté droit bien sûr). Dit autrement :

>>> not a.est_vide() and a.racine.gauche == a.gauche.racine
True

Remarque

Mais honnêtement est-ce que cela apporte quelque chose au niveau d'un enseignement de NSI d'avoir les deux classes Noeud et ArbreBinaire ? Probablement pas. Nous verrons dans la suite, avec les arbres binaires de recherche que l'implémentation à l'aide de deux classes ne fait que complexifier les choses. Malheureusement, on trouve dans de nombreux sujets, une implémentation bancale à l'aide de deux classes.

Cas des ABR

Concernant les arbres binaires de recherche, en plus de la cohérence évoquée précédemment, on souhaite évidemment la cohérence sur l'ordre des valeurs des nœuds : pas question de construire un arbre binaire de recherche avec des sous-arbres qui ne seraient pas des arbres binaires de recherche (parce que les nœuds auraient été ajoutés n'importe où).

Pour réaliser cela il suffit d'imposer de ne pouvoir construire qu'un ABR vide et proposer une méthode ad-hoc pour l'insertion de valeurs.

Dès lors l'utilisation de la classe Noeud va complexifier l'implémentation : il faut s'assurer de maintenir la cohérence entre nœuds et arbres lors de l'insertion. Voici à quoi pourrait ressembler une telle implémentation basé sur un héritage à partir de la classe AB, appelons la ABR2 :

Une classe d'ABR dérivée de AB

class ABR2(ArbreBinaire):
"""Pour garantir la conformité, on ne peut que créer un ABR vide, l'ajout de nœud
ne se faisant que par l'intermédiaire de la méthode ad-hoc
"""

    def __init__(self):
        ArbreBinaire.__init__(self)

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

    def valeur(self):
        return self.racine.valeur

    def insere_une_valeur(self, v):
        """insère correctement une valeur v dans l'ABR en conservant la cohérence avec
        l'ensemble des nœuds"""
        if self.est_vide():
            self.racine = Noeud(v)
            self.gauche = ABR2()
            self.droit = ABR2()
        elif v > self.valeur():
            if self.droit.est_vide():
                self.droit.insere_une_valeur(v)
                self.racine.droit = self.droit.racine 
            else:
                self.droit.insere_une_valeur(v)
        elif v < self.valeur():
            if self.gauche.est_vide():
                self.gauche.insere_une_valeur(v)                
                self.racine.gauche = self.gauche.racine 
            else:
                self.gauche.insere_une_valeur(v)

    def insere_valeurs(self, values):
        for v in values:
            self.insere_une_valeur(v)

Trop complexe

Cette implémentation est bien trop complexe et lourde pour un enseignement de NSI.

Finalement l'existence des nœuds est surtout utile pour les démonstrations sur les arbres. Pour l'implémentation, amalgamer nœud et valeur du nœud n'est pas très grave. On garde alors une unique classe ABR :

Une unique classe ABR

class ABR:

    def __init__(self, valeur=None):
        self.valeur = valeur
        if valeur is not None:
            self.gauche = ABR()
            self.droit = ABR()

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

    def insere_une_valeur(self, v):
        if self.est_vide():
            self.valeur = v
            self.gauche = ABR()
            self.droit = ABR()
        elif v > self.valeur:
                self.droit.insere_une_valeur(v)
        elif v < self.valeur:
                self.gauche.insere_une_valeur(v)

    def insere_valeurs(self, values):
        for v in values:
            self.insere_une_valeur(v)

Exemple 12. Création d'un ABR

Voici comment créer l'ABR de l'exemple 9 :

>>> EX9 = ABR()
>>> EX9.insere_valeurs([12, 10, 15, 5, 20, 4, 8])

Notons que les fonctions de l'interface restent identiques à ce qu'on avait défini pour les arbres binaires quelconques.

Le choix d'une seule classe

On pourrait alors implémenter les arbres binaires en général sur le même principe que cette implémentation des ABR : une seule classe ArbreBinaire. C'est probablement ce qu'il y a de plus raisonnable au niveau de l'enseignement de NSI.

Pour s'en convaincre :

• dresser un tableau des avantages et inconvénients des deux implémentations
• jeter un coup d'œil aux ressources qui proposent les deux classes (et comparer la lourdeur face à l'implémentation par une classe unique)

Visualiser dans un notebook

Vous pouvez télécharger une définition de ABR avec visualisation possible dans n'importe quel notebook² (Basthon ou Capytale) ici : ABR avec une méthode de visualisation

Exemple

>>> EX9 = ABR()
>>> EX9.insere_valeurs([12, 10, 15, 5, 20, 4, 8])

Visualisation en gris avec les arbres videsVisualisation sans arbres vides mais coloration

>>> EX9.show()

Les arbres gauches sont en bleu, les droits en rouge.

>>> EX9.show(show_vide=False, colored=True)

La solution Éduscol

Dans [Eduscol2021b] la modélisation d'un ABR proposée est celle de deux classes, mais la classe ABR_EDU est bancale et ne sert qu'à poser une référence sur le nœud racine et à modéliser l'arbre vide (la racine est fixée à None).

Les deux classes d'Éduscol

class ABR_EDU:
    def __init__(self, racine = None):
        self.racine = racine

class Noeud:
    def __init__(self, valeur, noeud_gauche = None, noeud_droit = None):
        self.valeur = valeur
        self.noeud_gauche = noeud_gauche
        self.noeud_droit = noeud_droit

Inconvénient 1

Avec cette solution, aucune garantie que l'arbre construit sera bien un ABR. Par exemple l'arbre a ci-dessous n'est pas un ABR :

n1 = noeud(10)
n2 = noeud(20)
a = ABR_EDU(noeud(15, n2, n1))

Inconvénient 2

Tous les algorithmes seront reportés sur les nœuds. Mais conceptuellement la hauteur d'un nœud par exemple n'a pas beaucoup de sens. D'autre part, comme la plupart des algorithmes sont reportés sur les nœuds, on perd l'intérêt d'avoir effectivement un arbre vide non modélisé par None et on se retrouve à gérer l'absence de nœud c'est-à-dire à gérer la valeur spéciale None.

Pour illustrer ce deuxième inconvénient, ci-dessous la méthode de recherche d'une valeur dans un arbre binaire proposée par Éduscol sous la forme de deux méthodes : l'une (celle qui fait vraiment le travail) dans la classe Noeud, l'autre dans la classe ABR ne fait qu'appeler la première sur la racine de l'arbre :

La fonction de recherche de Éduscol

class ABR_EDU:
    ...
    def rechercher(self, valeur):
        return self.racine.rechercher(valeur)

class Noeud:
    ...
    def rechercher(self, valeur):
        if self.valeur == valeur:
            return True
        elif valeur < self.valeur:
            if self.noeud_gauche is None:
                return False
            else:
                return self.noeud_gauche.rechercher(valeur)
        else:
            if self.noeud_droit is None:
                return False
            else:
                return self.noeud_droit.rechercher(valeur)

Voilà ce que serait cette méthode avec notre implémentation à une unique classe :

La fonction de recherche avec 1 classe ABR

Voici la méthode qui pourrait être ajoutée à notre classe ABR unique :

class ABR:
    ...
    def rechercher(self, valeur):
        if self.est_vide():
            return False
        elif valeur == self.valeur:
            return True
        elif valeur < self.valeur:
            return self.gauche.rechercher(valeur)
        else:
            return self.droit.rechercher(valeur)

Pour finir examinons quelques sujets de Bac.

VIII. Quelques sujets de Bac

Cette partie est amenée à évoluer au fur et à mesure des exercices traités, cela prend un peu de temps

20222021

• 2022 Asie-Pacifique, jour 2, sujet 1, exercice 2 : 22-NSIJ2A1-exo2
• 2022 Mayotte-Liban, jour 1, sujet 1, exercice 4 : 22-NSIJ1LR1-exo4
• 2022 Polynésie, jour 1, sujet 1, exercice 5 : 22-NSIJ1PO1-exo5

• 2021 Amérique du Nord, jour 1, sujet 1, exercice 3 : 21-NSIJ1AN1-exo3
• 2021 Amérique du Nord, jour 1, sujet 1, exercice 4 : 21-NSIJ1AN1-exo4
• 2021 Métropole, candidats libres, jour 2, exercice 3 : 21-NSIJ2ME2-exo3
• 2021 Guyane, jour 1, exercice 3 : 21-NSIJ1G11-exo3
• 2021 Métropole, jour 1, sujet 1, exercice 1 : 21-NSIJ1ME1-exo1

IX. Conclusion

Les structures de données arborescentes (arbre et surtout arbres binaires et arbres binaires de recherche) sont largement exploitées dans les sujets de l'écrit du Bac. En effet, ces structures permettent d'aborder de nombreux points du programme de Tle : structure de données, interface vs implémentation, programmation orientée objet, récursivité. De plus, les exemples concrets où cette structure intervient sont nombreux.

Mais, ce thème des arbres n'est pas facile, concentrant beaucoup de définitions et différentes implémentations possibles. Certains choix malheureux d'implémentations augmentent encore cette difficulté. Que ce soit dans les séances de cours, les activités ou encore les sujets d'examen, une grande vigilance devrait être apportée aux définitions et implémentations pour produire des codes légers et compréhensibles.

Bibliographie

Chambon2022 Algorithmique, mathématiques, avec Python. Partie 2

DGESCO2021 Adaptation du périmètre d'évaluation de l'épreuve de NSI

Eduscol2021a Arbres binaires de recherche

Eduscol2021b Implémentation des arbres binaires de recherche à l'aide de la POO

Eduscol2021c Généralités sur les arbres

Knuth1968 The Art of Computer Programming, Vol.3 Sorting and Searching, Addison-Wesley, 1968

Knuth1997 The Art of Computer Programming, Vol.1 Fundamental Algorithms, 3rd Edition, Addison-Wesley, 1997

Lassus2022 Terminale NSI -- Lycée François Mauriac -- Bordeaux

Nativel2022 Cours de Tle NSI, F.Nativel, lycée Mémona Hintermann-Afféjee (académie de la Réunion)

Progalgo2022 Notebook cours sur les Arbres

---

1. Pourtant on trouve cette erreur dans un sujet de Bac ; voir la question 1a de 22-NSIJ1LR1-exo4 ↩

2. La méthode show utilisée est d'Olivier Lecluse, collègue malheureusement décédé en 2020 (voir le site original) ; D'autres collègues se servent de l'outil graphviz pour visualiser leurs arbres (c'est le cas par exemple dans [Chambon2022]) ↩