I. Arbres binaires

a) Définitions

Par exemple, voici un arbre binaire de recherche stockant les nombres 1, 2, 3, 4, 5, 6, 9, 10 :

Voici un arbre préfixe représentant les onomatopées "hop", "hoh", "hip", "hips" et "hih" :

Et voici l'arbre d'opération de :

Pour ces trois exemples, la structure de l'arbre est identique, mais les données stockées sont de nature différente.

b) Propriétés des arbres

On prendra pour exemple l'arbre binaire de recherche ci-dessus (de racine 4).

Ici, 4 est la racine de l'arbre.

Ici, 4 est à une profondeur de 0, et 5 est à une profondeur de 2.

Ici, la taille est 8.

Ici, la hauteur est 3, car 6 est à une profondeur de 3.

c) Et en OCaml ?

On peut définir des arbres binaires de la manière suivante :

type arbre_binaire =
    | Vide
    | N of arbre_binaire * int * arbre_binaire;;

Un nœud avec un seul fils peut être représenté par un fils vide. Une feuille peut être représentée par deux fils vides.

Les arbres binaires stricts non vides sont le plus souvent représentés par :

type arbre_binaire_strict =
    | F of int
    | N of arbre_binaire_strict * int * arbre_binaire_strict;;

C'est la forme la plus courante d'arbres binaires.

Les fonctions sur les propriétés les plus courantes peuvent être définies de la manière suivante :

let rec taille a = match a with
    | F _ -> 1
    | N (fg, _, fd) -> 1 + (taille fg) + (taille fd)
;;

let rec hauteur a = match a with
    | F _ -> 0
    | N (fg, _, fd) -> 1 + max (hauteur fg) (hauteur fd)
;;

Par exemple, avec l'arbre binaire strict dont la racine est 1, et dont les fils sont la feuille 2 et le nœud 3 (de fils 4 et 5) :

let exemple = N (F 2, 1, N (F 4, 3, F 5));;

taille exemple;;
hauteur exemple;;

Pour dessiner un arbre, le site fournit une fonction afficher_arbre. Comme elle ne connaît pas notre type, on lui donne une fonction qui "découpe" un arbre : elle renvoie None pour l'arbre vide, et sinon Some du couple (étiquette sous forme de chaîne de caractères, liste des fils).

let decoupe_strict a = match a with
    | F x -> Some (string_of_int x, [])
    | N (fg, x, fd) -> Some (string_of_int x, [fg; fd]);;

afficher_arbre decoupe_strict exemple;;

d) Preuves sur les arbres binaires

II. Arbres généraux

a) Définition

Par exemple, un arbre de décision :

b) Implémentation

On utilise le type suivant :

type arbre =
    | Vide
    | N of int * arbre list;;

Cela complique un petit peu toutes les fonctions ! La dernière fois, on traitait explicitement chacun des fils de notre arbre. Ici, ce n'est pas possible !

Deux solutions :

• une fonction auxiliaire ;
• être astucieux sur la récurrence.

Par exemple, pour calculer la somme des étiquettes d'un arbre général, avec une fonction auxiliaire :

let rec somme (arb: arbre): int =
    (*calcule la somme des sommes des arbres dans une liste d'arbres*)
    let rec aux (l: arbre list) : int = match l with
        | [] -> 0
        | a::q -> (somme a) + (aux q)
    in
    match arb with
        | Vide -> 0
        | N (x, l) -> x + (aux l)
;;

Ou bien en étant astucieux sur la récurrence :

let rec somme (arb: arbre): int =
    match arb with
        | Vide -> 0
        | N (x, []) -> x
        | N (x, a::q) -> (somme a) + (somme (N (x, q)))
;;

(* un nœud 1, de fils 2 (lui-même de fils 4 et 5) et 3 *)
let arbre_exemple = N (1, [N (2, [N (4, []); N (5, [])]); N (3, [])]);;

somme arbre_exemple;;

III. Les parcours d'arbre

Un parcours d'arbre, c'est un ordre dans lequel on va visiter les nœuds de l'arbre. Il en existe deux principaux.

Cette partie est valable autant pour les arbres binaires que pour les arbres généraux. On traitera uniquement les concepts généraux des deux parcours principaux dans ce cours ; ils seront revus plus en détail lorsqu'on parlera de graphes. Voir visualgo.

a) Parcours en profondeur

Le parcours en profondeur est celui que vous avez utilisé avec des fonctions récursives, par exemple la fonction taille d'un arbre binaire. Il s'agit d'aller le plus loin possible, et de ne faire demi-tour que lorsqu'on arrive à une feuille.

Voici l'ordre dans lequel les nœuds sont visités, sur un exemple (la fonction animer_parcours_arbre du site anime un parcours, avec la même fonction de découpage que afficher_arbre) :

b) Parcours en largeur

Au contraire, le parcours en largeur consiste à parcourir d'abord tous les nœuds de profondeur 0, puis de profondeur 1, 2, etc.

Il est très compliqué à implémenter de manière récursive, et de même, de manière impérative, ce n'est pas simple.

c) Utilité

Globalement, le parcours en profondeur a l'avantage principal d'être plus simple à implémenter, et c'est donc celui qu'on utilise quand l'ordre des sommets parcourus n'a pas d'importance.

Le parcours en largeur a en revanche des avantages, en particulier sur des arbres très grands : si notre arbre a une hauteur extrêmement grande, mais qu'on ne veut parcourir que les sommets proches de la racine, c'est lui qu'on utilisera.

d) Ordres préfixe, infixe et postfixe

Dans un parcours en profondeur, on peut traiter la racine d'un sous-arbre à différents moments par rapport à ses fils :

• ordre préfixe : la racine, puis les fils (de gauche à droite) ;
• ordre postfixe : les fils, puis la racine ;
• ordre infixe (pour les arbres binaires) : le fils gauche, puis la racine, puis le fils droit.

(* on redéfinit le type des arbres binaires : les constructeurs Vide et N
   désignent pour l'instant ceux du type arbre (général) défini plus haut *)
type arbre_binaire =
    | Vide
    | N of arbre_binaire * int * arbre_binaire;;

let rec prefixe (a: arbre_binaire) : int list = match a with
    | Vide -> []
    | N (g, x, d) -> [x] @ prefixe g @ prefixe d;;

let rec infixe (a: arbre_binaire) : int list = match a with
    | Vide -> []
    | N (g, x, d) -> infixe g @ [x] @ infixe d;;

let rec postfixe (a: arbre_binaire) : int list = match a with
    | Vide -> []
    | N (g, x, d) -> postfixe g @ postfixe d @ [x];;

(* l'arbre binaire de recherche du début du chapitre *)
let a = N (N (N (Vide, 1, Vide), 2, N (Vide, 3, Vide)), 4,
           N (N (Vide, 5, N (Vide, 6, Vide)), 9, N (Vide, 10, Vide)));;

prefixe a;;
infixe a;;
postfixe a;;

IV. Dictionnaire et arbre binaire de recherche

a) Définition

Par exemple, un arbre binaire de recherche contenant les entiers :

b) Implémentation OCaml

(*le type ocaml d'un arbre binaire de recherche sur les entiers*)
type abr =
    | Vide
    | N of abr * int * abr;;

(*recherche d'une valeur dans un arbre binaire de recherche*)
let rec recherche (a: abr) (x: int): bool = match a with
    | Vide -> false
    | N (ag, y, ad) -> if x = y then true
        else if x < y then recherche ag x
        else recherche ad x;;

(*ajout d'une valeur dans un abr*)
let rec ajout (a: abr) (x: int): abr = match a with
    | Vide -> N (Vide, x, Vide)
    | N (ag, y, ad) -> if x = y then a
        else if x < y then N (ajout ag x, y, ad)
        else N (ag, y, ajout ad x);;

(* construction de l'arbre de l'exemple par ajouts successifs *)
let rec ajout_liste (a: abr) (l: int list): abr = match l with
    | [] -> a
    | x::q -> ajout_liste (ajout a x) q;;

let exemple_abr = ajout_liste Vide [7; 5; 12; 1; 6; 10; 34; 8; 11; 28];;

recherche exemple_abr 11;;
recherche exemple_abr 9;;

Pour les arbres binaires (avec un constructeur Vide), la fonction afficher_arbre_binaire prend une fonction de découpage qui renvoie Some (gauche, étiquette, droit) : un fils gauche vide est alors bien dessiné à gauche.

let decoupe_abr a = match a with
    | Vide -> None
    | N (g, x, d) -> Some (g, string_of_int x, d);;

afficher_arbre_binaire decoupe_abr exemple_abr;;

En parcourant l'arbre dans l'ordre infixe (fils gauche, puis la racine, puis le fils droit), on obtient les éléments dans l'ordre croissant :

On peut également construire un arbre binaire de recherche à partir d'une liste en réalisant des ajouts successifs à partir de l'arbre vide.

c) Complexité des opérations

Les opérations de recherche et d'ajout s'appellent récursivement une fois pour chaque niveau de l'arbre. Si on note la hauteur de l'arbre, elles sont donc en .

Cas 1 : l'arbre est complet. Supposons qu'on ait un arbre binaire strict , tel que toutes les feuilles soient à la même profondeur. On dit qu'il est complet.

Dans ce cas, les opérations sur l'arbre binaire de recherche se font en , où est la taille de l'arbre. C'est efficace !

Cas 2 : l'arbre est une branche. Reprenons l'exemple précédent, mais en insérant simplement les entiers dans l'ordre croissant :

Dans ce cas, la hauteur de l'arbre est égale à sa taille moins 1. On a des opérations en temps linéaire : pas mieux qu'une simple liste !

Cas 3 : et en général ? En pratique, avec des éléments aléatoires, on va souvent se retrouver dans un cas proche du cas 1. Mais pour le garantir, il existe des algorithmes avancés, qui permettent de toujours avoir un arbre équilibré, et d'avoir des complexités en quoi qu'il arrive.

Exercices

let rec nb_feuilles (a: arbre_binaire) : int = match a with
    | Vide -> 0
    | N (Vide, _, Vide) -> 1
    | N (g, _, d) -> nb_feuilles g + nb_feuilles d;;

let rec minimum (a: abr) : int = match a with
    | Vide -> failwith "arbre vide"
    | N (Vide, x, _) -> x
    | N (g, _, _) -> minimum g;;

N (N (N (Vide, 4, Vide), 2, N (Vide, 5, Vide)), 1, N (Vide, 3, Vide))