Les arbres binaires

Warning

Ce cours a été automatiquement traduit des transparents de M.Noyer par Félix qui continue le travail fait par Lorentzo et Elowan et Mehdi, nous ne nous accordons en aucun cas son travail, ce site à pour seul but d'être plus compréhensible pendant les périodes de révision que des diaporamas.

Crédits

• "Option informatique MPSI, MP/MP* ", Roger Mansuy, paru chez Vuibert.
• Wikipédia, arbres binaires
• Un cours à Louis Le Grand

Introduction

Résumé

"Les arbres permettent la réalisation de structures de données : structure persistante de dictionnaire, structure persistante de file de priorité. Ils permettent aussi de représenter des expressions arithmétiques ou des formules logiques "(programme officiel CPGE 2013).

Figure 1 – Une arborescence de fichiers

Commentaire

La colonne de gauche est l'affichage arborescent de mon répertoire $\mathtt{\text{Files}}$ à l'aide de la commande $\text{Unix}$ $\mathtt{\text{tree Files/}}$

Figure 2 – Contenu d'un fichier html

Commentaire

La colonne de gauche est le code d'un fichier $\mathtt{\text{html}}$. Noter la présentation arborescente de ce langage de balises.

Figure 3 – Affichage html

Commentaire

La colonne de gauche est l'interprétation du fichier précédent par $\mathtt{\text{Firefox}}$.

Arithmétique

Figure 4 – Une expression arithmétique

Commentaire

La colonne de gauche est la représentation arborescente de $3+4\times 5$

Logique

Figure 5 – Une expression logique

Commentaire

La colonne de gauche est la représentation arborescente de $\neg (A\wedge (B\vee C)$ soit "$\text{Non}$ ($A$ $\text{et}$ ($B$ $\text{ou}$ $C$)) "

Définition mathématique

Arbre binaire

Définition $1$ : Arbre binaire

Soient $E$ un ensemble de cardinal au moins un ; nil un élément d'un ensemble sans intersection avec $E$ ; $C$ un symbole de constructeur ternaire sans intersection avec les précédents. On définit inductivement les arbres binaires étiquetés par $E$ en convenant que :

• $\text{Règle de base}$ : nil est un arbre binaire appelé arbre vide
• $\text{Règle d'induction}$ : Si $x\in E$ et si $F_g$ ,$F_d$ sont deux arbres binaires étiquetés par $E$ , alors $A=C(F_g,x,F_d)$ est un arbre binaire étiqueté par $E$ .
• $\text{Règle de complétude}$ : Seuls nil et les éléments que l'on peut former en un nombre fini d'application des règles d'induction sont des arbres binaires.

Remarque

Un arbre est donc un élément d'un ensemble inductif (voir chapitre précédent). On fait le choix dans la suite de ne pas utiliser de symbole pour le constructeur ternaire : on écrira $(F_g,x,F_d)$ plutôt que $C(F_g,x,F_d)$. La raison est purement esthétique : cela alourdirait les transparents.

Vocabulaire

Avec les conventions de la définition $1$ :

Étiquette

$x$ est appelée étiquette de la racine de $A$,

Fils gauche / droit

Si $A=(F_g,x,F_d)$, on dit que $F_g$ est le fils gauche de $A$, et $F_d$ son fils droit. Ce sont des sous-termes immédiats de $A$.

Père

On dit que $A$ est le père de $F_g$ . On dit parfois $\underset{―}{\text{improprement}}$ que $x$ est le père de $F_g$ .

Feuille

Si $Fg=Fd=$ nil on dit que $A$ est un arbre-feuille ou plus simplement une feuille.

$\text{Pour certains auteurs, les feuilles sont les nils !!}$

Remarque

Si \(A = $(\ast \ast nil\ast \ast ,$x\) ,$F_d$ ), nous disons que $A$ a un seul fils

Chemin

Si $A$ est un arbre, on appelle chemin tout $n$-uplet ($n>0$) $A=A_0,...,A_n$ tel que $A_0=A$ et quel que soit $k<n,A_{k+1}$ est un fils de $A_k$ . Le nombre $n$ est la longueur du chemin. Parfois, pour désigner un chemin, on ne donne que les étiquettes.

Sous-arbre

Dans un chemin, tous les $A_i$ avec $i>0$ sont appelés des descendants de $A$. On dit aussi sous-arbre ou sous-termes.

Noeud interne

Un nœud interne possède au moins un fils qui n'est pas l'arbre vide. Ce sont tous les nœuds d'un arbre à l'exception de nil et des feuilles.

Convention de représentation

Par convention, on ne représente ni nil, ni les arcs d'extrêmités nil. Au lieu de

Figure 6 – Avec nil

On représente

Figure 7 – Sans nil

Propriétés

Lemme

Dans un arbre, aucun chemin ne comporte deux fois un même arbre non vide.

Preuve

• Soit un chemin $A_1,...,A_i,...,A_j,...,A_k$ tel que $A_i=A_j$ .
• Par application du théorème sur l'ordre structurel (voir chapitre induction), les tailles structurelles (nombres de constructeurs) sont strictement décroissantes.

Ainsi $|Ai|>|Aj|$ et $A_i=A_j$ : ABSURDE.

Types d'arbres binaires

• Certains arbres ne sont pas binaires. Exemple : la figure $1$.
• Un arbre binaire entier est un arbre dont tous les nœuds possèdent zéro ou deux fils (ex : la figure $4$ mais pas $5$).
• Un arbre binaire parfait est un arbre binaire entier dans lequel toutes les feuilles sont à la même distance de la racine (c'est-à-dire à la même profondeur) (ex : la figure $7$).
• L'arbre binaire parfait est parfois nommé arbre binaire complet. Cependant certains auteurs${}^{\mathbf{\text{1.}}}$ définissent un arbre binaire complet comme étant un arbre binaire entier dans lequel les feuilles ont pour profondeur soit $n$ soit $n-1$ pour un $n$ donné (voir figure $8$).

$\mathbf{\text{1.}}$ Et nous avec !

Arbres binaires

Figure 8 – Un arbre binaire parfait

Tous les niveaux sont remplis.

Figure 9 – Un arbre binaire complet gauche

Tous les niveaux sont complets sauf le dernier qui est rempli incomplètement en commençant par la gauche.

Preuve par induction

Ordre sur les arbres binaires

$\prec$

La relation binaire $\prec$ sur les arbres étiquetés par $E$ définie par

$A⪯B\iff$ $A$ est un descendant de $B$

C'est un ordre bien fondé et $\prec$ est un ordre strict.

Démonstration

Un descendant est un sous-terme. Donc cet ordre n'est rien d'autre que l'ordre structurel (voir chapitre induction) lequel est bien fondé.

Eléments sans prédecesseur de ${\displaystyle \mathcal{A}}$

Proposition

L'ensemble des éléments sans prédecesseur des arbres étiquetés par $E$ est réduit à nil.

Preuve

Soit un arbre A.

• Si $A=$ nil, il n'a pas de prédécesseur car le constructeur est d'arité $0$.
• Sinon, $A$ est de la forme ($F_g,x,F_d$ ) et donc $F_g\prec A$. Donc $A$ admet un prédécesseur.

Principe d'induction appliqué aux arbres

Soit $P$ un prédicat sur ${\displaystyle \mathcal{A}}$

• On établit la propriété pour les éléments minimaux (donc $\{$nil$\}$).
• On prend $A$ avec prédécesseur. On suppose que pour tout prédécesseur $B$ de $A$, $P(B)$ est vrai, et on tente d'établir que $P(A)$ est vrai.

Fonction inductives

Soit ${\displaystyle \mathcal{A}}$, l'ensemble des arbres étiquetés par $E$. De nombreuses fonction $f:{\displaystyle \mathcal{A}}\to F$ se définissent par la donnée d'un élément $a\in F$ et d'une application $\phi :F\times E\times F\to F$ telles que :

• $f(\mathbf{\text{nil}})=a$
• $\forall (F_g,F_d)\in {{\displaystyle \mathcal{A}}}^2,\forall x\in E,f(F_g,x,F_d)=\phi (f(F_g),x,f(F_d))$

Le principe d'induction établit que $f$ est définie sur ${\displaystyle \mathcal{A}}$ et qu'elle prend ses valeurs dans $F$ .

Taille

Taille

La taille d'un arbre binaire est le nombre de ses nœuds qui ne sont pas nil

La taille d'un arbre $A$, notée $|A|$, se définie inductivement par :

• $|\mathbf{\text{nil}}|=0$
• $\forall (F_g,F_d)\in {{\displaystyle \mathcal{A}}}^2,\forall x\in E,|(F_g,x,F_d)|=1+|F_g|+|F_d|$

Remarque

Cette définition est différente de la taille structurelle vue au chapitre induction en ce sens qu'elle ne compte pas les constructeurs d'arité $0$. La définition varie selon les auteurs : il faut donc bien lire l'énoncé.

Profondeur

Hauteur

La hauteur d'un arbre binaire est la longueur de la plus longue branche (sans arriver jusqu'à nil).

La hauteur d'un arbre binaire $A$, notée $h(A)$, est la fonction définie inductivement par :

• $h(nil)=-1$
• $\forall (F_g,F_d)\in {\displaystyle {\mathcal{A}}^2,\forall x\in E,h((F_g,x,F_d))=1+max(h(F_g),h(F_d))}$

Profondeur

La profondeur d'un nœud dans un arbre binaire est la longueur du chemin qui le relie à la racine.

Remarque

Là encore, la définition varie selon les auteurs.

Un type $\text{OCAML}$ pour les arbres binaires

(* type possible pour les arbres binaires *)
type 'a arbre =
    Nil | Node of ('a arbre * 'a * 'a arbre);;

let a = let b = Node (Nil , 1, Nil) and c =
Node (Nil , 2, Nil) and d = Node (Nil , 4, Nil) in
let g = Node (b,4,c) and f= Node (Nil , 5, Node(d,3,Nil))
in Node(g,6,f);;(* un arbre à représenter *)

Hauteur et taille

let rec taille a =
    match a with
    | Nil -> 0
    | Node(g,_,d) ->1+taille g+taille d;;

let rec hauteur a =
    match a with
    | Nil -> -1
    | Node(g,_,d) ->1+ (max (hauteur g) (hauteur d));;

• On observe d'abord que pour ces fonctions, la complexité au pire est croissante avec la taille de la variable.
• En effet, soit $A$ un arbre avec $n$ nœuds qui atteint le maximum de complexité. Pour ($A$,$x$ ,nil), qui a $n+1$ nœuds, le calcul nécessite au moins une opération de plus (ne serait-ce que le filtrage).

Complexité du calcul de la hauteur

Méthode informelle

Pour un arbre de taille $n$ :

• De façon empirique on peut dire que chaque nœud est parcouru trois fois : quand on y accède (au moment du filtrage), quand le parcours revient du fils gauche (avec l'info sur sa hauteur), quand il revient du fils droit (avec l'info sur sa hauteur).
• Pour chacun de ces trois passages dans le nœud, le nombre d'opérations élémentaires hors appels récursifs est borné par une constante (disons $c$).
• Au total, on peut donc majorer le nombre d'opérations par $3nc$ et le minorer par $n$.
• Donc complexité en $\Theta (n)$

Relation entre taille et hauteur

Proposition

Soit $A$ un arbre. Alors $h(A)+1\le |A|\le 2^{h(A)+1}-1$. Et les bornes sont atteintes.

Preuve par induction

• Si $A=$ nil, alors $|A|=0$; $h(A)=-1.-1+1\le 0\le 2^{-1+1}-1.$ OK
• Si $A=(G,x,D)$, et si la propriété est vraie pour $G$ ,$D$ , alors

$|A|=1+|G|+|D|\ge 1+h(G)+1+h(D)+1\ge 1+(1+max(h(G),h(D)))=1+h(A)$

Et $|A|=1+|G|+|D|\le 1+2^{h(G)+1}-1+2^{h(D)+1}-1$

Donc $|A|\le -1+2·2^{max(h(G),h(D))+1}=2·2^{h(A)}-1=2^{h(A)+1}-1$

Les deux bornes sont atteintes : à gauche par les listes chaînées et à droite par les arbres parfaits.

Profondeur moyenne et applications

Profondeur moyenne

La profondeur moyenne d'un arbre est la moyenne des longueurs de ses branches ou encore la moyenne des profondeurs des feuilles.

Proposition

Dans un arbre binaire à $n>0$ feuilles, la profondeur moyenne est égale ou supérieure à $lo{g}_2(n)$

Cas de base

Par récurrence sur le nombre de feuille $n$ de $A$, on montre que la profondeur moyenne $m_A$ est plus grande que $lo{g}_2(n)$.

• Vrai pour $n=1$ (profondeur au moins zéro, $lo{g}_2(1)=0$).

• Si $n=2$, la plus petite profondeur moyenne intervient quand les deux feuilles sont à la profondeur $1$. Alors la profondeur moyenne vaut $1$ et $lo{g}_2(2)=1$. Si l'une des feuilles n'est pas à la profondeur $1$, la profondeur moyenne est strictement supérieure à $lo{g}_2(2)$.

Cas d'un fils unique

Par récurrence sur le nombre de feuille $n$ de $A$, on montre que la profondeur moyenne $m_A$ est plus grande que $lo{g}_2(n)$. Supposons la propriété vraie pour tout arbre binaire d'au plus $n$ feuilles $(2\le n)$. On se donne un arbre $A$ de $n+1$ feuilles $(n\ge 2)$. Si $A$ n'a qu'un fils, on se ramène au problème à deux fils :

• L'unique fils $F$ de $A$ a autant de feuilles que $A$ mais la profondeur de ses feuilles est plus petite (car $m_A=m_F+1$).
• En descendant dans l'arbre on finit par trouver un premier descendant $D$ qui a deux fils (car $A$ a au moins deux feuilles) et $n+1$ feuilles.
• On montre donc la propriété pour $D$ , elle sera vraie pour $A$ car la profondeur moyenne y est plus grande.

Deux fils et $n+1$ feuilles

On suppose que $A$ a deux fils $F_g,F_d$ . Soit $k$ tel que $F_g$ possède $k$ feuilles $(n+1>k\ge 1)$, $F_d$ en a $n+1-k$

Relation moyenne $/$ somme des profondeurs :

On a à gauche : $\frac{\sum _{i=1}^k{p}_i^g}{k}=m_g$

Notation

• $p_i^g$ = profondeur de la feuille i du fils gauche,
• $m_g$ moyenne des profondeurs à gauche.

Gauche : $\sum _{i=1}^k{p}_i^g=k\times \underset{\text{prof. moy.}}{\underbrace{m_g}}\underset{\text{par HR}}{\underbrace{\ge }}k\times lo{g}_2(k)$

Droite :

$\sum _{i=1}^{n+1-k}{p}_i^d=(n+1-k)\times m_d\ge (n+1-k)\times lo{g}_2(n+1-k)$.

La somme des profondeurs des feuilles dans $A$ vérifie

$\begin{array}{ccc}{S}_{n+1}& =& \sum _{r=1}^{n+1}{p}_r\\ & & \\ & =& \sum _{i=1}^k(1+p_i^g)+\sum _{i=1}^{n+1-k}(1+p_i^d)\\ & & \\ & =& n+1+\sum _{i=1}^k{p}_i^g+\sum _{i=1}^{n+1-k}{p}_i^d\\ & & \\ & \ge & n+1+k\times lo{g}_2(k)+(n+1-k)\times lo{g}_2(n+1-k)\end{array}$

La somme $S_{n+1}$ des profondeurs est :

$S_{n+1}\ge n+1+k\times lo{g}_2(k)+(n+1-k)\times lo{g}_2(n+1-k)$

La fonction $f:k\mapsto k\times lo{g}_2(k)+(n+1-k)lo{g}_2(n+1-k)$ se dérive en $f^{\prime }:k\mapsto lo{g}_2(k)-lo{g}_2(n+1-k)$.

Cette dérivée s'annule en $n+1$ $f\prime (1)<0,f\prime (n)>0$ donc $f(\frac{n+1}{2})$ est minimale.

Par suite $f(k)=k\times lo{g}_2(k)+(n+1-k)\times lo{g}_2(n+1-k)$

Donc $f(k)\ge f(\frac{n+1}{2})=(n+1)\times lo{g}_2(\frac{n+1}{2})$

Alors la moyenne $m_A=\frac{Sn+1}{n+1}$ des profondeurs vérifie

$\begin{array}{ccc}(n+1)\times m_A& =& \sum _{r=1}^{n+1}{p}_r\\ & & \\ & \ge & n+1+(n+1)\times lo{g}_2(\frac{n+1}{2})\\ & & \\ & =& n+1+(n+1)\times lo{g}_2(n+1)-(n+1)\\ & & \\ & =& (n+1)\times lo{g}_2(n+1)\end{array}$

Donc $m_A\ge lo{g}_2(n+1)$ : OK !

Application aux tris

Permutation associée à une liste

Considérons un tri $T$ donné (par ex : tri fusion ou tri insertion).

• Considérons une liste (ou un tableau) à $n$ nombres $\text{tous distincts}$. La complexité du tri sur cette structure ne dépend pas des valeurs de ces nombres mais de l'ordre initial dans lequel ils sont placés.
• Classer $[12;50;3;28;46]$ a la même complexité que le classement de $[2;5;1;3;4]$ (permutation d'éléments dans J1,nK).
• A une liste $L$ de $n$ nombres distincts à trier, on associe ainsi une unique permutation $\sigma \in S_n$ . Le coût $C(L)$ du tri de $L$ selon l'algorithme $T$ dépend seulement de $\sigma$ (ordre des éléments) et on le note donc $C(\sigma )$.

Complexité en moyenne

Complexité en moyenne

La complexité en moyenne $c(n)$ du tri selon l'algo $T$ des liste de taille $n$ est le coût moyen des permutations associées :

$c(n)=\frac{1}{n!}\sum _{\sigma \in Sn}C(\sigma )$.

Arbre de décision

Arbre de décision

Un arbre de décision est un arbre binaire tel que

• chaque nœud interne est étiqueté avec une comparaison,
• chaque feuille est étiquetée avec une permutation

A un algorithme de tri appliqué à des listes de taille $n$ on associe un arbre binaire de décision unique (admis). Une permutation donnée est l'extrémité d'une branche complète de l'arbre.

On construit ainsi cet arbre de décision : La racine est la première comparaison observée entre éléments. Son fils gauche est la première comparaison effectuée lorsque le test correspondant à la racine est positif, le droit est la première comparaison effectuée si le premier test est négatif etc.

L'arbre de décision associé à un tri par comparaison sur des structures de longueur $n$ est unique (c'est une affirmation, pas une preuve : il faudrait le montrer) et il a $n!$ feuilles (autant que de permutations).

Arbre de décision du tri par insertion pour les listes $[A;B;C]$

Complexité en moyenne à partir de l'arbre de décision

Soit un tri $T$ et son arbre de décision $A$.

• La complexité du tri par $T$ d'une liste $L$ de longueur $n$ est proportionnelle à la longueur de la branche de A empruntée en traitant L. $\text{Si }L\text{ est associée à la permutation σ, la feuille sur laquelle arrive}$ $\text{ l'algorithme en traitant }L\text{ est la permutation réciproque σ−1 (car}\sigma ◦{\sigma }^{-1}=i{d}_{S_n})$

Si $L$ est associe à la permutation $[2,3,1]$ on arrive sur la feuille CAB qui correspond à la permutation $[3,1,2]$ réciproque de la précédente.

• La complexité en moyenne de $T$ est donc proportionnelle à la profondeur moyenne des $n!$ feuilles.
• Or, celle-ci est minorée par $lo{g}_2(n!)$ Et la formule de Stirling nous donne $lo{g}_2(n!)=\Theta (n\times log(n))$.
• Ainsi, la meilleure complexité possible en moyenne pour un tri par comparaison est $\Theta (n\times log(n))$.
• La complexité au pire est supérieure à la complexité en moyenne. Un algorithme qui, comme le tri fusion, réalise une complexité au pire en $\Theta (n\times log(n))$ est donc un algorithme de tri par comparaison optimal.

Parcours d'arbres binaires

Objectif

Un parcours d'arbre est une façon d'ordonner les nœuds d'un arbre afin de tous les parcourir.

On peut le voir comme une fonction qui à un arbre associe une liste de ses nœuds même si la liste n'est souvent pas explicitement construite par le parcours.

Parcours en profondeur

Depth-first search (DFS)

Les parcours en profondeur se définissent de manière récursive sur les arbres. Le parcours d'un arbre consiste à traiter la racine de l'arbre et à parcourir récursivement les sous-arbres gauche et droit de la racine. Les parcours préfixe, infixe et suffixe se distinguent par l'ordre dans lequel sont faits ces trois traitements.

Figure – Ordre dans lequel les nœuds sont visités (en exposant) dans un parcours en profondeur préfixe. Les lettres correspondent à la numérotation par parcours en largeur.

Type OCAML (rappel)

Il y a beaucoup de façon de définir les arbres binaires en Ocaml. En voici une :

type 'a tree = Nil | Node of 'a tree * 'a * 'a tree;;

let t = let g = Node(Node(Nil ,3,Nil),2,Node(Nil ,4,Nil)) and
    d = Node(Node(Nil ,6,Nil),5,Node(Nil ,7,Nil)) in
    Node(g,1,d);;

Parcours préfixe

Principe

Dès qu'on passe par un nœud, on effectue un traitement de son étiquette. On n'attend pas que les descendants du nœud soient traités. On fait ce qu'on a à faire avec ce nœud dès qu'on passe dessus.

let rec parcours_prefixe = function
    | Nil -> ()
    | Node (g, r, d) ->
        Printf.printf "%d " r;
        parcours_prefixe g;
        parcours_prefixe d ;;

parcours_prefixe a;;

On obtient 1 2 3 4 3 6 7.

Parcours suffixe

Principe

Quand on passe sur un nœud, on attend que tous ses descendants soient traités avant d'agir sur ce nœud.

let rec parcours_suffixe = function
    | Nil -> ()
    | Node (g, r, d) ->
        parcours_suffixe g;
        parcours_suffixe d ;
        Printf.printf "%d " r;;

parcours_suffixe a;;

On obtient 3 4 2 6 7 5 1

Parcours infixe

Principe

Quand on passe sur un nœud, on traite d'abord le fils gauche. Puis on traite le nœud lui même. Et enfin on traite le second fils.

let rec parcours_infixe = function
    | Nil -> ()
    | Node (g, r, d) ->
        parcours_infixe g;
        Printf.printf "%d " r;;
        parcours_infixe d ;;


parcours_infixe a;;

On obtient 3 2 4 1 6 5 7

Compléments

La complexité du parcours en profondeur pour un arbre a déjà été étudiée : c'est celle du calcul de la hauteur (laquelle est un parcours suffixe dans notre code puisque le traitement a lieu lorsqu'on connaît la hauteur des $2$ fils) : $\Theta (n)$

Le parcours préfixe (resp. suffixe) est injectif (si l'on considère que Node(Nil,x,f)=Node(f,x,Nil)). Voir TD.

Parcours en largeur

BFS

L'algorithme de parcours en largeur (ou BFS, pour Breadth First Search en anglais) permet le parcours d'un arbre de la manière suivante : on commence par explorer un nœud source, puis tous ses fils, puis les fils des fils, etc.

En bref, on visite complètement une génération avant de visiter la génération suivante.

Un BFS

La dénomination des nœuds suivants respecte le parcours en largeur :

BFS vs DFS

La dénomination des nœuds suivants respecte le parcours en profondeur (prefixe) :

Deux fonctions auxiliaires

Liste des étiquettes des racines d'une forêt (i.e. un ens. d'arbres) :

let rec label_list f = match f with
    | [] -> []
    | Nil::q->label_list q
    | Node(_,x,_)::q->x::( label_list q);;

Liste des fils des racines d'une forêt (si ce sont des nœuds internes).

let rec sons f = match f with
    | [] -> []
    | Nil::q -> sons q
    | Node(Nil ,_,Nil)::q->sons q
    | Node(Nil ,_,d)::q-> d::( sons q)
    | Node(g,_,Nil)::q-> g::( sons q)
    | Node(g,_,d)::q-> g::(d::( sons q));;

Principe du parcours en largeur

La fonction sons retourne une forêt, label_list retourne la liste des étiquettes de la forêt.

La fonction bfs utilise la fonction aux qui prend une forêt et concatène la liste de ses étiquettes avec la liste des étiquettes des fils des racines.

let bfs t =
    let rec aux les_t = match les_t with
        | [] -> []
        | _ -> (label_list les_t) @ (aux (sons les_t))
    in aux [t];;

Complexité : chaque étiquette est ajoutée une fois et une seule à la liste résultat, $\text{on a envie de dire que la complexité est en }\Theta (n)$.

Dans ce qui suit on note $u_p$ la complexité pour calculer la liste des étiquettes de l'arbre à la profondeur $p$. Il s'agit de calculer $u_0$.

Complexité du parcours en largeur

Pour un arbre à $n$ nœuds de hauteur $h$ :

• La fonction qui récupére les étiquettes des racines d'une forêt $F$ et celle qui récupère les fils sont de complexité $\Theta (|F|)$.
• A chaque étape, on récupère la liste des étiquettes des sous-arbres d'une même profondeur et on l'ajoute au résultat.
• Lorsqu'on traite la liste des nœuds de profondeurs $p$ (disons qu'il y en a $n_p$ ) :
  • on récupère la liste de leurs étiquettes en $O(n_p)$ ;
  • on les concatènes à gauche du résultat de l'appel récursif en $O(n_p)$ ;
  • la liste des fils des nœuds de profondeur $p$ s'obtient aussi en $O(n_p)$.
  • A ceci s'ajoute le coût de l'appel interne.
• La complexité $u_p$ vérifie donc une relation de la forme : $u_p=n_p+u_{p+1}$. $\text{Donc }{u}_p-u_{p+1}=n_p$.
• Au départ $u_0-u_1=1$ (nombre de nœuds à la profondeur $0$ : racine) et $u_h-u_{h+1}=n_h$ avec $h$ la hauteur et $u_{h+1}$ qui correspond au traitement de la liste vide (pas de nœud à la profondeur $h+1$).
• On somme sur les profondeurs allant de $0$ (la racine) à $h$ (la hauteur de l'arbre). C'est une série telescopique. On obtient :

$u_0-\underset{\text{exploration liste vide}}{\underbrace{u_{h+1}}}=\sum _{p=0}^h{n}_p=\Theta (n)$

La complexité est proportionnelle au nombre de nœuds : on aurait pu s'en douter !