Aller au contenu

Énumération des arbres binaires de taille n⚓︎

  • Il y a 1 arbre binaire de taille 0.
  • Il y a 1 arbre binaire de taille 1.
  • Il y a 2 arbres binaires de taille 2.
  • Il y a 5 arbres binaires de taille 3.
  • Il y a 14 arbres binaires de taille 4.
Arbres binaires de taille 4

Les 14 arbres binaires de taille 4, peuvent être répartis en fonction de la taille des sous arbres.

Il y a un nœud racine et 3 autres nœuds à répartir à gauche (\(t_g\)) et à droite (\(t_d\)).

\[(1 + t_g + t_d = 4)\]

\((t_g=0, t_d=3)\)

\((t_g=1, t_d=2)\)

\((t_g=2, t_d=1)\)

\((t_g=3, t_d=0)\)

Objectif : écrire une fonction telle que nb_arbres_binaires(n) renvoie le nombre d'arbres binaires de taille n. Il existe plusieurs méthodes de calcul. Voici une méthode pédagogique pour calculer ce nombre en fonction de n. Il s'agit des nombres de Catalan.

  • Si la taille \(n\) vaut zéro,
    • renvoyer \(1\). Il y a un seul arbre à zéro nœud, un arbre vide.
  • Sinon,
    • l'arbre possède une racine et deux sous-arbres. Les tailles possibles pour les sous-arbres sont :
      • \(0\) à gauche et \(n-1\) à droite
      • \(1\) à gauche et \(n-2\) à droite
      • \(2\) à gauche et \(n-3\) à droite
      • ...
      • \(n-3\) à gauche et \(2\) à droite
      • \(n-2\) à gauche et \(1\) à droite
      • \(n-1\) à gauche et \(0\) à droite
    • renvoyer la somme du nombre d'arbres dans chaque cas.

Indices

Pour un arbre binaire de taille \(5\), il y a un nœud racine et \(4\) autres nœuds. Ces derniers peuvent se répartir en \((0, 4)\), \((1, 3)\), \((2, 2)\), \((3, 1)\), \((4, 0)\) à gauche et à droite.

  • Pour \((0, 4)\), il y a
    • \(1\) sous-arbre à gauche possible, à 0 nœud,
    • \(14\) sous-arbres à droite possibles à 4 nœuds,
    • ainsi \(1×14\) possibilités de choisir un arbre binaire de taille \(0\) à gauche et de taille \(4\) à droite.
  • Pour \((1, 3)\), il y a
    • \(1\) sous-arbre à gauche possible à 1 nœud,
    • \(5\) sous-arbres à droite possibles à 3 nœuds,
    • donc \(1×5\) possibilités pour ce cas.
  • Pour \((2, 2)\), il y a \(2×2\) possibilités.
  • Pour \((3, 1)\), il y a \(5×1\) possibilités.
  • Pour \((4, 0)\), il y a \(14×1\) possibilités.

Il y a donc \(1×14 + 1×5 + 2×2 + 5×1 + 14×1 = 42\) arbres binaires de taille \(5\).

On stocke les résultats qui sont utilisés souvent dans une liste catalan_mem, cette liste commence avec [1, 1, 2, 5, 14, 42]. Il est très utile de mettre à jour cette liste dès que possible.

Exemples
🐍 Console Python
>>> nb_arbres_binaires(3)
5
>>> nb_arbres_binaires(4)
14
>>> nb_arbres_binaires(5)
42

Code à compléter :

###
# testsbksl-nlbksl-nlassert nbpy-undarbrespy-undbinaires(3) == 5bksl-nlassert nbpy-undarbrespy-undbinaires(4) == 14bksl-nlassert nbpy-undarbrespy-undbinaires(5) == 42bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlbksl-nlassert nbpy-undarbrespy-undbinaires(8) == 1430bksl-nlassert nbpy-undarbrespy-undbinaires(6) == 132bksl-nlbksl-nlbksl-nlCATALAN = [bksl-nl 1,bksl-nl 1,bksl-nl 2,bksl-nl 5,bksl-nl 14,bksl-nl 42,bksl-nl 132,bksl-nl 429,bksl-nl 1430,bksl-nl 4862,bksl-nl 16796,bksl-nl 58786,bksl-nl 208012,bksl-nl 742900,bksl-nl 2674440,bksl-nl 9694845,bksl-nl 35357670,bksl-nl 129644790,bksl-nl 477638700,bksl-nl 1767263190,bksl-nl 6564120420,bksl-nl 24466267020,bksl-nl 91482563640,bksl-nl 343059613650,bksl-nl 1289904147324,bksl-nl 4861946401452,bksl-nl 18367353072152,bksl-nl 69533550916004,bksl-nl 263747951750360,bksl-nl 1002242216651368,bksl-nl 3814986502092304,bksl-nl]bksl-nlbksl-nlfor (n, catalanpy-undn) in enumerate(CATALAN):bksl-nl assert nbpy-undarbrespy-undbinaires(n) == catalanpy-undn, f"Erreur avec n = {n}"bksl-nlbksl-nl 5/5

# Initialisation da la suite des résultatsbksl-nlcatalanpy-undmem = [1]bksl-nlbksl-nlbksl-nldef nbpy-undarbrespy-undbinaires(n):bksl-nl if n >= len(catalanpy-undmem):bksl-nl sommepy-undcas = ...bksl-nl for i in range(...):bksl-nl sommepy-undcas += nbpy-undarbrespy-undbinaires(...) py-str ...bksl-nl # Ici, catalanpy-undmem sera de longueur nbksl-nl catalanpy-undmem.append(...)bksl-nl return catalanpy-undmem[...]bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undarbrespy-undbinaires(3) == 5bksl-nlassert nbpy-undarbrespy-undbinaires(4) == 14bksl-nlassert nbpy-undarbrespy-undbinaires(5) == 42bksl-nlbksl-nl# Initialisation da la suite des résultatsbksl-nlcatalanpy-undmem = [1]bksl-nlbksl-nlbksl-nldef nbpy-undarbrespy-undbinaires(n):bksl-nl if n >= len(catalanpy-undmem):bksl-nl sommepy-undcas = 0bksl-nl for i in range(n):bksl-nl sommepy-undcas += nbpy-undarbrespy-undbinaires(i) py-str nbpy-undarbrespy-undbinaires(n - 1 - i)bksl-nl # Ici, catalanpy-undmem sera de longueur nbksl-nl catalanpy-undmem.append(sommepy-undcas)bksl-nl return catalanpy-undmem[n]bksl-nlbksl-nl

A

  1. La première partie à compléter est à la fin return catalan_mem[n], on souhaite la valeur d'indice \(n\) de cette liste. Ou bien n >= len(catalan_mem) auquel cas on peut répondre directement, sinon, il faut le calculer et l'ajouter à la liste, ce qui se fait à la ligne précédente.
  2. somme_cas est une somme des cas, initialisée à \(0\) à la ligne 6. Il y a \(n\) cas à étudier de \((0, n-1)\), \((1, n-2)\), \(\cdots\), \((n-2, 1)\), \((n-1, 0)\). La boucle for i in range(n): fera bien \(n\) tours.
    • au premier tour \(i=0\), l'autre élément du couple devra être \(n-1\)
    • au tour suivant \(i=1\), l'autre élément du couple devra être \(n-2\)
    • de manière générale, l'autre élément du couple devra être \(n-1-i\)
  3. La formule pour le cas en \(i\) est donc nb_arbres_binaires(i) * nb_arbres_binaires(n - 1 - i)
  4. Justifions le commentaire ligne 9 # Ici, catalan_mem sera de longueur n
    • Si on est entré dans la structure conditionnelle, c'est que n < len(catalan_mem)
    • Mais à l'issue de la boucle nb_arbres_binaires(n - 1) a été appelé, et donc catalan_mem a déjà été mis à jour de manière récursive, et il est donc de longueur n.
    • On peut ainsi compléter la ligne 10 catalan_mem.append(somme_cas).

Il existe d'autres méthodes de calcul, plus efficaces.

Z