TD n° 5 : Arbres

In [1]:
type ('f, 'n) arbre =
    | Feuille of 'f
    | NoeudInterne of ('f, 'n) arbre * 'n * ('f, 'n) arbre
;;
Out[1]:
type ('f, 'n) arbre =
    Feuille of 'f
  | NoeudInterne of ('f, 'n) arbre * 'n * ('f, 'n) arbre

Exercice 1

In [2]:
let arbre =
  NoeudInterne (Feuille 2, 1, NoeudInterne (Feuille 4, 3, Feuille 5))
;;
Out[2]:
val arbre : (int, int) arbre =
  NoeudInterne (Feuille 2, 1, NoeudInterne (Feuille 4, 3, Feuille 5))

Exercice 2

In [3]:
let rec symetrique arbre =
  match arbre with
  | Feuille _ -> arbre
  | NoeudInterne (fils_gauche, noeud, fils_droit) ->
    NoeudInterne (symetrique fils_droit, noeud, symetrique fils_gauche)
;;
Out[3]:
val symetrique : ('a, 'b) arbre -> ('a, 'b) arbre = <fun>
In [4]:
symetrique arbre;;
Out[4]:
- : (int, int) arbre =
NoeudInterne (NoeudInterne (Feuille 5, 3, Feuille 4), 1, Feuille 2)

Exercice 3

1.

In [5]:
let rec initialise_complet n val_f val_n =
  match n with
  | 0 -> Feuille val_f
  | _ -> let arbre = initialise_complet (n - 1) val_f val_n in
	 NoeudInterne (arbre, val_n, arbre)
;;
Out[5]:
val initialise_complet : int -> 'a -> 'b -> ('a, 'b) arbre = <fun>
In [6]:
initialise_complet 2 1 0;;
Out[6]:
- : (int, int) arbre =
NoeudInterne (NoeudInterne (Feuille 1, 0, Feuille 1), 0,
 NoeudInterne (Feuille 1, 0, Feuille 1))

2. Un arbre complet de hauteur $h$ a $2^h$ feuilles de profondeur $h$ chacune. Son cheminement est donc de $h2^h$.

Exercice 4

1.

In [7]:
let rec strahler arbre =
    match arbre with
    | Feuille _ -> 1
    | NoeudInterne(fils_gauche, _, fils_droit) ->
        let s_g = strahler fils_gauche in
        let s_d = strahler fils_droit in
        if s_g = s_d then
            s_g + 1
        else
            max s_g s_d
;;
Out[7]:
val strahler : ('a, 'b) arbre -> int = <fun>
In [8]:
let arbre2 = 
    let sous_arbre = initialise_complet 2 0 0 in
    NoeudInterne(
        NoeudInterne(
            sous_arbre,
            0,
            NoeudInterne(
                sous_arbre,
                0,
                Feuille 0
                )
            ),
        0, 
        Feuille 0
        )
;;
Out[8]:
val arbre2 : (int, int) arbre =
  NoeudInterne
   (NoeudInterne
     (NoeudInterne (NoeudInterne (Feuille 0, 0, Feuille 0), 0,
       NoeudInterne (Feuille 0, 0, Feuille 0)),
     0,
     NoeudInterne
      (NoeudInterne (NoeudInterne (Feuille 0, 0, Feuille 0), 0,
        NoeudInterne (Feuille 0, 0, Feuille 0)),
      0, Feuille 0)),
   0, Feuille 0)
In [9]:
strahler arbre2;;
Out[9]:
- : int = 4

2. Par récurrence sur $h\in\mathbb N$.

  • Initialisation : Si on considère un arbre de hauteur $0$, la racine est une feuille et le nombre de Strahler est $1=h+1$ avec un arbre qui est bien complet.
  • Hérédité : Si le résultat est vrai pour un $h\geqslant0$, et si on a un arbre de hauteur $h+1$, en notant $s$ son nombre de Strahler, considérons $s_g$ et $s_d$ les nombres de Strahler des fils gauche et droit de la racine. Comme ce sont des arbres de hauteur au plus $h$, par hypothèse de récurrence, $s_g\leqslant h+1$ et $s_d\leqslant h+1$. Alors $s\in\{s_g + 1, max(s_g, s_d)\}$ donc $s_g\leqslant h + 2$. De plus, il y a égalité si et seulement si $s = s_g + 1$ si et seulement si $s_g = s_d = h + 1$ si et seulement si les fils gauche et droit sont complets de hauteur $h$ (par hypothèse de récurrence) si et seulement si l'arbre est complet, ce qui établit la récurrence.

3. Un arbre de hauteur $h\neq0$ possède au moins un noeud interne, donc au moins un noeud avec deux feuilles qui aura $2$ comme nombre de Strahler. Comme le nombre de Strahler d'un noeud est toujours au moins aussi grand que ceux de ses fils, un arbre de hauteur $h\neq0$ a bien un nombre de Strahler au moins égal à $2$.

De plus, ce nombre sera égal à $2$ si et seulement si tous les noeuds internes ont un nombre de Strahler de $2$ (toujours vu la propriété de croissance). Cela signifie que chaque noeud interne doit avoir un fils dont le nombre de Strahler vaut $1$ et un fils dont le nombre de Strahler vaut $2$, ce qui correspond bien au type d'arbre décrit dans la question.