Combien d'arbres binaires de recherche ? — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 9)

Combien d'arbres binaires de recherche ?

Arbres binaires de recherche de coût minimum · niveau 3 (difficile)

Énoncé

On note $b (n)$ le nombre d'abr différents construits sur $n$ valeurs distinctes.

Donner $b (0)$ , $b (1)$ , $b (2)$ , $b (3)$ en dessinant les arbres.
En raisonnant sur la valeur à la racine, montrer que $b (n) = \sum_{k = 0}^{n - 1} b (k) b (n - 1 - k)$ pour $n \geq 1$ .
Écrire le programme qui calcule $b (n)$ en $Θ (n^{2})$ et donner $b (9)$ , $b (20)$ , $b (30)$ . Que penser d'un algorithme qui énumérerait tous les abr pour garder le moins coûteux ?

Corrigé

$b (0) = 1$ (l'arbre vide), $b (1) = 1$ , $b (2) = 2$ (la seconde valeur à gauche ou à droite de la première), $b (3) = 5$ (racine $0$ : deux arbres ; racine $1$ : un ; racine $2$ : deux).
Si la racine est la $(k + 1)$ -ème plus petite valeur, le sous-arbre gauche est un abr quelconque sur les $k$ plus petites ( $b (k)$ choix) et le sous-arbre droit un abr quelconque sur les $n - 1 - k$ autres ( $b (n - 1 - k)$ choix), indépendamment. On somme sur la racine.


static long[] nombreAbr(int N) {
    long[] B = new long[N + 1];
    B[0] = 1;                                         // l'arbre vide
    for (int n = 1; n < N + 1; n++)
        for (int k = 0; k < n; k++) B[n] += B[k] * B[n - 1 - k]; // racine = (k+1)-ème valeur
    return B;
}

Exécution :


b(4) = 14, b(9) = 4862, b(20) = 6564120420, b(30) = 3814986502092304

Ce sont les nombres de Catalan, qui croissent comme $4^{n}$ (à un facteur polynomial près). Énumérer les abr est envisageable pour $n = 9$ , impossible dès $n = 30$ ; la programmation dynamique trouve l'optimum en $Θ (n^{3})$ , voire $Θ (n^{2})$ avec Knuth.