Arbres binaires¶

Définition inductive¶

Définition

Un arbre binaire étiqueté par $\mathcal{E}$ est :

soit vide, et on le note alors $\text{nil}$ ou $\perp$ ;
soit un triplet $(g,x,d)$ où $x \in \mathcal{E}$ et $g$ et $d$ sont des arbres binaires.

Remarque

Cette définition inductive ressemble à la définition des listes.

On peut la formaliser en introduisant $T_b(\mathcal{E})$ l'ensemble des arbres étiquetés par $\mathcal{E}$. C'est le plus petit ensemble tel que :

$\text{nil} \in T_b(\mathcal{E})$ ;
$\forall x\in \mathcal{E}, \forall g, d \in T_b(\mathcal{E}), (g,x,d) \in T_b(\mathcal{E})$.

Les conséquences de la précision plus petit ensemble sont importantes :

les arbres sont nécessairement des expressions finies, c'est-à-dire qu'ils ne comportent qu'un nombre fini de constructions. C'est automatique car l'ensemble des arbres finis vérifie les conditions précédentes ;
pour tout triplet $(g,x,d)$ il ne peut exister qu'un arbre, sinon, en enlevant un arbre en double on vérifierait encore les deux conditions précédentes.

On en déduit directement la notion de preuve par induction structurelle sur les arbres :

\[ \forall a \in T_b(\mathcal{E}), P(a) \iff \begin{cases} P(\text{nil}) \\ \forall x \in \mathcal{E}, \forall g, d \in T_b(\mathcal{E}), P(g) \wedge P(d) \Rightarrow P(g,x,d) \end{cases} \]

Cette induction correspond à un pseudo principe de récurrence qui nous permettra de faire les preuves.

Pour démontrer cette équivalence, il suffit de vérifier que $T_P = \{ t \in T_b(\mathcal{E}), P(t) \}$ vérifie les relations de la définition inductive ; comme $T_P \subset T_b(\mathcal{E})$, par minimalité, on a bien $T_P = T_b(\mathcal{E})$.

Exemple

Si $\mathcal{E} = \N$, les éléments suivants sont des arbres :

$\text{nil}$
$(\text{nil}, 2, \text{nil})$
$( (\text{nil}, 1, \text{nil}), 2, \text{nil} )$

On adoptera une représentation graphique très naturelle pour les arbres binaires où un nœud $(g,x,d)$ sera représenté par :

Exemple

Les trois arbres précédents sont donc représentés par :

$\text{nil}$

Afin d'alléger la notation, on omettra $\text{nil}$, sauf pour l'arbre vide. On fera cependant attention à conserver les arêtes donnant sur $\text{nil}$ pour ne pas confondre $(\text{nil}, 1, (\text{nil}, 2, \text{nil}))$ et $( (\text{nil}, 2, \text{nil}), 1, \text{nil} )$. Ainsi on représentera les arbres précédents par :

Vocabulaire¶

Définition

Soit $a$ un arbre binaire. Les arbres non vides présents dans $a$ sont appelés les nœuds de $a$. Parmi ceux-ci on distingue ceux qui sont de la forme $(\text{nil},x,\text{nil})$, appelés des feuilles. Les nœuds qui ne sont pas des feuilles sont appelés des nœuds internes. Le nœud $a$ lui-même est appelé la racine de l'arbre. On note $N(a)$ l'ensemble des nœuds de $a$.

Si $n \in N(a)$ n'est pas la racine, il est le fils gauche ou le fils droit d'un unique nœud appelé le père de $n$.

Si $n \in N(a)$, on appelle sous-arbre de $a$ l'arbre dont $n$ est la racine.

Remarque

En partant de la définition inductive, il y a une identification entre un sous-arbre et sa racine. Mais afin de raisonner, on distinguera un nœud en tant qu'emplacement au sein d'un arbre et le sous-arbre lui-même.

Définition

Soit $a$ un arbre binaire.

On appelle taille de $a$, et on note $|a|$, le nombre de nœuds de $a$.
On appelle hauteur de $a$ l'entier

\[ h(a) = \begin{cases} -1 & \text{ si } a = \text{nil} \\ 1 + \max(h(g), h(d)) & \text{ si } a = (g,x,d) \end{cases} \]

Définition

Soit $a$ un arbre binaire et $n \in N(a)$. On appelle profondeur de $n$ l'unique entier $p(n)$ tel qu'il existe une suite finie $(n_0, n_1, \dots, n_{p(n)})$ de nœuds de $a$ vérifiant :

$n_0$ est la racine de $a$ ;
$n_{p(n)} = n$ ;
pour tout $i < p(n)$, $n_i$ est le père de $n_{i+1}$.

Cette suite finie est le chemin de la racine à $n$. Il est nécessairement unique car chaque nœud autre que la racine a un unique père.

Ainsi, la racine est de profondeur $0$, ses fils de profondeur $1$, etc. L'ensemble des nœuds de profondeur $p$ est appelé le niveau $p$ de l'arbre.

Théorème

Soit $a$ un arbre ; si $a$ est non vide, alors $h(a) = \max_{n \in N(a)} p(n)$.

Preuve

Par induction structurelle sur $a$.

Initialisation Si $a = \text{nil}$ la prémisse est fausse, donc l'implication est trivialement vérifiée.
- Soit $g \neq \text{nil}$ et $d \neq \text{nil}$. Dans ce cas, par hypothèse $h(g) = \max_{n \in N(g)} p_g(n)$ où $p_g(n)$ est la profondeur de $n$ en tant que nœud de l'arbre $g$. Or, mis à part la racine de $a$, le chemin menant dans $a$ au nœud $n$ est dans $g$. On a donc directement $p_g(n) = p(n) - 1$. Ainsi $h(g) = \max_{n \in N(g)} p(n) - 1$. De même, $h(d) = \max_{n \in N(d)} p(n) - 1$. On a
  
  \[h(a) = 1 + \max(h(g),h(d)) = \max\left(\max_{n\in N(g)} p(n), \max_{n \in N(d)} p(n)\right)\]
  
  Or, le seul nœud de $a$ qui n'est ni dans $g$ ni dans $d$ est sa racine, qui est de profondeur nulle donc $h(a) = \max_{n \in N(a)} p(n)$.
Hérédité Supposons la propriété vérifiée pour deux arbres $g$ et $d$, soit $x \in \mathcal{E}$, on va montrer qu'elle est vérifiée pour $a = (g,x,d)$. On a quatre cas pour le couple $(g,d)$ :
- Soit $g = \text{nil}$ et $d \neq \text{nil}$. Ainsi $h(g) = -1$ et donc $h(a) = 1 + h(d) = \max_{n \in N(d)} p(n)$ par l'analyse précédente. On conclut donc avec la propriété voulue.
- Soit $g \neq \text{nil}$ et $d = \text{nil}$. Cas symétrique du précédent.
- Soit $g = d = \text{nil}$. Auquel cas, $h(a) = 0$ qui est bien la profondeur de son unique nœud.

On a bien montré la propriété voulue par induction structurelle.

La taille et la hauteur d'un arbre binaire sont liées par l'encadrement suivant, qu'on utilisera constamment pour estimer la complexité des opérations sur les arbres.

Théorème

Pour tout arbre binaire $a$, on a $h(a) + 1 \le |a| \le 2^{h(a)+1} - 1$.

De manière équivalente, si $a$ est non vide : $\log_2(|a|+1) - 1 \le h(a) \le |a| - 1$.

Preuve

Par induction structurelle sur $a$.

Si $a = \text{nil}$ : $h(a) + 1 = 0 = |a| = 2^0 - 1$.
Si $a = (g,x,d)$ avec $g$ et $d$ vérifiant l'encadrement. Quitte à échanger les rôles, on suppose $h(g) \ge h(d)$ de sorte que $h(a) = 1 + h(g)$. On a alors $|a| = 1 + |g| + |d| \ge 1 + |g| \ge 1 + h(g) + 1 = h(a) + 1$, et $|a| = 1 + |g| + |d| \le 1 + (2^{h(g)+1} - 1) + (2^{h(d)+1} - 1) \le 2 \times 2^{h(g)+1} - 1 = 2^{h(a)+1} - 1$.

L'équivalence s'obtient en passant au $\log_2$ dans $|a| + 1 \le 2^{h(a)+1}$.

Remarque

Les deux bornes sont atteintes : la borne $|a| = h(a) + 1$ pour les arbres dont chaque nœud a au plus un fils non vide (des peignes, qui sont essentiellement des listes), la borne $|a| = 2^{h(a)+1} - 1$ pour les arbres dont tous les niveaux sont pleins (les arbres parfaits définis plus bas). Un arbre de taille $n$ a donc une hauteur comprise entre environ $\log_2 n$ et $n - 1$.

Implémentations¶

En `OCaml`¶

En OCaml, on traduit directement la définition inductive par un type récursif :

type 'a arbre = Noeud of 'a arbre * 'a * 'a arbre | Nil

On pourra alors définir des fonctions récursives sur les arbres par induction structurelle à l'aide d'un filtrage.

let rec taille a = match a with
    | Nil -> 0
    | Noeud(g,x,d) -> 1 + taille g + taille d

let rec hauteur a = match a with
    | Nil -> -1
    | Noeud(g, x, d) -> 1 + max (hauteur g) (hauteur d)

En `C`¶

En C, un nœud d'un arbre binaire a la même structure qu'un maillon d'une liste doublement chaînée : une valeur et deux pointeurs vers d'autres nœuds, nommés ici gauche et droite. L'arbre vide est représenté par le pointeur NULL.

struct noeud {
    struct noeud *gauche;
    struct noeud *droite;
    int valeur;
};

typedef struct noeud *arbre;

int taille(arbre a)
{
    if (a == NULL)
        return 0;
    return 1 + taille(a->gauche) + taille(a->droite);
}

Les fonctions de manipulation de ce type sont étudiées dans le TP sur les arbres.

Arbres binaires stricts¶

Définition

Un arbre binaire est dit strict lorsqu'aucun de ses nœuds n'a exactement un fils vide.

Cela revient à dire que seules les feuilles ont des fils vides. On peut donc omettre l'arbre vide et ne garder que les feuilles à la place.

Remarque

L'arbre de gauche ici est un arbre binaire strict alors que ce n'est pas le cas de l'arbre de droite (le nœud $c$ n'a qu'un fils non vide) :

Théorème

Soit $a$ un arbre binaire strict non vide. Si $a$ a $n$ nœuds internes, alors il a $n+1$ feuilles.

Preuve

Par induction structurelle sur les arbres stricts non vides. On note $n_i(t)$ le nombre de nœuds internes et $n_f(t)$ le nombre de feuilles de l'arbre $t$.

Initialisation Si $a$ est une feuille, il a $0$ nœud interne et $1$ feuille : on a directement la relation.
Hérédité Si $a = (g,x,d)$ n'est pas une feuille, comme $a$ est strict, $g$ et $d$ sont tous deux non vides, et ce sont des arbres stricts. On suppose la propriété vraie pour $g$ et $d$. On a $n_i(a) = 1 + n_i(g) + n_i(d)$ et $n_f(a) = n_f(g) + n_f(d) = (n_i(g) + 1) + (n_i(d) + 1) = 1 + n_i(a)$. La propriété est démontrée pour $a$.

Cela permet naturellement de considérer des arbres où les feuilles et les nœuds internes ont deux types différents d'étiquettes.

L'exemple classique d'un tel arbre est celui des expressions arithmétiques :

les nœuds internes sont étiquetés par des opérateurs binaires ;
les feuilles sont étiquetées par des nombres.

En OCaml, on peut ainsi représenter un tel arbre par le type récursif :

type ('a, 'b) arbre_bin = Feuille of 'a
    | Noeud of ('a, 'b) arbre_bin * 'b * ('a, 'b) arbre_bin

Remarque

On ne peut plus représenter l'arbre vide avec ce type.

Et pour les expressions, on pourra ainsi définir un type pour les opérateurs et écrire :

type operateur = Plus | Times | Minus | Divides

let e = Noeud(Feuille 2, Plus, Noeud(Feuille 3, Times, Feuille 4))

L'évaluation de telles expressions est étudiée dans le TP sur les arbres.

Arbres binaires complets¶

Définition

Un arbre binaire dont tous les niveaux sont pleins sauf éventuellement le dernier est dit complet. Si son dernier niveau est également plein, on dit qu'il est parfait.

Si, de plus, les nœuds du dernier niveau sont tous placés le plus à gauche possible, on dit que l'arbre est complet à gauche. C'est le cas de l'exemple ci-dessous, et c'est cette hypothèse qui permet la représentation dans un tableau.

On peut représenter un arbre complet à gauche dans un tableau niveau par niveau en partant de la racine.

Si on place les indices comme étiquettes on aura, par exemple :

Arbre complet à gauche dont chaque nœud est étiqueté par son indice.

Et on pourra donc le représenter par le tableau des étiquettes dans cet ordre d'énumération.

On remarque que :

le nœud $0$ est toujours la racine ;
si on considère un nœud $i$, son fils gauche est le nœud $2 i + 1$ et son fils droit est le nœud $2 i + 2$ ;
le fils gauche de $i+1$ est $2 (i+1) + 1 = 2i + 3$ : il vient bien directement après le fils droit de $i$ ;
le $k$-ième nœud du niveau $l$, en commençant à numéroter à $0$, a pour indice $\sum_{j=0}^{l-1} 2^j + k = 2^l - 1 + k$ ;
si $i > 0$, son père est le nœud $\left\lfloor \frac{i-1}{2} \right\rfloor$.

On peut donc, avec cette représentation, manipuler assez simplement un arbre binaire à plat.

Si le nœud de numéro $i$ a l'étiquette $e_i$, le tableau a la structure suivante :

Arbre complet stocké à plat : les fils de e_i sont e_2i+1 et e_2i+2. — Arbre complet stocké à plat : les fils de $e_i$ sont $e_{2i+1}$ et $e_{2i+2}$.

Arbres¶

Définition¶

On étend directement la définition inductive des arbres binaires au cas où les nœuds ont un nombre quelconque de fils.

Définition

Un arbre étiqueté par $\mathcal{E}$ est un couple $(x,f)$ où $x \in \mathcal{E}$ et $f$ est une suite finie d'arbres.

On étend naturellement le vocabulaire des arbres binaires :

le nœud de tête d'un arbre, en fin de compte sa valeur, est appelé sa racine ;
les éléments de $f$ sont appelés les fils du nœud ;
si $f$ est vide, on dit que le nœud est une feuille, sinon, on dit que c'est un nœud interne ;
$|f|$, le nombre d'éléments de $f$, est appelé l'arité du nœud. Les feuilles sont donc les nœuds d'arité nulle ;
une suite finie d'arbres, ou plus généralement un ensemble d'arbres, est appelé une forêt.

Si on note $T(\mathcal{E})$ l'ensemble des arbres étiquetés par $\mathcal{E}$, on a

\[ \forall x \in \mathcal{E}, \forall n \in \N, \forall a_1, \dots, a_n \in T(\mathcal{E}), (x, (a_1, \dots, a_n)) \in T(\mathcal{E}) \]

Attention contrairement à ce que peut laisser entendre la formule précédente, il est tout à fait possible que $n = 0$ ce qui correspond à la suite finie vide et donc à une feuille. On perd ici la possibilité de représenter un arbre vide.

Remarque

La taille, la hauteur et la profondeur se définissent comme pour les arbres binaires : $|(x,(a_1,\dots,a_n))| = 1 + \sum_{i=1}^n |a_i|$ et $h(x,(a_1,\dots,a_n)) = 1 + \max(-1, h(a_1), \dots, h(a_n))$. Une feuille est ainsi de hauteur $0$, ce qui est cohérent avec la convention $h(\text{nil}) = -1$ des arbres binaires.

Remarque

Un arbre binaire non vide peut être vu comme un arbre dont les nœuds sont d'arité au plus deux. On remarque en disant cela qu'on perd une information : la position gauche ou droite de l'unique fils d'un nœud unaire.

Comme pour les arbres binaires stricts, on pourra être amenés à considérer des arbres dont les nœuds internes et les feuilles sont étiquetés par des ensembles différents.

Implémentation¶

L'implémentation d'un arbre repose sur l'implémentation d'une suite finie. Celle-ci peut être faite par un tableau ou par une liste chaînée.

On retrouve alors des implémentations différentes des arbres mais qui sont, au fond, très proches.

En OCaml, on pourra alors avoir les deux implémentations suivantes (à écrire dans deux fichiers différents, car elles utilisent les mêmes noms de champs) :

type 'a arbre_l = { etiquette : 'a; enfants : 'a arbre_l list }
type 'a arbre_a = { etiquette : 'a; enfants : 'a arbre_a array }

On va alors avoir des programmes à la présentation assez différente suivant le type choisi. Voici, par exemple, les deux implémentations du calcul de la taille d'un arbre.

Avec des listes et aucune fonction du module List, on écrit souvent une fonction récursive sur les arbres et une fonction récursive sur les forêts.

let rec taille_arbre a =
    1 + taille_foret a.enfants
    and taille_foret l = match l with
        | [] -> 0
        | t::q -> taille_arbre t + taille_foret q

On peut aussi utiliser directement fold_left et map :

let rec taille_arbre a =
    1 + List.fold_left (+) 0 (List.map taille_arbre a.enfants)

Avec l'autre représentation, on procédera avec un mélange de fonction récursive et de boucles. Cela n'est pas sans rappeler ce qui a été fait pour le backtracking.

let rec taille_arbre a =
    let t = ref 1 in
    for i = 0 to Array.length a.enfants - 1 do
        t := !t + taille_arbre a.enfants.(i)
    done;
    !t

Représentation par un arbre binaire¶

Pour des raisons d'efficacité ou de réutilisation de programmes existants, on peut vouloir représenter un arbre comme un arbre binaire.

On va définir une application $\text{bin} : T(\mathcal{E}) \rightarrow T_b(\mathcal{E} \cup \{ \star \})$ ainsi : $\text{bin}(x, ()) = (\text{nil},x,\text{nil})$, $\text{bin}(x, (a)) = (\text{bin}(a),x,\text{nil})$ et pour un nœud d'arité strictement plus grande que 1 :

où $a'_i = \text{bin}(a_i)$. Les nœuds rouges sont des nœuds ayant une étiquette spéciale $\star$ telle que $\star \not \in \mathcal{E}$.

Exemple

L'arbre suivant :

sera alors représenté par l'arbre binaire :

Applications¶

Arbres d'expressions¶

On a déjà vu l'utilisation des arbres binaires pour représenter des expressions arithmétiques avec des opérateurs binaires. On généralise naturellement cela à des expressions dont les opérateurs sont d'arité quelconque.

C'est ainsi qu'on représente un programme en mémoire, on parle d'arbre syntaxique.

Arbres préfixes ou tries¶

Un arbre préfixe ou trie est un arbre permettant de représenter un ensemble de mots. On étiquette les arêtes par des caractères et les nœuds par un booléen indiquant si la suite des étiquettes qui mène de la racine à ce nœud est un mot (ce qu'on représente par $\star$).

Par exemple, le trie :

permet de représenter l'ensemble de mots : bar, barbe, art, ami, abri, abricot, abonne.

Afin de représenter un tel arbre, il est nécessaire d'avoir une étiquette sur les arêtes, le plus simple pour cela est de remplacer la liste des enfants par une liste de couples (étiquette, enfant) ainsi :

type trie = {
    mot : bool;
    enfants : (char * trie) list
    }

Les fonctions de manipulation de ce type de donnée sont étudiées dans le TP sur les arbres.

Parcours¶

Parcours récursif d'un arbre binaire¶

On a déjà vu dans les paragraphes précédents ce qui constitue le cœur du parcours d'un arbre :

let rec parcours a =
    match a with
    | Nil -> ()
    | Noeud(g, x, d) ->
        parcours g;
        parcours d

Cette fonction ne fait rien, mais elle va parcourir chacun des nœuds de l'arbre. Si on veut effectuer un traitement sur le nœud, on peut le faire à trois moments :

Les trois moments où l'on peut traiter un nœud : préfixe, infixe et postfixe.

avant l'appel à parcours g, on parle de traitement préfixe ;
entre les deux appels, on parle de traitement infixe ;
après l'appel à parcours d, on parle de traitement postfixe.

On représente ici l'ordre dans lequel on va effectuer chacun de ces trois traitements selon le code couleur : rouge pour préfixe, bleu pour infixe et vert pour postfixe. On a également indiqué, pour les premiers traitements, l'ordre dans lequel ils sont effectués par des numéros.

Ordre des traitements préfixes (rouge), infixes (bleu) et postfixes (vert) au cours du parcours.

Pour illustrer ces traitements, on peut rajouter trois arguments au parcours :

let rec parcours prefixe infixe postfixe a =
    match a with
    | Nil -> ()
    | Noeud(g, x, d) ->
        prefixe a;
        parcours prefixe infixe postfixe g;
        infixe a;
        parcours prefixe infixe postfixe d;
        postfixe a

On peut, par exemple, définir les deux fonctions suivantes :

let idle a = () (* ne fait rien *)

let print a = match a with
    | Nil -> failwith "Vide"
    | Noeud(_,x,_) -> print_char x

On peut alors observer les nœuds affichés sur l'arbre précédent selon les traitements effectués :

parcours print idle idle a : abdejkvwcfg, on suit uniquement les arêtes rouges ;
parcours idle print idle a : dbjevkwafcg, on suit uniquement les arêtes bleues ;
parcours idle idle print a : djvwkebfgca, on suit uniquement les arêtes vertes ;
parcours print print print a : abdddbejjjekvvvkwwwkebacfffcgggca, on suit toutes les arêtes.

Remarque

Si on considère un arbre d'expression comme :

On va alors obtenir en affichant à chaque traitement la suite : $+222+\times333\times444\times +$. Chaque nombre $n$ étant une feuille, on va observer l'affichage de $nnn$ qu'on peut réduire à $n$. Pour les opérateurs, on remplace le premier affichage par $($ et le dernier par $)$. En procédant ainsi, on affiche $(2+(3\times 4))$ et on a ainsi retrouvé l'écriture bien parenthésée de l'expression.

Définition

L'ordre dans lequel on effectue un traitement préfixe dans un parcours sur les nœuds d'un arbre est appelé l'ordre préfixe sur les nœuds.

On définit, de même, l'ordre infixe et l'ordre postfixe.

Parcours impératifs¶

Cadre général¶

On va considérer une structure de donnée abstraite qui généralise les piles et les files et permet de représenter un ensemble de tâches à traiter. Pour cela, on dispose d'un type paramétrique 'a t et de l'interface :

cree : unit -> 'a t crée un ensemble de tâches ;
ajoute : 'a t -> 'a -> unit ajoute une nouvelle tâche à traiter ;
retire : 'a t -> 'a retire une tâche de l'ensemble des tâches à traiter ;
est_vide : 'a t -> bool renvoie un booléen indiquant si l'ensemble de tâches est vide.

On a ainsi vu, dans le chapitre sur les piles et les files, deux implémentations possibles, qui sont elles-mêmes des structures abstraites mais un peu moins abstraites que celle-ci :

les piles pour lesquelles on retire le dernier élément ajouté ;
les files pour lesquelles on retire l'élément le plus anciennement ajouté.

On peut écrire un parcours impératif générique :

let parcours traitement a =
    let avisiter = cree () in
    ajoute avisiter a;
    while not (est_vide avisiter) do
        let a = retire avisiter in
        match a with
        | Nil -> ()
        | Noeud(g, _, d) -> traitement a;
                            ajoute avisiter g;
                            ajoute avisiter d
    done

Cas du parcours en profondeur¶

Dans le cas où on utilise une pile, on retrouve essentiellement le parcours récursif précédent avec quelques changements :

on empile ici d'abord g puis d, donc on va à droite avant d'aller à gauche. Il suffit de permuter les deux ajouts pour retrouver l'ordre précédent ;
on effectue un unique traitement préfixe ;

si on considère la pile d'appels récursifs du parcours récursif, on constate que sa taille est majorée par $h(a) + 2$. Ici, la pile explicite reste également de taille $O(h(a))$ : quand on dépile un arbre de profondeur $p$, on empile ses deux fils de profondeur $p+1$, si bien que la pile contient, à tout moment, au plus un arbre de chaque profondeur, sauf pour la plus grande profondeur présente qui peut en contenir deux. Pour un arbre d'arité quelconque, on empile en revanche tous les fils d'un nœud et la pile peut contenir jusqu'à (arité maximale) $\times$ (hauteur) éléments.

On parle de parcours en profondeur ou depth-first search (DFS) en anglais.

Exemple

Si on considère l'arbre suivant :

En ignorant les arbres vides, par exemple en ne les ajoutant pas, on va avoir le déroulement suivant du parcours (le sommet de la pile est à droite) :

avisiter	étiquette traitée
$1 \rightarrow$
$2, 3 \rightarrow$	$1$
$2, 5, 6 \rightarrow$	$3$
$2, 5 \rightarrow$	$6$
$2, 7 \rightarrow$	$5$
$2 \rightarrow$	$7$
$4 \rightarrow$	$2$
	$4$

Cas du parcours en largeur¶

Dans le cas où on utilise une file, on obtient un parcours appelé le parcours en largeur ou breadth-first search (BFS) en anglais.

Dans ce parcours, on va visiter les nœuds niveau par niveau en partant de la racine jusqu'aux feuilles de plus grande profondeur.

Exemple

Si on considère l'arbre suivant :

En ignorant les arbres vides, par exemple en ne les ajoutant pas, on va avoir le déroulement suivant du parcours (on ajoute à gauche et on retire à droite) :

avisiter	étiquette traitée
$\rightarrow 1 \rightarrow$
$\rightarrow 3, 2 \rightarrow$	$1$
$\rightarrow 4, 3 \rightarrow$	$2$
$\rightarrow 6, 5, 4 \rightarrow$	$3$
$\rightarrow 6, 5 \rightarrow$	$4$
$\rightarrow 7, 6 \rightarrow$	$5$
$\rightarrow 7 \rightarrow$	$6$
	$7$

Ce parcours est particulièrement intéressant quand on cherche une information avec la plus petite profondeur possible. Par exemple, dans le cas de la recherche d'une solution à un problème, on peut vouloir tester les petites solutions avant les plus grandes.

Pour des problèmes d'énumération, c'est également intéressant, car on va obtenir des éléments par ordre croissant de la longueur du chemin depuis la racine. Par exemple, pour les tries, on en déduit les mots par ordre croissant de longueur.

Parcours d'arbres¶

Pour des arbres, on va suivre les mêmes principes. La différence va se situer au niveau de l'implémentation car il faudra alors manipuler des listes ou des tableaux d'enfants.

Notons qu'on a déjà vu un tel problème quand on a résolu des problèmes par backtracking. En effet, avec le backtracking, on a un arbre implicite des positions partielles dont les enfants sont les mouvements possibles vers de nouvelles positions.

Arbres binaires de recherche¶

Objectif¶

On souhaite ici réaliser une structure efficace d'ensembles finis. Pour cela, on cherche à définir une structure immuable 'a ensemble munie de cinq opérations :

ensemble_vide : 'a ensemble l'ensemble vide ;
ajoute : 'a ensemble -> 'a -> 'a ensemble rajoute un élément à un ensemble et renvoie le nouvel ensemble ;
supprime : 'a ensemble -> 'a -> 'a ensemble retire un élément à un ensemble et renvoie le nouvel ensemble ;
contient : 'a ensemble -> 'a -> bool teste si l'ensemble contient un élément ;
cardinal : 'a ensemble -> int renvoie le nombre d'éléments de l'ensemble.

Notons qu'on pourra souvent relâcher la contrainte naturelle des ensembles en permettant d'ajouter plusieurs fois un même élément.

Une implémentation possible de cette structure serait d'utiliser des listes ou des tableaux triés, on aurait alors des opérations en $O(n)$ pour manipuler $n$ éléments (seul le test d'appartenance passe en $O(\log_2 n)$ dans un tableau trié, grâce à une recherche dichotomique).

Ici, on présente une implémentation rendant possible une complexité en $O(\log_2 n)$ pour chaque opération sous certaines hypothèses dont on montrera qu'elles peuvent être satisfaites dans un second temps.

Définition¶

Définition

On dit qu'un arbre $a$ étiqueté par $X$, muni d'une relation d'ordre total, est un arbre binaire de recherche (ABR) lorsque :

soit $a = \text{nil}$ ;
soit $a = (g, x, d)$ où $g$ et $d$ sont des arbres binaires de recherche et de plus

\[ \max_{y \in N(g)} e(y) \le x \le \min_{y \in N(d)} e(y) \]

où $e(y)$ est l'étiquette du nœud $y$ (la condition portant sur $g$, resp. $d$, est vide si $g$, resp. $d$, est vide).

Remarque

Tout sous-arbre d'un arbre binaire de recherche est un arbre binaire de recherche.
Pour un ensemble donné d'étiquettes il n'y a pas unicité de l'arbre binaire de recherche : voir ci-après.

Exemples d'ABR pour les ensembles $\{1,2,3\}$ et $\{1,\dots,7\}$ :

Remarque

La propriété caractéristique des ABR n'est pas locale, c'est-à-dire que tester si chaque nœud a une étiquette supérieure à son fils gauche et inférieure à son fils droit ne suffit pas. Dans l'arbre suivant, $3$ est dans le sous-arbre gauche de $2$ :

Opérations¶

Minimum et maximum¶

On peut obtenir la valeur minimale et maximale d'un ABR en effectuant un parcours le long de la branche la plus à gauche ou de la branche la plus à droite.

En effet, si l'arbre est $(g,x,d)$ : soit $g$ est vide et $x \le \min d$ est le minimum, soit $g$ est non vide et on a alors $\min g \le \max g \le x$ donc le minimum de $g$ est celui de l'arbre.

On en déduit le programme suivant :

let rec minimum a =
    match a with
    | Nil -> failwith "vide"
    | Noeud(Nil, x, _) -> x
    | Noeud(g, _, _) -> minimum g

On remarque que pour parcourir cette branche, on est en $O(h(a))$ où $a$ est l'arbre considéré.

Test si un arbre est un ABR¶

Pour tester si un arbre est bien un arbre binaire de recherche on doit connaître la valeur maximum de l'arbre gauche et minimum de l'arbre droit et tester si l'étiquette de chaque nœud $n$ vérifie

\[\max_{\eta\in A_g} e(\eta)\leq e(n)\leq \min_{\eta\in A_d} e(\eta)\]

On peut écrire une procédure qui indique si l'arbre est un arbre binaire de recherche et les valeurs minimum et maximum de l'arbre (puisqu'on doit les calculer...).

let rec abr_test a = match a with
| Nil -> failwith "Arbre vide"
| Noeud(Nil,n,Nil) -> (true, n, n)
| Noeud(Nil,n,d) -> let bd, mind, maxd = abr_test d in
    (bd && n <= mind, min n mind, max n maxd)
| Noeud(g,n,Nil) -> let bg, ming, maxg = abr_test g in
    (bg && maxg <= n, min n ming, max n maxg)
| Noeud(g,n,d) ->
    let bg, ming, maxg = abr_test g in
    let bd, mind, maxd = abr_test d in
    (bg && bd && maxg <= n && n <= mind,
     min n (min ming mind), max n (max maxg maxd))

Ici on a fait le choix de ne rien associer à l'arbre vide et de le traiter en amont au niveau des nœuds. Cela permet de ne pas imposer de contraintes sur le type des étiquettes comme cela aurait été le cas en mettant des valeurs ad hoc dans le cas de l'arbre vide (typiquement $\pm \infty$).

Remarque

On rajoute des fonctions permettant de manipuler facilement ces données et on obtient alors un algorithme de test plus concis :

let valeur a = match a with
    | None -> failwith "None n'a pas de valeur"
    | Some x -> x

let opt_bin f a b = match a, b with
    | None, _ -> b
    | _, None -> a
    | Some a, Some b -> Some (f a b)

let omax = opt_bin max
let omin = opt_bin min

let abr_test a =
    let rec aux a = match a with
        | Nil -> (true, None, None)
        | Noeud(g,n,d) ->
            let bg, ming, maxg = aux g in
            let bd, mind, maxd = aux d in
            (bg && bd && (maxg = None || valeur maxg <= n)
                && (mind = None || n <= valeur mind),
            omin (Some n) (omin ming mind),
            omax (Some n) (omax maxg maxd))
    in let est_abr, min_abr, max_abr = aux a in
    (est_abr, valeur min_abr, valeur max_abr)

Chaque nœud étant traité une fois en temps constant, ce test est en $O(|a|)$. On verra en exercice qu'une lecture infixe permet de conclure également.

Recherche d'un élément¶

Comme leur nom l'indique, la recherche est adaptée à ce type d'arbres. On peut construire la fonction de recherche :

let rec recherche x a = match a with
  |Nil -> false
  |Noeud(gauche,n,droite) when x=n -> true
  |Noeud(gauche,n,droite) when x>n -> recherche x droite
  |Noeud(gauche,n,droite)  -> recherche x gauche

Elle est correcte : si $x > n$, $x$ ne peut pas être une étiquette de gauche dont toutes les étiquettes sont $\le n$, il suffit donc de le chercher dans droite (et symétriquement si $x < n$). Elle suit une branche, d'où une complexité en $O(h(a))$.

Si l'ABR est construit par insertions successives (voir ci-dessous) des éléments pris dans un ordre aléatoire uniforme, on peut montrer (résultat admis) que sa hauteur moyenne est un $O(\log_2 n)$. Ce modèle aléatoire est étudié dans le TP (deuxième modèle).

Insertion d'un élément¶

Étant donné un arbre binaire de recherche $a$ et une étiquette $x$, on veut construire un nouvel arbre binaire de recherche contenant les étiquettes des nœuds de $a$ et $x$. Il n'y a bien sûr pas unicité de la solution... Dans un arbre binaire de recherche, l'opération se décompose en une étape de recherche, qui renvoie des informations sur la place où doit être inséré le nouvel élément, suivie de l'adjonction proprement dite.

let rec insere x a = match a with
  | Nil -> Noeud(Nil,x,Nil)
  | Noeud(gauche,n,droite) when x>n -> Noeud(gauche,n,insere x droite)
  | Noeud(gauche,n,droite) -> Noeud(insere x gauche,n,droite)

On compare $x$ à la racine pour déterminer s'il faut l'ajouter dans le sous-arbre gauche ou le sous-arbre droit, et l'on rappelle la procédure récursivement. Le dernier appel récursif se fait sur un arbre vide et l'on crée alors à cette place le nœud d'étiquette $x$. Le nouvel arbre est reconstruit de proche en proche depuis cette branche vers la racine, sans modifier les branches non explorées. Les anciens nœuds ne sont pas modifiés et l'ancien arbre reste donc disponible : c'est une structure immuable (ou persistante), qui partage avec l'ancien arbre tous les sous-arbres non explorés et ne crée que $O(h(a))$ nouveaux nœuds.

Propriété

Si $a$ est un ABR, insere x a est un ABR dont les étiquettes sont celles de $a$ et $x$ (en tant que multiensemble). Le calcul est en $O(h(a))$.

Preuve

Par induction structurelle sur $a$. Si $a = \text{nil}$, on renvoie $(\text{nil}, x, \text{nil})$ qui convient. Si $a = (g, n, d)$ et $x > n$, par hypothèse d'induction insere x d est un ABR d'étiquettes celles de $d$ et $x$ ; elles sont toutes $\ge n$ (celles de $d$ par hypothèse, et $x > n$), et $g$ est inchangé : $(g, n, \texttt{insere x d})$ est bien un ABR. Le cas $x \le n$ est symétrique. Chaque appel descend d'un niveau et fait un travail constant, d'où le $O(h(a))$.

Construction par insertion successive de l'ABR pour les éléments 5, 9, 1, 20, 4, 7, 17, 12 :

Insertions successives de 5, 9, 1, 20, 4, 7, 17, 12 ; en orange, le nœud inséré à chaque étape.

Suppression d'un élément¶

Le problème de la suppression d'un élément (ou plutôt de sa première occurrence) d'un arbre binaire de recherche est plus compliqué. On peut le décomposer en :

recherche de l'élément ;
suppression ;
recomposition de l'arbre.

Le nœud à supprimer est la racine d'un sous-arbre de l'arbre binaire de recherche. Commençons par considérer le problème de la suppression de la racine $z$ d'un arbre binaire de recherche.

Si les deux branches issues de $z$ sont vides, on supprime et c'est fini (cas a) de la figure, $z=13$).
Si l'une des deux branches issues de $z$ est vide, on se contente de garder l'autre branche. On conserve ainsi un arbre binaire de recherche (cas b) de la figure, $z=16$).
Si les deux branches sont non vides, soit $y$ l'élément le plus à gauche du sous-arbre droit $A_d$ de $z$, c'est-à-dire son minimum. On a $y \ge z$ par la propriété des ABR.

Remarquons que $y$ ne peut avoir de fils gauche car sinon il ne serait pas le plus à gauche de $A_d$.

On peut donc le supprimer et le reporter en lieu et place de $z$ : on obtient alors un nouvel arbre qui est un arbre binaire de recherche. En effet :
- la branche droite est un arbre binaire de recherche (on a supprimé un nœud sans fils gauche) et l'étiquette de la racine $y$ est, par construction, inférieure ou égale aux étiquettes des nœuds de cette branche ;
- la branche gauche est un arbre binaire de recherche (on n'y a pas touché) et la nouvelle étiquette de la racine $y$ est supérieure ou égale à $z$ qui majorait les étiquettes des nœuds de la branche gauche.
(cas c) de la figure, $z=5$ et $y=6$).

Les trois cas de suppression :

Cas a) : z (en rouge) n'a pas de fils, on le supprime. — Cas a) : $z$ (en rouge) n'a pas de fils, on le supprime.

Cas b) : z n'a qu'un fils, son sous-arbre prend sa place. — Cas b) : $z$ n'a qu'un fils, son sous-arbre prend sa place.

Cas c) : z est remplacé par le minimum y de son sous-arbre droit. — Cas c) : $z$ est remplacé par le minimum $y$ de son sous-arbre droit.

On en déduit le programme suivant :

let rec supprime a x =
    match a with
    | Nil -> Nil
    | Noeud(g, y, d) when y < x ->
        Noeud(g, y, supprime d x)
    | Noeud(g, y, d) when y > x ->
        Noeud(supprime g x, y, d)
    (* à partir d'ici l'étiquette est forcément x *)
    | Noeud(Nil, _, Nil) -> Nil
    | Noeud(Nil, _, d) -> d
    | Noeud(g, _, Nil) -> g
    | Noeud(g, _, d) ->
        let y = minimum d in
        Noeud(g, y, supprime d y)

La recherche de $x$, celle du minimum de d puis la suppression de $y$ dans d suivent chacune une branche : la suppression est en $O(h(a))$. La correction se démontre par induction structurelle sur $a$, comme pour l'insertion, en utilisant l'analyse des trois cas ci-dessus.

Équilibrage¶

Principe et approche naïve¶

Les opérations précédentes sont toutes en $O(h(a))$, or on a vu que $h(a) + 1 \le |a| \le 2^{h(a)+1} - 1$ donc $\log_2 (|a| + 1) - 1 \le h(a) \le |a| - 1$. On aimerait se rapprocher au plus de $\log_2 |a|$ et pour cela, il faut que l'arbre soit le plus proche possible d'un arbre parfait. On parle alors d'équilibrage.

Par exemple, insérer successivement $1, 2, \dots, n$ dans un ABR vide produit un peigne de hauteur $n-1$ : toutes les opérations sont alors en $O(n)$.

Une approche naïve consiste à extraire les valeurs dans l'ordre croissant à l'aide d'un parcours infixe puis à reconstruire un arbre équilibré par dichotomie : on place la valeur médiane à la racine et on construit récursivement les sous-arbres gauche et droit. Cela coûte $O(n)$ à chaque rééquilibrage : on cherche donc plutôt des structures qui restent équilibrées au fil des opérations.

Arbres 2-3¶

Définition

Un arbre 2-3 est un arbre étiqueté, éventuellement vide, contenant des nœuds de deux types :

des nœuds binaires $N(g,x,d)$ où $g,d$ sont des arbres 2-3 et $x$ une étiquette tels que $\max g \le x \le \min d$ (c'est la même condition que les ABR) ;
des nœuds ternaires $M(g,x,m,y,d)$ où $g,m,d$ sont des arbres 2-3 et $x,y$ sont des étiquettes telles que : $\max g \le x \le \min m \le \max m \le y \le \min d$.

et parfaitement équilibré : tous les chemins de la racine à un arbre vide ont même longueur. En particulier les fils d'un nœud sont soit tous vides (le nœud est alors une feuille), soit tous non vides.

Un nœud ternaire contient donc un fils central dont les valeurs sont comprises entre ses deux étiquettes.

Voici un exemple d'arbre 2-3 :

Théorème

Un arbre 2-3 non vide à $n$ nœuds est de hauteur au plus $\log_2(n+1) - 1 \le \lfloor \log_2 n \rfloor$.

Preuve

Montrons par récurrence sur $h \ge 0$ qu'un arbre 2-3 de hauteur $h$ a au moins $2^{h+1} - 1$ nœuds. Pour $h = 0$, l'arbre est une feuille : il a $1$ nœud. Si $h > 0$, la racine a au moins deux fils, tous de hauteur $h-1$ par équilibre parfait, qui ont donc chacun au moins $2^h - 1$ nœuds par hypothèse de récurrence ; l'arbre a donc au moins $1 + 2(2^h - 1) = 2^{h+1} - 1$ nœuds.

Ainsi $n + 1 \ge 2^{h+1}$, soit $h \le \log_2(n+1) - 1$. Comme $h$ est entier et $\log_2(n+1) - 1 < \log_2 n$ pour $n \ge 1$, on a $h \le \lfloor \log_2 n \rfloor$. Le maximum est atteint quand tous les nœuds sont binaires : les nœuds ternaires rendent l'arbre plus compact.

Recherche

Pour rechercher un élément $x$ on adapte l'algorithme des ABR :

pour un nœud binaire $N(g,y,d)$
- si $x < y$ on cherche dans $g$ ;
- si $x = y$ on a trouvé le nœud voulu ;
- si $x > y$ on cherche dans $d$.
pour un nœud ternaire $M(g,y,m,z,d)$
- si $x < y$ on cherche dans $g$ ;
- si $x = y$ ou $x = z$ on a trouvé le nœud voulu ;
- si $y < x < z$ on cherche dans $m$ ;
- si $z < x$ on cherche dans $d$.

La complexité de cet algorithme est donc encore en $O(h)$ où $h$ est la hauteur de l'arbre. D'après le théorème précédent, elle est en $O(\log n)$.

Insertion

Pour insérer un élément $x$ dans un arbre 2-3, on va temporairement enrichir sa structure par des nœuds quaternaires satisfaisant les mêmes conditions sur les clés que les nœuds binaires et ternaires.

Pour insérer, on effectue alors une recherche qui nous amène à la feuille où $x$ doit être placé. On transforme alors cette feuille en augmentant son arité et en plaçant $x$ à la bonne position par rapport aux étiquettes qu'elle contient. L'équilibre parfait est préservé, car on n'a créé aucun nouveau niveau.

Exemples :

insertion de 1 dans

donne
insertion de 8 dans

donne

Maintenant on va supprimer les nœuds quaternaires en les faisant remonter, au pire, jusqu'à la racine pour laquelle on peut faire l'opération suivante :

$\rightarrow$

Voici tous les cas de transformations selon le type du père et la position du nœud quaternaire :

fils gauche d'un binaire :

$\rightarrow$
fils droit d'un binaire :

$\rightarrow$
fils gauche d'un ternaire :

$\rightarrow$
fils central d'un ternaire :

$\rightarrow$
fils droit d'un ternaire :

$\rightarrow$

On observe rapidement que toutes ces transformations préservent la position des sous-arbres vis-à-vis des étiquettes des nœuds, ainsi que la profondeur des sous-arbres $A_i$ (sauf l'éclatement de la racine, qui augmente de un la profondeur de tous les nœuds, donc préserve l'équilibre parfait). Chaque transformation fait remonter le nœud quaternaire d'un niveau, ou le fait disparaître. Ainsi, au final, on aura obtenu un arbre 2-3, en $O(h)$ étapes.

Remarque sur l'implémentation

Les arbres 2-3 sont simples à comprendre mais complexes à programmer :

beaucoup de cas à traiter, notamment en fonction des parents ;
des nœuds intermédiaires 2-3-4 qui demandent d'avoir un type de travail et un type final.

On va voir dans un dernier temps des arbres quasiment équivalents à ceux-ci mais bien plus simples à programmer.

Arbres rouges et noirs¶

On va transformer un arbre 2-3 en ABR en transformant les nœuds ternaires ainsi :

$\rightarrow$

Afin de se souvenir que le nœud $b$ provient de cette séparation, on le marque en rouge. Ici on a également marqué l'arête droite en rouge mais on l'omettra dans la suite.

Quelques remarques, en convenant que les arbres vides sont noirs :

la racine est noire et les arbres vides sont noirs ;
le fils gauche d'un nœud est toujours noir ;
il ne peut exister d'arêtes liant deux nœuds rouges car par construction les nœuds rouges sont toujours entourés de nœuds noirs ;
les chemins de la racine aux feuilles dans l'arbre 2-3 sont tous de même longueur et à chacun des nœuds de l'arbre 2-3 correspond exactement un nœud noir, on en déduit donc que tous les chemins de la racine aux arbres vides contiennent le même nombre de nœuds noirs.

Réciproquement un ABR dont les nœuds peuvent avoir ces deux couleurs et qui vérifie ces propriétés est appelé un arbre rouge et noir.

En fait, on a une bijection entre les arbres 2-3 et les arbres rouges et noirs ainsi définis.

Remarque

La condition « le fils gauche d'un nœud est toujours noir » est spécifique à la variante présentée ici, qui est celle qui correspond exactement aux arbres 2-3 (les arbres rouges et noirs penchés, introduits par R. Sedgewick, ici penchés à droite). Dans la définition usuelle des arbres rouges et noirs, un nœud noir peut avoir deux fils rouges (ce qui correspond à un nœud quaternaire d'un arbre 2-3-4), et seules les trois autres conditions sont imposées.

La proposition suivante permet de voir que les arbres rouges et noirs sont de bons ABR :

Théorème

La hauteur d'un arbre rouge et noir est au plus égale à $2h + 1$ où $h$ est la hauteur de l'arbre 2-3 qui lui est associé.

Ainsi tout arbre rouge et noir de taille $n \ge 1$ est de hauteur au plus $2 \log_2(n+1) - 1$, donc $O(\log n)$.

Preuve

Un chemin de la racine vers un nœud de l'arbre rouge et noir contient au plus $h + 1$ nœuds noirs, un par nœud de l'arbre 2-3 traversé. Comme la racine est noire et qu'un nœud rouge a toujours un père noir, il contient au plus autant de nœuds rouges que de nœuds noirs. Il a donc au plus $2(h+1)$ nœuds, soit au plus $2h + 1$ arêtes.

L'arbre 2-3 associé a au plus $n$ nœuds (chacun correspond à un ou deux nœuds de l'arbre rouge et noir), donc $h \le \log_2(n+1) - 1$ d'après le théorème sur les arbres 2-3, ce qui donne une hauteur au plus $2\log_2(n+1) - 1$.

Pour l'insertion d'un nœud, on va déstabiliser la coloration en mettant trop de nœuds rouges, puis on va rétablir les contraintes en remontant vers la racine. Cela rappelle l'élimination des nœuds quaternaires des arbres 2-3. Mettre des nœuds rouges a l'avantage de préserver l'équilibrage noir.

Pour rétablir les couleurs, on va alors utiliser une succession de deux opérations élémentaires : les rotations et la bascule.

Rotations

On définit les deux rotations gauche et droite, duales l'une de l'autre, ainsi :

Ici, on a utilisé la couleur bleue pour représenter la couleur du nœud de départ qui peut être soit rouge soit noire mais va être préservée.

Les rotations permettent donc de faire pencher des nœuds rouges à droite ou à gauche. Elles préservent la propriété d'ABR, car l'ordre infixe $A_1, y, A_2, x, A_3$ est le même dans les deux arbres.

On remarque que la hauteur en nœuds noirs de l'arbre n'a pas changé.

On peut passer d'une des trois représentations convenables des nœuds quaternaires à une autre à l'aide de rotations :

Les trois représentations d'un nœud quaternaire, reliées par des rotations.

Bascule

Une autre opération importante dans les arbres rouges et noirs est la bascule qui permet de faire remonter les défauts de coloration vers la racine tout en préservant l'équilibre en nœuds noirs :

Si on effectue une bascule directement sur la racine de l'arbre considéré, on finit par la noircir ce qui augmente de un la profondeur noire de chaque feuille mais ne change pas l'équilibrage global.

Insertion

Selon les remarques précédentes, on ne va pas hésiter à perdre la propriété des arbres rouges et noirs temporairement. De toutes les propriétés de ces arbres, c'est sûrement le fait qu'ils soient parfaitement équilibrés en nœuds noirs qui est le plus dur à assurer. On ne va donc pas toucher à cette propriété : on va insérer des nœuds rouges à la place d'un arbre vide.

En faisant cela on risque d'avoir deux types de problèmes :

des arêtes rouge-rouge ;
des fils gauches rouges.

On va alors traiter les différents cas d'insertion et voir comment on peut les ajuster pour obtenir des arbres rouges et noirs.

Insertion dans un nœud issu d'un nœud binaire

Un nœud noir issu d'un nœud binaire a nécessairement ses deux fils qui sont vides ou non vides simultanément, car ils proviennent directement de la structure parfaitement équilibrée des arbres 2-3.

On a alors les deux cas suivants d'insertion :

Le nœud inséré (cerclé d'orange) est rouge : on obtient directement un nœud ternaire.

Insertion à gauche puis rotation droite ; le nœud inséré est cerclé d'orange.

Dans les deux cas on se ramène à un nœud ternaire directement.

Insertion dans un nœud issu d'un nœud ternaire

On a trois cas d'insertion selon la position de la nouvelle valeur par rapport aux deux valeurs du nœud ternaire.

Supposons que l'on insère $z$ dans l'arbre :

Si $x \le y \le z$ :
Si $z \le x \le y$ :
Si $x \le z \le y$ :

Ici, on ne peut pas rétablir tout de suite la structure mais on peut faire remonter le problème jusqu'à la racine, quitte à faire une bascule finale qui va la noircir. On va donc partir d'un des trois problèmes précédents mais supposer qu'il se situe sur un nœud quelconque avec des sous-arbres rouges et noirs $t_1, t_2, t_3$ et $t_4$.

Cas x le y le z : rotation gauche puis bascule (z inséré, cerclé d'orange). — Cas $x \le y \le z$ : rotation gauche puis bascule ($z$ inséré, cerclé d'orange).

Cas z le x le y : une bascule suffit. — Cas $z \le x \le y$ : une bascule suffit.

Cas x le z le y : rotation droite en y, rotation gauche, puis bascule. — Cas $x \le z \le y$ : rotation droite en $y$, rotation gauche, puis bascule.

On remarque qu'on effectue essentiellement les mêmes opérations, et quitte à les inhiber quand on ne peut pas les appliquer, on peut se dire que pour insérer $z$ dans l'arbre $a$, on le rajoute récursivement à gauche ou à droite, on obtient ainsi $a'$ et on effectue alors

\[ (\text{bascule}^? \circ \text{rot\_gauche}^? \circ \text{rot\_droite}^?)(a') \]

où ici, $\text{op}^?$ signifie qu'on effectue l'opération uniquement si elle s'applique :

pour une rotation droite, il faut que le fils gauche soit rouge et le fils droit noir, pour ne pas tomber dans le cas d'une bascule ;
pour une rotation gauche, il faut que le fils droit et le fils droit du fils droit soient rouges ;
pour une bascule, que les deux fils soient rouges.

Implémentation

On commence par définir le type des arbres rouges et noirs :

type couleur = R | N
type 'a arn = Nil | Noeud of couleur * 'a arn * 'a * 'a arn

On définit ensuite des fonctions qui nous seront utiles vu la remarque précédente pour tester les couleurs à gauche et à droite :

let gauche a = match a with
    | Nil -> failwith "Invalide"
    | Noeud(_,g,_,_) -> g
let droite a = match a with
    | Nil -> failwith "Invalide"
    | Noeud(_,_,_,d) -> d
let couleur a = match a with
    | Nil -> N
    | Noeud(c,_,_,_) -> c
let rouge a = couleur a = R
let noir a = not (rouge a)

On implémente alors les rotations et la bascule avec le filtrage.

let rotation_gauche a = match a with
    | Noeud(c,t1,x,Noeud(R,t2,y,t3)) ->
            Noeud(c,Noeud(R,t1,x,t2),y,t3)
    | _ -> failwith "Invalide"
let rotation_droite a = match a with
    | Noeud(c,Noeud(R,t1,x,t2),y,t3)
        -> Noeud(c,t1,x,Noeud(R,t2,y,t3))
    | _ -> failwith "Invalide"
let bascule a = match a with
    | Noeud(N,Noeud(R,t1,x,t2),y,Noeud(R,t3,z,t4))
        -> Noeud(R,Noeud(N,t1,x,t2),y,Noeud(N,t3,z,t4))
    | _ -> failwith "Invalide"
let noircit a = match a with
    | Noeud(_,g,x,d) -> Noeud(N,g,x,d)
    | Nil -> Nil

Puis, les versions optionnelles qui ne s'effectuent que si c'est nécessaire :

let essai_rotgauche a =
    if rouge (droite a) && rouge (droite (droite a))
    then rotation_gauche a else a
let essai_rotdroite a =
    if rouge (gauche a) && noir (droite a)
    then rotation_droite a else a
let essai_bascule a =
    if rouge (gauche a) && rouge (droite a)
    then bascule a else a

On peut alors réaliser l'insertion récursivement :

let insere a x =
    let rec aux a =
        match a with
        | Nil -> Noeud(R,Nil,x,Nil)
        | Noeud(c,g,y,d) ->
            let a' =
                if x < y
                then Noeud(c,aux g,y,d)
                else Noeud(c,g,y,aux d)
            in
            essai_bascule
                (essai_rotgauche
                    (essai_rotdroite a'))
    in noircit (aux a)

Propriété

Soit $a$ un sous-arbre d'un arbre rouge et noir, de hauteur noire $b$ (nombre de nœuds noirs sur chaque chemin vers un arbre vide). Alors aux a est un ABR contenant les étiquettes de $a$ et $x$, de même hauteur noire $b$, et :

si la racine de $a$ est noire (ou $a$ vide), aux a vérifie toutes les conditions des arbres rouges et noirs, sauf éventuellement que sa racine peut être rouge ;
si la racine de $a$ est rouge, aux a a une racine rouge et vérifie toutes les conditions, sauf éventuellement qu'un de ses fils peut être rouge (ce fils ayant lui-même deux fils noirs).

Par conséquent insere a x est un arbre rouge et noir, et l'insertion est en $O(\log n)$.

Preuve (esquisse)

Par induction structurelle sur $a$. Les rotations et la bascule préservent la propriété d'ABR et la hauteur noire, l'appel récursif aussi par hypothèse d'induction. Le défaut renvoyé par l'appel récursif est situé à la racine du fils modifié ; les figures précédentes traitent exactement les situations possibles :

un nœud noir dont un fils (issu d'un nœud binaire) devient rouge : c'est le cas binaire, réglé par au plus une rotation droite ;
un nœud noir dont les deux fils sont rouges : une bascule fait remonter le défaut (la racine devient rouge) ;
un nœud noir dont le fils droit rouge a un fils rouge : une rotation droite éventuelle (effectuée lors du traitement du fils rouge) puis une rotation gauche et une bascule.

Enfin noircit rend la racine noire, ce qui augmente de un la hauteur noire de tous les chemins à la fois. Le calcul suit une branche avec un travail constant par niveau, d'où le $O(h) = O(\log n)$ d'après le théorème précédent.

Remarque

Ce code a été testé en comparant, après chaque insertion d'éléments aléatoires (ou croissants), le parcours infixe de l'arbre avec la liste triée des éléments insérés, et en vérifiant les invariants : racine noire, pas de fils gauche rouge, pas d'arête rouge-rouge, même nombre de nœuds noirs sur toutes les branches, hauteur au plus $2\log_2(n+1) - 1$.

Tas¶

Présentation¶

On va considérer une structure de donnée permettant de réaliser efficacement deux opérations :

récupérer la plus grande des valeurs ajoutées et la supprimer ;
ajouter une nouvelle valeur.

Avec des arbres, on cherche à réaliser ces opérations en $O(\log n)$ où $n$ est le nombre de valeurs présentes.

Définition

On appelle tas sur l'ensemble $X$ un arbre binaire étiqueté par $X$ et complet à gauche tel que pour tout nœud de l'arbre, son étiquette est supérieure ou égale à celle de ses fils.

Exemple

Un tas : chaque nœud a une étiquette supérieure ou égale à celles de ses fils.

Remarque

On parle de heap en anglais. Ici, nous présentons des tas-max permettant de déduire le maximum, on pourrait définir des tas-min, mais quitte à renverser la relation d'ordre, il s'agit de la même structure.

Remarque

Par transitivité, l'étiquette d'un nœud est supérieure ou égale à toutes les étiquettes de son sous-arbre : le maximum est à la racine. Un tas à $n$ nœuds étant complet, sa hauteur est $\lfloor \log_2 n \rfloor$ (il a au moins $2^h$ nœuds : les niveaux $0$ à $h-1$ sont pleins et le niveau $h$ est non vide).

Opérations¶

Dans les deux opérations qu'on souhaite implémenter, on va avoir besoin d'un accès rapide à la dernière feuille insérée et à la place, à sa droite, de la prochaine feuille qu'on pourrait insérer.

Insertion¶

Pour insérer un élément dans un tas on adopte la stratégie suivante :

on le place dans la seule place libre permettant de garantir que l'arbre soit complet à gauche ;
on l'insère à la bonne place sur la branche qui le relie à la racine en effectuant des échanges successifs jusqu'à ce que la condition de tas soit vérifiée (étape appelée remontée du tas).

On va illustrer cet algorithme sur un exemple.

On part du tas

dans lequel on insère la valeur 15.

On commence par ajouter ce nœud dans le premier emplacement libre à droite de 10 :

Comme le fils gauche de 12 a une valeur plus grande que celui-ci on échange les étiquettes pour obtenir :

Maintenant le père de 15 est bien plus grand que celui-ci, on s'arrête car on a obtenu un tas.

Remarque

Pendant la remontée, la condition de tas est vérifiée partout sauf éventuellement entre le nœud $i$ contenant la nouvelle valeur $v$ et son père $p$. Si $e_p < v$, on les échange : $v$ est plus grande que l'ancienne étiquette $e_p$, elle-même plus grande que l'autre fils de $p$ et que le sous-arbre de $i$, donc la condition devient vraie autour de $p$ et le seul défaut possible remonte entre $p$ et son père. On s'arrête à la racine ou quand $e_p \ge v$ : on a alors un tas.

Extraction du maximum¶

Pour supprimer la racine :

soit $x$ l'étiquette du nœud situé juste avant le prochain emplacement libre (il s'agit de la dernière position remplie par une insertion), on place la valeur $x$ à la racine et on supprime le nœud où était situé $x$, ce qui préserve le caractère complet à gauche ;
on fait ensuite descendre $x$ en l'échangeant à chaque étape avec le plus grand de ses fils, tant que celui-ci est plus grand que $x$ : choisir le plus grand garantit que le nouveau père respecte bien la condition de tas vis-à-vis de ses deux fils (étape appelée descente du tas).

Sur le tas suivant on a $x = 12$

La racine 23 (en rouge) est supprimée et remplacée par x = 12 (en orange). — La racine $23$ (en rouge) est supprimée et remplacée par $x = 12$ (en orange).

On obtient donc après la première étape l'arbre

On échange alors $12$ avec $20$ qui est le plus grand des fils :

Maintenant $12$ est à la bonne place : on a obtenu un tas.

Complexité¶

Dans l'hypothèse de pouvoir accéder rapidement (au moins en $O(\log n)$) à la fin du dernier niveau, on peut réaliser ces deux opérations en remontant ou en descendant le long d'une branche, donc en $O(\log n)$ puisque la hauteur du tas est $\lfloor \log_2 n \rfloor$.

Implémentation¶

On va reposer sur l'implémentation à plat d'un arbre comme décrit précédemment. On va supposer qu'on dispose d'une constante $N$ et que l'on sait que le tas contiendra au maximum $N$ valeurs. Cette implémentation est alors à rapprocher de celle faite pour les files ou les piles dans des tableaux.

struct tas {
    int *elements;
    int taille;
    int taille_max;
};
typedef struct tas tas;

tas *tas_cree(int N)
{
    tas *t = malloc(sizeof(tas));
    t->elements = malloc(N * sizeof(int));
    t->taille = 0;
    t->taille_max = N;
    return t;
}

void tas_libere(tas *t)
{
    free(t->elements);
    free(t);
}

void swap(int *t, int i, int j)
{
    int z = t[i];
    t[i] = t[j];
    t[j] = z;
}

int pere(int i)
{
    return (i-1)/2;
}

int gauche(int i)
{
    return 2*i+1;
}

int droite(int i)
{
    return 2*i+2;
}

void tas_insere(tas *t, int x)
{
    assert(t->taille < t->taille_max);
    int n = t->taille;
    t->taille++;
    t->elements[n] = x;
    while(n > 0 && t->elements[pere(n)] < t->elements[n])
    {
        swap(t->elements, n, pere(n));
        n = pere(n);
    }
}

bool feuille(tas *t, int i)
{
    return gauche(i) >= t->taille;
}

// Indice du plus grand des fils de i, qu'on suppose ne pas être une feuille
int fils_max(tas *t, int i)
{
    int g = gauche(i);
    int d = droite(i);
    if (d < t->taille && t->elements[d] > t->elements[g])
        return d;
    return g;
}

int tas_extrait_max(tas *t)
{
    assert(t->taille > 0);
    int racine = t->elements[0];
    t->taille--;
    t->elements[0] = t->elements[t->taille];

    int n = 0;
    while(!feuille(t, n) && t->elements[n] < t->elements[fils_max(t, n)])
    {
        int f = fils_max(t, n);
        swap(t->elements, n, f);
        n = f;
    }

    return racine;
}

Application au tri¶

Pour trier, il suffit de créer un tas, d'insérer tous les éléments puis de les extraire un à un. On appelle cela le tri par tas. C'est d'ailleurs l'origine historique de la structure de donnée. Il est en $O(n \log n)$, puisqu'on fait $n$ insertions et $n$ extractions en $O(\log n)$.

Une manière intéressante de faire cet algorithme consiste à le faire en place, c'est-à-dire sans utiliser un autre tableau pour le tri. Pour cela, on va maintenir dans le même tableau le tas en construction en préfixe et les éléments à insérer en suffixe.

Pour reconstruire le tableau trié, il suffit alors d'extraire les maximums et de les placer à la fin du tableau en faisant ici grossir le suffixe trié et réduire le tas préfixe.

void heapify(int *t, int sz)
{
    for(int i = 1; i < sz; i++)
    {
        int j = i;
        while(j > 0 && t[(j-1)/2] < t[j])
        {
            int p = (j-1)/2;
            swap(t, j, p);
            j = p;
        }
    }
}

void sort(int *t, int sz)
{
    heapify(t, sz);
    for(int i = sz-1; i > 0; i--)
    {
        // le tas occupe t[0..i] : on place son maximum en position i
        swap(t, i, 0);
        // le tas occupe maintenant t[0..i-1] : on fait descendre t[0]
        int j = 0;
        while(2*j+1 < i)
        {
            int c = 2*j+1;
            if (c+1 < i && t[c+1] > t[c])
                c = c+1;
            if (t[j] >= t[c])
                break;
            swap(t, j, c);
            j = c;
        }
    }
}

Application aux files de priorité¶

À la manière des dictionnaires, on peut considérer des couples $(\textit{prio}, \textit{val})$ pour les étiquettes en utilisant uniquement la première composante dans le tas. Ainsi, on réalise la structure de données files de priorité introduite dans un chapitre précédent.

Exercices¶

Reconstruction¶

Exercice

On considère un arbre binaire à 27 nœuds étiquetés par les lettres A, B, ..., Z et &.

On connaît l'ordre des étiquettes vues dans un parcours préfixe :

I Q J H L E M V O T S B R G Y Z K C A & F P N U D W X

et dans un parcours postfixe :

H E M L J V Q S G Y R Z B T C P U D N F W & X A K O I

Dessiner cet arbre binaire.

Exercice

On rappelle qu'un arbre binaire est strict si chaque nœud qui n'est pas une feuille a exactement deux fils non vides.

Décrire et analyser un algorithme récursif qui reconstruit un arbre binaire strict étant donné son ordre préfixe et son ordre postfixe.
Montrer que ce n'est pas possible de réaliser un tel algorithme sans savoir que l'arbre est strict.

Lecture infixe d'un ABR¶

Exercice

Montrer qu'un arbre binaire est un ABR si et seulement si la suite de ses étiquettes dans l'ordre infixe est croissante.
En déduire une fonction est_abr : 'a arbre -> bool en $O(|a|)$.

Corrigé

Par induction structurelle. Pour $\text{nil}$, les deux propriétés sont vraies. Pour $a = (g,x,d)$, la suite infixe est $L_g, x, L_d$ où $L_g$ et $L_d$ sont les suites infixes de $g$ et $d$. Elle est croissante si et seulement si $L_g$ et $L_d$ sont croissantes, $\max L_g \le x$ et $x \le \min L_d$, c'est-à-dire, par hypothèse d'induction, si et seulement si $g$ et $d$ sont des ABR et $\max g \le x \le \min d$ : c'est la définition d'un ABR.

On construit la liste infixe en temps linéaire avec un accumulateur, puis on vérifie qu'elle est croissante.

let est_abr a =
    let rec infixe a acc = match a with
        | Nil -> acc
        | Noeud(g, x, d) -> infixe g (x :: infixe d acc)
    in
    let rec croissante l = match l with
        | x :: y :: q -> x <= y && croissante (y :: q)
        | _ -> true
    in
    croissante (infixe a [])

avisiter	étiquette traitée
\(1 \rightarrow\)
\(2, 3 \rightarrow\)	\(1\)
\(2, 5, 6 \rightarrow\)	\(3\)
\(2, 5 \rightarrow\)	\(6\)
\(2, 7 \rightarrow\)	\(5\)
\(2 \rightarrow\)	\(7\)
\(4 \rightarrow\)	\(2\)
	\(4\)

avisiter	étiquette traitée
\(\rightarrow 1 \rightarrow\)
\(\rightarrow 3, 2 \rightarrow\)	\(1\)
\(\rightarrow 4, 3 \rightarrow\)	\(2\)
\(\rightarrow 6, 5, 4 \rightarrow\)	\(3\)
\(\rightarrow 6, 5 \rightarrow\)	\(4\)
\(\rightarrow 7, 6 \rightarrow\)	\(5\)
\(\rightarrow 7 \rightarrow\)	\(6\)
	\(7\)

Arbres binaires¶

Définition inductive¶

Vocabulaire¶

Implémentations¶

En OCaml¶

En C¶

Arbres binaires stricts¶

Arbres binaires complets¶

Arbres¶

Définition¶

Implémentation¶

Représentation par un arbre binaire¶

Applications¶

Arbres d'expressions¶

Arbres préfixes ou tries¶

Parcours¶

Parcours récursif d'un arbre binaire¶

Parcours impératifs¶

Cadre général¶

Cas du parcours en profondeur¶

Cas du parcours en largeur¶

Parcours d'arbres¶

Arbres binaires de recherche¶

Objectif¶

Définition¶

Opérations¶

Minimum et maximum¶

Test si un arbre est un ABR¶

Recherche d'un élément¶

Insertion d'un élément¶

Suppression d'un élément¶

Équilibrage¶

Principe et approche naïve¶

Arbres 2-3¶

Arbres rouges et noirs¶

Tas¶

Présentation¶

Opérations¶

Insertion¶

Extraction du maximum¶

Complexité¶

Implémentation¶

Application au tri¶

Application aux files de priorité¶

Exercices¶

Reconstruction¶

Lecture infixe d'un ABR¶

En `OCaml`¶

En `C`¶