CPGE MP / PSI · Informatique

Analyse des algorithmes sur les arbres binaires

Pr. EL HADIQ Zouhair

Pour la hauteur, les parcours et l'insertion dans un ABR : spécification, correction (récurrence structurelle, invariant de boucle), terminaison (fonction de mesure, variant) et complexité.

📘 Cadre : correction totale

Un algorithme est correct (au sens total) s'il vérifie :

\[ \text{Correction totale} \;=\; \text{Correction partielle} \;+\; \text{Terminaison} \]

Les algorithmes sur les arbres sont presque tous récursifs, car la structure elle-même est récursive. L'outil naturel est donc la récurrence structurelle : on prouve la propriété sur l'arbre vide (cas de base), puis sur un arbre en supposant la propriété acquise sur ses deux sous-arbres (hérédité). La terminaison repose sur une fonction de mesure \(\mu \in \mathbb{N}\) qui décroît strictement à chaque appel.

🌳 Mesure de référence. Pour un arbre \(a\), on note \(n(a)\) son nombre de nœuds et \(h(a)\) sa hauteur. L'ensemble \((\mathbb{N},<)\) étant bien fondé (pas de suite infinie strictement décroissante), toute récursion dont la mesure décroît vers le cas de base s'arrête.

1. Hauteur d'un arbre

def hauteur(a):
    if a is None:
        return -1
    return 1 + max(hauteur(a[1]), hauteur(a[2]))
Spécification. Précondition : \(a\) est un arbre binaire (None ou [v, g, d]). Postcondition : hauteur(a) renvoie \(h(a)\), longueur du plus long chemin de la racine à une feuille, avec \(h(\varnothing) = -1\).
Correction (récurrence structurelle). Propriété \(P(a)\) : « hauteur(a) \(= h(a)\) ».

Base. Si \(a = \varnothing\), la fonction renvoie \(-1 = h(\varnothing)\). \(P(\varnothing)\) est vraie.

Hérédité. Soit \(a = [v, g, d]\). On suppose \(P(g)\) et \(P(d)\). Par définition, \(h(a) = 1 + \max(h(g), h(d))\). Les appels renvoient respectivement \(h(g)\) et \(h(d)\) (hypothèse), donc la fonction renvoie \(1 + \max(h(g), h(d)) = h(a)\). \(P(a)\) est vraie.

Terminaison (mesure). On prend \(\mu(a) = n(a)\). À chaque appel non terminal sur \(a = [v,g,d]\), les appels récursifs portent sur \(g\) et \(d\), avec \(n(g) < n(a)\) et \(n(d) < n(a)\) (la racine \(v\) n'appartient à aucun sous-arbre). La mesure décroît strictement et reste dans \(\mathbb{N}\) : l'algorithme s'arrête.
Complexité. Chaque nœud est visité exactement une fois et déclenche un travail \(O(1)\). D'où \(T(n) = \Theta(n)\), quelle que soit la forme de l'arbre. (En profondeur, la pile d'appels atteint \(O(h)\).)

2. Parcours en profondeur (infixe)

def infixe(a):
    if a is None:
        return []
    return infixe(a[1]) + [a[0]] + infixe(a[2])
Spécification. Postcondition : infixe(a) renvoie la liste des valeurs de \(a\) dans l'ordre gauche → racine → droite.
Correction (récurrence structurelle). Propriété \(P(a)\) : « infixe(a) renvoie le parcours infixe de \(a\) ».

Base. \(a = \varnothing\) : le parcours infixe est la liste vide, et la fonction renvoie [].

Hérédité. \(a = [v,g,d]\). Par hypothèse, infixe(g) et infixe(d) renvoient les parcours infixes de \(g\) et \(d\). La concaténation infixe(g) + [v] + infixe(d) place exactement gauche, puis racine, puis droite : c'est la définition du parcours infixe de \(a\).

La même preuve s'adapte au préfixe ([v] + ...) et au postfixe (... + [v]) : seul change l'emplacement de la racine.

Terminaison (mesure). Mesure \(\mu(a) = n(a)\). Les appels portent sur \(g\) et \(d\), de tailles strictement inférieures. Décroissance stricte dans \(\mathbb{N}\) : arrêt garanti.
Complexité. Chaque nœud est traité une fois. Attention toutefois : la concaténation + de listes en Python recopie, ce qui peut alourdir le coût. En comptant les concaténations, le pire cas (arbre filiforme) atteint \(O(n^2)\) ; avec un accumulateur (ou list.append), on retrouve \(O(n)\). Le nombre de visites, lui, reste \(\Theta(n)\).
Propriété de l'ABR. Si \(a\) est un arbre binaire de recherche, le parcours infixe renvoie les valeurs triées par ordre croissant. Preuve par récurrence : par l'invariant d'ordre, toutes les valeurs de \(g\) sont \(< v\) et toutes celles de \(d\) sont \(> v\) ; par hypothèse \(g\) et \(d\) donnent des listes triées, donc \(\text{infixe}(g) \;\frown\; [v] \;\frown\; \text{infixe}(d)\) est triée.

3. Parcours en largeur (itératif)

def largeur(a):
    if a is None:
        return []
    file = deque([a]); ordre = []
    while file:
        n = file.popleft()
        ordre.append(n[0])
        if n[1] is not None: file.append(n[1])
        if n[2] is not None: file.append(n[2])
    return ordre
Correction (invariant de boucle). Invariant \(I\) : « ordre contient, dans l'ordre des niveaux, les nœuds déjà défilés ; file contient les nœuds découverts mais pas encore traités, rangés par profondeur croissante (de gauche à droite à profondeur égale) ».

Initialisation. Avant la boucle, ordre = [] et file = [racine] : \(I\) est vraie.

Conservation. On défile le nœud le plus prioritaire \(n\) (le moins profond, le plus à gauche), on l'ajoute à ordre et on enfile ses fils en queue. Comme la file est FIFO et que les fils sont à profondeur \(+1\), ils sont traités après tous les nœuds du niveau courant : \(I\) est préservée.

Sortie. À l'arrêt, file est vide : tous les nœuds atteignables ont été défilés, donc ordre est le parcours en largeur complet.

Terminaison (variant). Chaque nœud de l'arbre est enfilé au plus une fois (il est atteint par son unique père). Variant : \(V = (\text{nœuds jamais enfilés}) + |\text{file}|\). Chaque tour défile un élément et enfile au plus 2 fils non encore vus ; \(V\) décroît strictement à chaque itération et reste \(\ge 0\). Par le théorème de Floyd, la boucle s'arrête après au plus \(n\) tours.
Complexité. \(n\) défilements, \(n\) enfilements, chacun \(O(1)\) avec une deque : \(T(n) = \Theta(n)\). L'espace est \(O(\ell)\) où \(\ell\) est la largeur maximale d'un niveau (jusqu'à \(O(n)\) pour un arbre parfait).

4. Insertion dans un ABR

def inserer(a, x):
    if a is None:
        return [x, None, None]
    if x < a[0]:
        a[1] = inserer(a[1], x)
    elif x > a[0]:
        a[2] = inserer(a[2], x)
    return a
Spécification. Précondition : \(a\) est un ABR. Postcondition : inserer(a, x) renvoie un ABR contenant les valeurs de \(a\) et \(x\) (sans doublon).
Correction (récurrence structurelle). Propriété \(P(a)\) : « le résultat est un ABR égal à \(a\) augmenté de \(x\) ».

Base. \(a = \varnothing\) : on renvoie la feuille [x,None,None], ABR ne contenant que \(x\). Correct.

Hérédité. \(a = [v,g,d]\). Si \(x = v\), rien n'est inséré (pas de doublon). Si \(x < v\), par hypothèse inserer(g, x) renvoie un ABR \(g'\) contenant \(g \cup \{x\}\), avec toutes ses valeurs \(< v\) (car \(x < v\) et les valeurs de \(g\) aussi) : l'invariant d'ordre en \(v\) est préservé, et \([v, g', d]\) est un ABR. Le cas \(x > v\) est symétrique.

Terminaison (mesure). Mesure \(\mu(a) = h(a)\) (ou \(n(a)\)). Chaque appel récursif descend dans un sous-arbre de hauteur strictement inférieure ; on atteint le cas de base \(a = \varnothing\) en au plus \(h(a)+1\) appels.
Complexité. Le coût suit le chemin de la racine au point d'insertion : \(O(h)\). Donc \(O(\log n)\) pour un arbre équilibré.
⚠ Pire des cas. Si l'on insère des valeurs déjà triées, chaque nouvelle valeur devient l'unique fils droit : l'arbre devient filiforme, \(h = n-1\), et l'insertion comme la recherche coûtent \(O(n)\). C'est la motivation des arbres équilibrés (AVL, rouge-noir), hors programme mais utiles à connaître.

5. Bilan

AlgorithmeCorrectionTerminaisonComplexité
hauteurrécurrence structurelle\(\mu = n(a)\)\(\Theta(n)\)
parcours DFSrécurrence structurelle\(\mu = n(a)\)\(\Theta(n)\) visites
parcours BFSinvariant (file FIFO)variant \(\le n\) tours\(\Theta(n)\)
insertion ABRrécurrence structurelle\(\mu = h(a)\)\(O(h)\) : \(\log n\) à \(n\)
À retenir. La récursivité de la structure (un arbre = racine + deux sous-arbres) se transpose directement en récurrence structurelle pour la correction et en fonction de mesure (\(n\) ou \(h\)) pour la terminaison. La complexité d'un parcours est toujours \(\Theta(n)\) ; celle des opérations d'un ABR dépend de la hauteur, d'où l'enjeu de l'équilibrage.

CPGE MP / PSI · Informatique — Analyse : arbres binaires