DS 2 (MPSI option 2021-2022) — Arbres de Fibonacci¶

Devoir surveillé · MPSI (option informatique) · 2021-2022 · partie II du DS 2 (2 h au total)

Autres parties : I, III, IV. Fibonacci et Zeckendorf

II. Arbres de Fibonacci¶

On considère le type Caml suivant pour représenter des arbres binaires stricts :

type arbre =
  | Feuille
  | Noeud of arbre * arbre

Question 5

Écrire une fonction nb_feuilles : arbre -> int qui renvoie le nombre de feuilles d'un arbre.

Corrigé

let rec nb_feuilles a =
  match a with
  | Feuille -> 1
  | Noeud (g, d) -> nb_feuilles g + nb_feuilles d

On définit les arbres de Fibonacci \((A_n)_{n\in\N}\) de la manière récursive suivante :

\(A_0\) et \(A_1\) sont des feuilles ;
si \(n \ge 2\), \(A_n\) est un nœud comportant \(A_{n-1}\) comme fils gauche et \(A_{n-2}\) comme fils droit.

Question 6

Dessiner les arbres \(A_2\), \(A_3\), \(A_4\) et \(A_5\).

Corrigé

Les nœuds sont représentés par des disques et les feuilles par des carrés.

Les arbres de Fibonacci A_2 à A_5 : nœuds en disques, feuilles en carrés. — Les arbres de Fibonacci \(A_2\) à \(A_5\) : nœuds en disques, feuilles en carrés.

Question 7

Écrire en Caml une fonction arbre_fibonacci : int -> arbre telle que l'appel arbre_fibonacci n renvoie l'arbre \(A_n\).

Corrigé

let rec arbre_fibonacci n =
  if n <= 1
  then Feuille
  else Noeud (arbre_fibonacci (n-1), arbre_fibonacci (n-2))

Question 8

Montrer que la complexité de cette fonction est en \(O(2^n)\).

On pourra remarquer qu'en dehors des appels récursifs tout se fait en temps constant et chercher à majorer le nombre d'appels récursifs.

Corrigé

On procède comme l'explication et on note \(C_n\) le nombre d'appels récursifs pour calculer le \(n\)-ième arbre. On a \(C_0 = C_1 = 0\) et \(C_n = 2 + C_{n-1} + C_{n-2}\).

Comme l'appel pour \(n\) nécessite de résoudre l'appel pour \(n-1\), on a nécessairement \(C_n\) croissante et \(C_n \le 2 (1 + C_{n-1})\) donc \(C_n + 2 \le 2 (C_{n-1} + 2)\) et par une récurrence rapide \(C_n + 2 \le 2^n\) donc \(C_n \le 2^n - 2 = O(2^n)\).

Question 9

Quelle est, pour \(n \in \N\), la hauteur de l'arbre \(A_n\) ? Justifier rigoureusement.

Corrigé

On a \(h(A_0) = h(A_1) = 0\) et pour \(n \ge 2\), \(h(A_n) = 1 + \max (h(A_{n-1}), h(A_{n-2}))\). On en déduit que \(h(A_n)\) est croissante et donc que \(h(A_n) = 1 + h(A_{n-1})\) d'où \(h(A_n) = n-1\) pour \(n \ge 1\).

Question 10

Exprimer le nombre de feuilles de \(A_n\) à l'aide des nombres de la suite de Fibonacci \((F_n)_{n\in\N}\).

Corrigé

De même si \(f(A)\) est le nombre de feuilles de \(A\), on a \(f(A_0) = f(A_1) = 1\) et \(f(A_n) = f(A_{n-1}) + f(A_{n-2})\). Donc \(f(A_n) = F_{n+1}\) : mêmes deux premières valeurs et même récurrence.

Question 11

Exprimer le nombre de nœuds de \(A_n\) à l'aide des nombres de la suite de Fibonacci \((F_n)_{n\in\N}\).

Corrigé

On note \(N(A)\) le nombre de nœuds de \(A\).

On a \(N(A_0) = N(A_1) = 0\) et \(N(A_n) = 1+ N(A_{n-1}) + N(A_{n-2})\).

En posant \(u_n = N(A_n) + 1\), on a pour \(n \ge 2\), \(u_n = u_{n-1} + u_{n-2}\) et \(u_0 = u_1 = 1\). Donc \(u_n = F_{n+1}\) et \(N(A_n) = F_{n+1} - 1\).

Question 12

Montrer que les arbres de Fibonacci sont équilibrés : en tout nœud de l'arbre les hauteurs des sous-arbres gauche et droit diffèrent au plus de 1.

Corrigé

C'est une conséquence directe du calcul de \(h(A_n) = n-1\) et de la définition.

Question 13

Écrire en Caml une fonction arbre_fibonacci_bis : int -> arbre de complexité \(O(n)\). Comment est-il possible d'avoir une fonction de complexité linéaire en \(n\) qui crée un arbre de taille exponentielle en \(n\) ?

Corrigé

let arbre_fibonacci_bis n =
  let f = ref Feuille in
  let f' = ref Feuille in
  for i = 1 to n do
    let t = !f' in
    f' := Noeud (!f', !f);
    f := t
  done;
  !f

En fait, quand on écrit Noeud (!f', !f) on ne copie pas les arbres, on se contente d'y faire référence. En mémoire, les valeurs ne sont pas dupliquées.