Structures arborescentes

Comment représenter une arborescence de commentaires comme sur un forum ? De quelle manière modéliser un système de fichiers ou organiser des catégories imbriquées dans une base de données ?

Tous ces problèmes ont un point commun : ils manipulent des données hiérarchiques. Et derrière cette hiérarchie se cache une structure fondamentale en informatique : l’arbre.

Un système de fichiers, par exemple, peut être représenté naturellement sous forme d’arbre :

Chaque dossier peut contenir des sous-dossiers, qui peuvent eux-mêmes contenir d’autres dossiers et fichiers. Cette organisation imbriquée reflète la manière dont nous structurons intuitivement l’information.

Un arbre est une structure hiérarchique composée de nœuds, où chaque nœud peut contenir d’autres nœuds appelés enfants.

Mais représenter un arbre n’est qu’une première étape. Comment le parcourir efficacement, le manipuler avec du code et surtout le stocker — que ce soit en mémoire, dans un fichier ou dans une base de données ?

Pour répondre à ces questions, un concept clé entre en jeu : la récursivité. Elle permet de traiter un arbre de manière naturelle, en exploitant sa structure imbriquée.

Dans cet article, nous partirons de cette relation entre arbres et récursivité pour comprendre comment manipuler ces structures, avant d’explorer différentes façons concrètes de les stocker : au format JSON ou XML, ou dans une base de données relationnelle.

Cet article se concentre surtout sur les aspects pratiques : manipulation des arbres, parcours et stockage.

Pour une approche plus théorique du sujet incluant les arbres binaires de recherche et les arbres équilibrés, vous pouvez également consulter l’article Structures arborescentes - La notion de type abstrait de donnée.

Tous les exemples seront implémentés en Python afin de privilégier la clarté et la lisibilité, mais les concepts présentés sont facilement transposables dans la plupart des langages.

Un nœud d’arbre peut contenir d’autres nœuds, appelés enfants. Cette organisation hiérarchique se prolonge à chaque niveau : chaque enfant peut à son tour posséder ses propres enfants.

Un arbre est une structure récursive : chaque nœud peut être vu comme la racine d’un sous-arbre. En programmation, la récursivité consiste pour une fonction à s’appeler elle-même afin de résoudre un problème en le découpant en sous-problèmes plus simples.

Cette propriété se retrouve directement dans la manière dont on manipule les arbres en programmation.

En Python, il est possible de représenter un nœud de façon très simple :

Sélectionnez

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

Chaque nœud possède une valeur et une liste d’enfants, qui sont eux-mêmes des instances de Node. Cela permet de construire des arbres de profondeur quelconque.

Par exemple, on peut créer un arbre manuellement :

Sélectionnez

a = Node("A")
b = Node("B")
c = Node("C")
d = Node("D")

a.children = [b, c]
b.children = [d]

La structure obtenue peut être représentée sous forme textuelle :

Sélectionnez

    A
   / \
  B   C
 /
D

Dans cet exemple, A est la racine, B et C sont ses enfants et D est un enfant de B, illustrant la hiérarchie de l’arbre.

Dans la pratique, ce type d’organisation peut représenter un système de fichiers où A serait un dossier racine, B et C des sous-dossiers et D un fichier contenu dans l’un d’eux.

Cette organisation illustre concrètement la nature récursive de l’arbre : chaque partie de la structure reproduit le même schéma que l’ensemble.

C’est précisément cette propriété qui rend la récursivité si naturelle pour travailler avec les arbres : une fonction peut s’appliquer à un nœud, puis se réappliquer de la même manière à chacun de ses enfants.

Malgré sa simplicité, ce modèle permet de représenter des structures très riches comme les systèmes de fichiers, les arbres de décision en intelligence artificielle ou les arbres syntaxiques en compilation.

Explorer un arbre consiste à parcourir ses différents nœuds selon différentes approches, afin d’analyser sa structure et les informations qu’il contient.

III-A. Parcourir un arbre en profondeur (DFS)▲

III-A-1. Version récursive▲

Cette fonction parcourt l’arbre en profondeur (DFS, Depth-First Search) :

Sélectionnez

def dfs_recursive(noeud):
    print(noeud.value)
    for enfant in noeud.children:
        dfs_recursive(enfant)

Le principe est simple :

on traite le nœud courant (affichage de sa valeur) ;
on appelle récursivement la fonction sur chacun de ses enfants ;
lorsqu’un nœud ne possède pas d’enfants, aucun nouvel appel récursif n’est effectué : la récursion s’arrête naturellement.

Chaque appel applique exactement le même traitement, quelle que soit la profondeur.

Exemple d’arbre :

Sélectionnez

    A
   / \
  B   C
 /
D

Ordre de parcours :

Sélectionnez

A
B
D
C

Le parcours suit une logique « profondeur d’abord » :

on visite d’abord le nœud racine (A) ;
puis on descend dans le premier sous-arbre (B) ;
on continue jusqu’à atteindre une feuille (D) ;
on remonte ensuite pour explorer les autres branches (C).

Ce comportement est directement lié à la récursivité : chaque appel de fonction suspend son exécution le temps de traiter un sous-arbre, puis reprend là où il s’était arrêté.

Ce type de parcours est appelé « DFS » (Depth-First Search) ou « parcours en profondeur ». Il est utilisé, par exemple, pour explorer tous les fichiers d’un dossier, analyser un arbre de commentaires ou encore parcourir une arborescence de menus.

Ce principe constitue la base de nombreux algorithmes, notamment la recherche d’un élément dans un arbre : il suffit d’ajouter une condition d’arrêt lorsque la valeur recherchée est trouvée.

La simplicité de cette implémentation masque un mécanisme puissant : la pile d’appels gère automatiquement le retour en arrière dans l’arbre.

Dans le cas particulier des arbres binaires, il existe d’autres variantes de parcours en profondeur, comme les parcours préfixe, infixe et postfixe, utilisés notamment pour manipuler des expressions ou des structures ordonnées.

III-A-2. Comprendre la pile d’appels▲

Lorsqu’une fonction récursive est appelée, son contexte (variables locales, position dans le code, paramètres) est stocké dans une structure appelée pile d’appels.

Chaque nouvel appel est empilé au-dessus du précédent. Tant qu’un appel n’est pas terminé, le programme ne peut pas reprendre l’exécution de celui qui l’a invoqué.

Cela signifie que l’on descend dans l’arbre jusqu’à atteindre une feuille, puis que l’on remonte progressivement en dépilant les appels.

Exemple de déroulement pour l’arbre précédent :

Sélectionnez

parcourir(A)
  parcourir(B)
    parcourir(D)
  parcourir(C)

Chaque niveau d’indentation correspond à un appel empilé. Lorsque parcourir(D) se termine, l’exécution reprend dans parcourir(B), puis remonte jusqu’à parcourir(A).

On peut visualiser cela comme une pile d’assiettes : on empile les appels au fur et à mesure, puis on les retire dans l’ordre inverse (dernier entré, premier sorti).

Ce comportement est appelé « LIFO » (Last In, First Out) et constitue le fondement du fonctionnement de la récursivité.

Des outils comme l’IDE Python Thonny permettent de visualiser la pile d’appels en mode débogage : chaque appel récursif empile un nouveau contexte d’exécution, qui est ensuite dépilé lors du retour de la fonction.

Une récursivité trop profonde peut provoquer un dépassement de pile (stack overflow), entraînant l’arrêt du programme.

Dans ce cas, il est souvent préférable d’utiliser une version itérative avec une pile explicite, comme nous allons le voir dans la section suivante.

III-A-3. Version itérative▲

Cette version reproduit le comportement de la récursion, mais sans appel de fonction :

Sélectionnez

def dfs_iterative(root):
    if root is None:
        return

    stack = [root]
    while stack:
        node = stack.pop()
        print(node.value)
        stack.extend(reversed(node.children))

On utilise une pile explicite pour gérer les nœuds à visiter :

on commence avec la racine dans la pile ;
on dépile un nœud, on le traite ;
on empile ses enfants.

L’utilisation de reversed() permet de conserver le même ordre de parcours que la version récursive.

Exemple de déroulement avec l’arbre précédent :

Sélectionnez

Pile initiale : [A]

On dépile A → on empile C, B
Pile : [C, B]

On dépile B → on empile D
Pile : [C, D]

On dépile D
Pile : [C]

On dépile C
Pile : []

Cette approche évite les problèmes de dépassement de pile liés à la récursivité.

Que l’implémentation soit récursive ou itérative, ce parcours visite chaque nœud une seule fois, ce qui donne une complexité en temps en O(n), où n est le nombre de nœuds. La mémoire utilisée est en O(h), où h correspond à la hauteur de l’arbre (pile d’appels ou pile explicite).

Après avoir vu comment parcourir un arbre en profondeur, voyons maintenant une approche complémentaire : le parcours en largeur.

III-B. Parcourir un arbre en largeur (BFS)▲

Le parcours en largeur (Breadth-First Search, BFS) consiste à explorer un arbre niveau par niveau.

Contrairement au parcours en profondeur (DFS), qui descend dans une branche avant de revenir en arrière, le BFS visite tous les nœuds d’un même niveau avant de passer au suivant.

Pour cela, on utilise une file FIFO (First In, First Out).

Sélectionnez

from collections import deque

def bfs(root):
    if root is None:
        return

    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)
        queue.extend(node.children)

Le fonctionnement est le suivant :

on place la racine dans la file ;
on retire le premier élément de la file ;
on traite ce nœud (par exemple : affichage ou traitement métier) ;
on ajoute ses enfants à la fin de la file ;
on répète jusqu’à ce que la file soit vide.

Exemple d’arbre :

Sélectionnez

    A
   / \
  B   C
 /
D

Ordre de parcours en largeur :

Sélectionnez

A
B
C
D

Évolution de la file d’attente :

Sélectionnez

File initiale : [A]

On traite A → on ajoute B, C
File : [B, C]

On traite B → on ajoute D
File : [C, D]

On traite C → aucun enfant
File : [D]

On traite D → aucun enfant
File : []

Le BFS est particulièrement utile pour :

explorer un arbre niveau par niveau ;
analyser les niveaux d’une hiérarchie ;
rechercher rapidement un élément proche de la racine.

Le BFS visite les nœuds dans l’ordre de leur distance à la racine, ce qui permet d’explorer progressivement chaque niveau de l’arbre.

Comme pour le parcours en profondeur, chaque nœud est visité une seule fois (O(n)). En revanche, ce parcours nécessite une structure de file, pouvant contenir un grand nombre de nœuds selon la largeur de l’arbre.

Voyons maintenant comment ces notions s’appliquent concrètement à travers des cas d’usage réels.

Les structures arborescentes prennent tout leur sens dans des situations concrètes, où elles permettent de représenter naturellement des relations hiérarchiques.

Voici deux exemples classiques qui illustrent l’utilisation des arbres dans des contextes différents, ainsi que les concepts vus précédemment (récursivité, DFS et BFS).

IV-A. Arbre d’expression arithmétique▲

Un arbre peut servir à modéliser une expression mathématique. Chaque nœud correspond à un opérateur ou une valeur :

Exemple avec l’expression suivante :

Sélectionnez

(3 + 5) * 2

qui peut être représentée sous cette forme hiérarchique :

Sélectionnez

Dans cet arbre :

les feuilles (3, 5, 2) sont des valeurs ;
les nœuds internes (+, *) sont des opérateurs.

Cette structure permet d’évaluer l’expression de manière récursive selon un parcours en profondeur (DFS) :

Sélectionnez

def evaluer(noeud):
    if not noeud.children:
        return int(noeud.value)

    gauche = evaluer(noeud.children[0])
    droite = evaluer(noeud.children[1])

    if noeud.value == '+':
        return gauche + droite
    elif noeud.value == '*':
        return gauche * droite

Dans le cas particulier d’un arbre d’expression, les sous-expressions sont calculées avant l’application de l’opérateur parent : on obtient ainsi un parcours postfixe.

Sélectionnez

Parcours postfixe :
3 5 + 2 *

En notation postfixée, l’expression est évaluée de gauche à droite à l’aide d’une pile : on empile les valeurs, puis chaque opérateur applique son calcul aux deux derniers éléments empilés. Par exemple, 3 5 + 2 * correspond à (3 + 5) * 2.

Cette représentation est notamment employée par les interpréteurs pour faciliter l’évaluation des expressions.

Les arbres d’expression sont utilisés en compilation, en interprétation de code et dans les calculatrices.

IV-B. Arbre généalogique▲

Un arbre généalogique est un exemple très intuitif d’arborescence :

Chaque personne peut être vue comme un nœud, avec des enfants représentant la descendance.

Sélectionnez

            Grand-parent
            /          \
      Parent A        Parent B
      /      \            \
Enfant 1  Enfant 2     Enfant 3

Cette structure permet de modéliser les relations familiales de manière hiérarchique.

On peut facilement effectuer des opérations comme :

afficher toute la descendance d’une personne ;
calculer la profondeur (nombre de générations) ;
rechercher un individu dans l’arbre.

Exemple de recherche récursive :

Sélectionnez

def rechercher(noeud, valeur):
    if noeud.value == valeur:
        return noeud

    for enfant in noeud.children:
        resultat = rechercher(enfant, valeur)
        if resultat:
            return resultat

    return None

Ce type de représentation est utilisé dans :

les logiciels de généalogie ;
les systèmes de gestion d’état civil et de successions ;
la modélisation simplifiée des relations familiales.

Les techniques vues précédemment permettent également d’explorer efficacement un arbre généalogique :

parcours en profondeur (DFS) : explorer toute une branche familiale ;
parcours en largeur (BFS) : analyser les générations niveau par niveau.

Par exemple, un parcours en largeur fait apparaître les individus par génération :

Sélectionnez

Niveau 0 : Grand-parent
Niveau 1 : Parent A, Parent B
Niveau 2 : Enfant 1, Enfant 2, Enfant 3

Les arbres permettent de modéliser naturellement toute organisation hiérarchique du monde réel.

Dans un modèle simplifié, on ne représente que les liens parent-enfant sous forme d’arbre. Une généalogie complète nécessite un modèle plus riche, car un individu peut avoir plusieurs conjoints et appartenir à plusieurs branches.

Après avoir vu comment parcourir un arbre en mémoire, se pose naturellement la question de sa persistance : comment le conserver de manière durable, que ce soit dans un fichier ou sous une autre forme exploitable ?

Plusieurs solutions permettent de conserver un arbre de manière durable, sans nécessairement recourir à une base de données.

Un arbre étant naturellement hiérarchique, certains formats offrent une représentation directe, sans transformation complexe.

Le choix du mode de stockage dépend avant tout de l’usage : sauvegarde simple, échange de données ou traitement avancé.

V-A. Sérialisation en JSON▲

Le format JSON est particulièrement adapté pour représenter un arbre, car il supporte naturellement les données imbriquées.

Avant de pouvoir l’enregistrer, il faut convertir l’arbre en une structure de données standard (dictionnaires et listes) :

Sélectionnez

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

    def to_dict(self):
        return {
            "value": self.value,
            "children": [c.to_dict() for c in self.children]
        }

On peut ensuite sauvegarder l’arbre dans un fichier :

Sélectionnez

import json

with open("tree.json", "w") as f:
    json.dump(root.to_dict(), f, indent=2)

Exemple de contenu du fichier tree.json :

Sélectionnez

{
  "value": "A",
  "children": [
    {
      "value": "B",
      "children": [
        {
          "value": "D",
          "children": []
        }
      ]
    },
    {
      "value": "C",
      "children": []
    }
  ]
}

Il est ensuite possible de reconstruire l’arbre :

Sélectionnez

def from_dict(data):
    node = Node(data["value"])
    node.children = [from_dict(c) for c in data["children"]]
    return node

Le JSON est simple, lisible et largement utilisé pour les échanges de données.

V-B. Représentation en XML▲

Le XML est un autre format adapté aux données hiérarchiques.

Exemple de fichier XML décrivant le même arbre :

Sélectionnez

<node value="A">
    <node value="B">
        <node value="D"/>
    </node>
    <node value="C"/>
</node>

Cette représentation est très proche de l’organisation logique de l’arbre.

On peut facilement la parser en Python :

Sélectionnez

import xml.etree.ElementTree as ET

def from_xml(elem):
    node = Node(elem.attrib["value"])
    node.children = [from_xml(e) for e in elem]
    return node

Le XML est particulièrement intéressant lorsque l’on manipule déjà des documents structurés.

V-C. Format texte hiérarchique▲

Une autre approche consiste à représenter l’arbre sous forme de texte indenté.

Exemple de fichier texte :

Sélectionnez

A
  B
    D
  C

Chaque niveau d’indentation indique la profondeur dans la hiérarchie.

On peut reconstruire l’arbre à partir de ce texte en utilisant une pile :

Sélectionnez

def parse_tree(lines):
    stack = []
    root = None

    for line in lines:
        level = len(line) - len(line.lstrip())
        node = Node(line.strip())

        if level == 0:
            root = node
            stack = [(level, node)]
        else:
            while stack[-1][0] >= level:
                stack.pop()
            stack[-1][1].children.append(node)
            stack.append((level, node))

    return root

Ce format est très lisible et permet de visualiser rapidement une structure.

Cette approche est surtout utile pour des besoins pédagogiques ou pour visualiser rapidement une hiérarchie.

V-D. Sérialisation Python (pickle)▲

Python propose également un mécanisme de sérialisation natif avec le module pickle.

Sélectionnez

import pickle

with open("tree.pkl", "wb") as f:
    pickle.dump(root, f)

with open("tree.pkl", "rb") as f:
    root = pickle.load(f)

Le fichier tree.pkl contient une représentation binaire de l’arbre, non lisible directement par un humain.

Contrairement aux formats précédents, il ne s’agit pas d’un fichier texte, mais d’une sérialisation interne propre à Python.

Le module pickle n’est pas sécurisé : il ne faut jamais charger un fichier provenant d’une source non fiable.

Il est cependant très pratique pour des usages internes ou des prototypes.

V-E. Comparaison des approches▲

Chaque solution présente des avantages selon le contexte :

JSON : simple, portable, idéal pour les API ;
XML : structuré, adapté aux documents hiérarchiques ;
texte indenté : lisible et pédagogique ;
pickle : rapide et pratique en Python.

Il n’existe pas de solution universelle, le bon choix dépend du besoin.

Dans de nombreux cas, un simple format de sérialisation suffit. Cependant, lorsque les données deviennent volumineuses ou doivent être interrogées efficacement, une base de données devient pertinente.

Les structures arborescentes peuvent être stockées dans des bases de données relationnelles, même si celles-ci ne sont pas conçues nativement pour représenter des hiérarchies.

Plusieurs modèles existent, chacun avec ses avantages et ses contraintes. Le plus simple est le modèle parent-enfant.

VI-A. Modèle parent-enfant▲

Dans ce modèle, chaque nœud contient une référence vers son parent.

Sélectionnez

CREATE TABLE nodes (
    id INTEGER PRIMARY KEY,
    value TEXT,
    parent_id INTEGER
);

La colonne parent_id contient l’identifiant du nœud parent. La racine de l’arbre est représentée par une valeur NULL.

Exemple de données :

Sélectionnez

id | value | parent_id
----------------------
1  | A     | NULL
2  | B     | 1
3  | C     | 1
4  | D     | 2

Ces données correspondent à l’arbre suivant :

Sélectionnez

    A
   / \
  B   C
 /
D

Le nœud A est la racine (parent_id = NULL). Les nœuds B et C sont ses enfants et D est un enfant de B.

Cette double représentation permet de faire le lien entre la structure relationnelle (table) et l’organisation hiérarchique des données (arbre).

Elle est simple à mettre en place et intuitive, mais elle nécessite des requêtes récursives pour reconstruire l’arbre.

Chaque nœud référence son parent, ce qui permet de reconstituer la hiérarchie.

Une fois le modèle défini, il reste à insérer les données correspondant à un arbre.

VI-B. Insertion dans le modèle parent-enfant▲

Pour insérer un arbre complet dans une base de données, on peut utiliser une fonction récursive.

Elle applique le même principe que le parcours récursif : chaque nœud est traité, puis la fonction est appelée sur ses enfants.

Sélectionnez

def inserer(noeud, cursor, parent_id=None):
    cursor.execute(
        "INSERT INTO nodes (value, parent_id) VALUES (?, ?)",
        (noeud.value, parent_id)
    )
    node_id = cursor.lastrowid

    for enfant in noeud.children:
        inserer(enfant, cursor, node_id)

Le fonctionnement est le suivant :

on insère le nœud courant ;
on récupère son identifiant généré ;
on appelle récursivement la fonction pour chaque enfant.

Cette approche garantit que chaque nœud est correctement relié à son parent.

L’ordre d’insertion suit naturellement un parcours en profondeur de l’arbre.

Après l’insertion, il convient de valider la transaction (commit) afin d’enregistrer définitivement les données dans la base.

VI-C. Requête récursive SQL▲

Une fois les données stockées, il est nécessaire de reconstruire l’arbre pour l’exploiter.

Les bases modernes comme SQLite ou PostgreSQL permettent d’utiliser des requêtes récursives grâce à la clause WITH RECURSIVE, afin de parcourir une hiérarchie en réutilisant les résultats intermédiaires.

Sélectionnez

WITH RECURSIVE tree AS (
    SELECT id, value, parent_id FROM nodes WHERE parent_id IS NULL
    UNION ALL
    SELECT  n.id, n.value, n.parent_id FROM nodes n
    JOIN tree t ON n.parent_id = t.id
)
SELECT * FROM tree;

Cette requête fonctionne en deux étapes :

on sélectionne les nœuds racines (condition initiale) ;
on ajoute récursivement les nœuds enfants en les reliant aux résultats précédents.

Le résultat contient tous les nœuds de l’arbre.

Il est possible d’ajouter une colonne de profondeur pour mieux visualiser la hiérarchie :

Sélectionnez

WITH RECURSIVE tree(id, value, parent_id, depth) AS (
    SELECT id, value, parent_id, 0
    FROM nodes
    WHERE parent_id IS NULL

    UNION ALL

    SELECT n.id, n.value, n.parent_id, t.depth + 1
    FROM nodes n
    JOIN tree t ON n.parent_id = t.id
)
SELECT * FROM tree;

Les requêtes récursives permettent de reconstruire dynamiquement l’ensemble de l’arbre.

Cependant, ce type de requête peut devenir coûteux sur des structures volumineuses ou très profondes.

VI-D. Modèles avancés▲

Le modèle parent-enfant est simple, mais il devient rapidement limité lorsque l’on souhaite effectuer des requêtes complexes ou optimiser les performances.

Pour dépasser ces limites, d’autres modèles permettent de représenter efficacement les arbres dans une base de données, chacun étant adapté à des besoins spécifiques.

VI-D-1. Materialized Path▲

Dans ce modèle, chaque nœud stocke le chemin complet depuis la racine sous forme de chaîne de caractères.

Sélectionnez

id | value | path
------------------------
1  | A     | /1
2  | B     | /1/2
3  | C     | /1/3
4  | D     | /1/2/4

Cette approche permet de retrouver facilement tous les descendants d’un nœud grâce à une simple recherche sur le chemin.

Par exemple, pour trouver tous les descendants de B :

Sélectionnez

SELECT id, value, path FROM nodes WHERE path LIKE '/1/2/%';

Ce modèle est simple et performant en lecture, mais les mises à jour peuvent être coûteuses en cas de déplacement de sous-arbres.

VI-D-2. Nested Sets▲

Le modèle Nested Sets repose sur une numérotation des nœuds issue d’un parcours en profondeur (DFS) de l’arbre.

Chaque nœud reçoit deux valeurs :

lft : position lors de l’entrée dans le nœud ;
rgt : position lors de la sortie du nœud.

En pratique, on utilise souvent les noms lft et rgt plutôt que left et right, car ces derniers peuvent être des mots réservés en SQL.

Un compteur est incrémenté à chaque étape du parcours, ce qui permet d’attribuer ces valeurs de manière cohérente.

Exemple :

Sélectionnez

id | value | lft | rgt
-----------------------
1  | A     | 1   | 8
2  | B     | 2   | 5
4  | D     | 3   | 4
3  | C     | 6   | 7

Ces valeurs ne correspondent pas directement au nombre de descendants, mais à la position des nœuds dans le parcours complet de l’arbre.

Le mécanisme peut être visualisé ainsi :

Sélectionnez

Parcours DFS avec numérotation :

A (1
  B (2
    D (3 4)
  5)
  C (6 7)
8)

Chaque parent « encadre » ses enfants : ses bornes lft et rgt contiennent celles de tous ses descendants.

Par exemple, le nœud A possède l’intervalle [1, 8], car il est visité en premier (entrée) et quitté en dernier (sortie). Il englobe donc tous les autres nœuds.

Un nœud est un descendant d’un autre si son intervalle est entièrement inclus dans celui du parent.

Pour récupérer un nœud et l’ensemble de ses descendants, il suffit de sélectionner les nœuds dont la borne lft est comprise entre les deux bornes du nœud considéré. Par exemple, pour le nœud B, dont l’intervalle est [2, 5] :

Sélectionnez

SELECT id, value, lft, rgt
FROM nodes
WHERE lft BETWEEN 2 AND 5;

Cette requête retourne B lui-même ainsi que tous ses descendants, ici D.

Ce modèle permet également de calculer rapidement le nombre de descendants :

Sélectionnez

(rgt - lft - 1) / 2

Le modèle Nested Sets est très performant pour les lectures, car il permet de récupérer toute une sous-arborescence avec une seule requête.

En revanche, les insertions et modifications peuvent être coûteuses, car elles nécessitent généralement de recalculer les indices de nombreux nœuds pour maintenir la cohérence des intervalles.

VI-D-3. Closure Table▲

Le modèle Closure Table consiste à stocker explicitement toutes les relations ancêtre-descendant dans une table dédiée.

Sélectionnez

CREATE TABLE closure (
    ancestor INTEGER,
    descendant INTEGER,
    depth INTEGER
);

Exemple de contenu :

Sélectionnez

ancestor | descendant | depth
------------------------------
1        | 1          | 0
1        | 2          | 1
1        | 3          | 1
1        | 4          | 2
2        | 2          | 0
2        | 4          | 1
3        | 3          | 0
4        | 4          | 0

Chaque nœud apparaît au moins une fois dans la table en tant qu’ancêtre de lui-même (depth = 0), ce qui garantit que tous les éléments de l’arbre sont représentés.

Ce modèle permet des requêtes extrêmement rapides pour trouver les ancêtres ou les descendants d’un nœud.

En contrepartie, il nécessite plus d’espace de stockage et une logique d’insertion plus complexe.

VI-D-4. Choisir un modèle▲

Le choix du modèle dépend du type d’application et des contraintes de performance.

Materialized Path : simple à mettre en œuvre et efficace pour la lecture.
Nested Sets : très performant pour les lectures intensives, mais plus complexe en écriture.
Closure Table : flexible et adapté aux requêtes complexes sur les relations.

Aucun modèle n’est universel : le choix dépend des besoins en lecture, en écriture et de la complexité des requêtes.

Après avoir exploré les différentes façons de représenter, parcourir et stocker des arbres, il est temps de mettre en pratique ces notions à travers un exercice guidé.

Mettons maintenant en pratique les notions vues précédemment en calculant la profondeur maximale d’un arbre.

Elle correspond au nombre de nœuds du plus long chemin entre la racine et une feuille.

Sélectionnez

def profondeur(noeud):
    if not noeud.children:
        return 1
    return 1 + max(profondeur(c) for c in noeud.children)

Le principe est le suivant :

si le nœud est une feuille, sa profondeur est 1 ;
sinon, on calcule la profondeur de chaque enfant ;
on conserve la valeur maximale et on ajoute 1.

Cette approche repose sur la récursivité : chaque nœud peut être considéré comme la racine d’un sous-arbre.

Exemple :

Sélectionnez

    A
   / \
  B   C
 /
D

La profondeur maximale est ici de 3.

Bonus : pour aller plus loin, vous pouvez sérialiser l’arbre construit au format JSON, puis le reconstruire à partir du fichier obtenu.

Les structures arborescentes apparaissent dans de nombreux domaines de l’informatique : organisation des fichiers, représentation de données hiérarchiques, stockage dans une base de données ou encore conception d’algorithmes.

La récursivité constitue une approche particulièrement naturelle pour parcourir et traiter ces structures, même si des solutions itératives sont également possibles.

Selon le contexte, un arbre peut être exploré, sérialisé ou stocké, avec des approches adaptées aux besoins en performance, en lisibilité ou en flexibilité.

Bien maîtriser les arbres et la récursivité aide à mieux comprendre des structures fondamentales en informatique et à concevoir des algorithmes plus solides.

Le code source présenté dans cet article est disponible en téléchargement.

Vous pouvez récupérer un module Python contenant les différentes implémentations et exemples :

Télécharger le fichier compresséfichier de test

Ce module regroupe les exemples de parcours (DFS, BFS), les structures de données ainsi que les cas concrets présentés dans l’article.

Je tiens à remercier Laurent Ott, f-leb et Alcatiz pour leurs retours encourageants, ainsi que pour leurs propositions et conseils.

Je remercie également escartefigue pour sa relecture orthographique attentive et Malick pour le suivi de l'article.

Sources et références

Documentation officielle Python — Structures de données : Python – Data Structures
Documentation Python — Module collections (Deque pour BFS) : Python – collections.deque
SQLite — Requêtes récursives (WITH RECURSIVE) : SQLite – WITH RECURSIVE
Romuald Perrot, Introduction aux arbres : article sur Developpez.com
Thomas H. Cormen et al., Introduction to Algorithms, MIT Press.
Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser, Data Structures and Algorithms in Python.
Joe Celko, SQL for Smarties: Advanced SQL Programming.

Arbres : récursivité, parcours (DFS/BFS) et stockage

Des structures hiérarchiques aux bases de données : manipuler et stocker les arbres efficacement

L'auteur

L'article

Liens sociaux

I. Introduction▲

II. Arbres et récursivité : un lien naturel▲

III. Explorer un arbre▲

III-A. Parcourir un arbre en profondeur (DFS)▲

III-A-1. Version récursive▲

III-A-2. Comprendre la pile d’appels▲

III-A-3. Version itérative▲

III-B. Parcourir un arbre en largeur (BFS)▲

IV. Cas concrets d’utilisation des arbres▲

IV-A. Arbre d’expression arithmétique▲

IV-B. Arbre généalogique▲

V. Stocker un arbre dans un fichier▲

V-A. Sérialisation en JSON▲

V-B. Représentation en XML▲

V-C. Format texte hiérarchique▲

V-D. Sérialisation Python (pickle)▲

V-E. Comparaison des approches▲

VI. Stocker un arbre dans une base de données▲

VI-A. Modèle parent-enfant▲

VI-B. Insertion dans le modèle parent-enfant▲

VI-C. Requête récursive SQL▲

VI-D. Modèles avancés▲

VI-D-1. Materialized Path▲

VI-D-2. Nested Sets▲

VI-D-3. Closure Table▲

VI-D-4. Choisir un modèle▲

VII. Exercice guidé▲

VIII. Conclusion▲

IX. Téléchargement▲

X. Remerciements▲