É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 :

Évaluations restantes : 5/5

.128013lS]et-d5f18umaèg,_/R=in 6)yàqPhcNL\[(Mbsx.p;r4j'CJ90"ov+w73êOk:é *2I030b08090i0q050I0*0A050i0I0I0p0V090q0L0V020s030I0g0h0h0i0N0v02060W050g110W0r0*000i0h0L0M0*0o081b0N0x0g080I030n181a1c1e160L02031J1C1M0n1J160b0q0X0_0{0}0 0z0q0k0z051!0z0914030;0H05081V0|0~0V1Z1#1%1#091,1.1*090N1K090z0_1h0I0L0i0r0 0,0V1:1X0V0d0?080r1p081*26282d1=2g1.2j0h2l02040*0y0N0W0L0W0I0q1k1m0/240N0N080A2G1C2n0r1K0n222S1 21201+0b2p0 1%0r2i2D1*1S1U0`1;2$0q2'0r0W2+1*0L2L1K2Q2S2|17271m2-2e2=0N1b05140*0e2P30152 2o321=3436380,3b283d2Q2#0V3i0i37020*0#3m2R163p3g0 3s3u0*0O3y3o303q3E380c3I3A3K3C3r0W353t380t3P3e311W3h3U3j3v0!3Z3B3$3D3'3W3v0f3+3R3-3T3V3F0T3?3f3^3M020e0U3}3#2.3_3(0e3a1D3c3Q3~46400e3l4b3n1N2`1C2+2V0b212!3S0A2?2v0.1T1K2_082{3c3I034u0/4C4e2e0A0e14010*0-0r2F0q3t0q0I0i2G0*0b0i0*0{0*182F1/0/0^0N0)18050;091B4j3z3!3L140A4X3t280m2u0h3I0*4_3S0W140p53553^13020E4E3,460h0q144a2~5h2e5d073P0s4d452e0'140/0d5a5o3h0d140r0H0m1c0H2L0I0m0H2:0=5L5g3@465d0F5S4J3h5F5X5v1=5d0u0(3P0*5+545C0 5x020q5A4@3v5b4f5!5@5-5T2e5702000k090M595|5_330H142s5#3q5V6d3S0r4{4}0{0r501v6g5c145(5*5,6u685Z020I0W1a080m4|4?2|5}5Y0 60666G6w0 5j14435@0s6u6v5.0V5:0d3U5B5~6x0q6#6I0V0W0Z142:6(5$3D6a020N280k086p5U145W5@6N3r5{5n6$0 5'5)6S6U796H6:716y6A2u6D0|6/3q600Y6L3c7b4`025G5I0N5K1A5N5P0q5R6 6W6f7B747d6'7E6)5'7j56140+7L3 5F5H5J5L7x2j7z1A6{5p6}7Z6x0r7P46600a7(2e6P417,1=7*7:3D6-7$756r6t79704L4N4P0A0q0l0_6k4 514'086@4Z1/051l0k1z0g0N0*7'787a706i024|0;6l6n527I7c600K7_7d0i0L0L2i0b8A7D736)8p6z6B7h6F4D7C7{8m5+705:2L098i8l6M6W8p8r4~6m518H145f8w7q8!8Q7F5q3Z0n4G4B4l8`0n4o1C094q8 2Y2T0i1-8|4o1I4I7c2L0h0m0d0i0'6C0z0#141u1w1y1A0*772~1P3d1h3d1%020C4#4A5j0j2L0*270N111/0w241q050)098a0*1A090*9K4%2g1m4F4v3q1@1$1'1)9a3q8W0:8Z7?7d8'8t8*8.3S5d8-8J7c8p8:4k8R025r6 8^4v02841l4'0W0g0z0=9P4$4#0X3t088i4Z0Q2:1S0A1/701c2F0z1b9P0J140D0F0r0D0u532Iao1{8d4V9P0K0*0%0g0*5O2i548_9#1'1_1(2m7F9|9.6062647n3n7p6h6=6c9?6q026~9`7q9:876oa-6|02aCa28_3v0i0g9o05850^a78E1j0*4-2C0r0b9E1S2L2N1v2i09842E2=0r840?0*9fb81.85050A0g1.8j0:4$0Q0i0Pa99P8j9V4#1%0I9P84ao0*1y0q89brac9Uae4$1!2'9F4-0A0)0/0raJ1C9x169x9Z4H8M7g6E1Ca~9RbM0*0gb!b;4*9p6Ebp4R114U0I0)9Ja)3^ar22au08aw02ay0UaB53bJbY0kb!0taK0-b30v0*4#aq0NascdcfayaAa|6G6EbW9O0g1S9Q2Icwcy4Xceax0F0F0U840r0a0e0ucj5@84cMcccOcAcR0ecU0a0,cYcD3cc#6Wcbatc'cQ0D0A0b0W4=cZ2|c;7Fc?czcQazc,84cXc c:c946d3c^cgcRcVc*0*0Uc.3IaK9zaOa90`apaS3S9$aV9(8V146Z0N9.8p7H8#7F6+6-9}2Rdc69146@0r6_8+a/8AaZa_7!a{9r4Da34Hbr8a4#aP9Yc=cxc%avcQcC5309a90N0I8zby9w0q02b0b#1v0q9Qd=ajc$c@d.dg0q0pcic/3n8405bD1j9E0)9N2ub)4ZaN4u0g0Lbu0/0X8b0$1 apd+cNe7cBcWda4k0nb,039xd~e38j4(ageme5d4e80p0eeE2Reeegex0*ej0)el9T0beoa9erb eu4#ew9EeQdfeC0,eV2SeH9x2I1b4R9D1/0k0)0r0)6@1.eXb0eZe#e%en24eqes08e-0*e/eyd2d,e6cPdgdi0a0qe^b+d|160nd`fwe`d|dpdB0hby1/2CajbucFaQe;eB0FfsecdL9S4Z1l0AaR9!dvaU9'aX8K7R7t7v5M5O7W7Aa;9@7#dW6%dSfQ5^6W607O678$f%7T7wf*5Q7Yf:7`dTg37ddKf@dH147+f{7F7.5m7o707=gdf$5;f=4Ed#8|fA020S0gbM5=0q1l0^fJ7fbjg1cmb!0TfW4H4O0-82bO868)1v898b2I8edQ8h8j8la~03fyeId|06bSa7fSbj4-4Z28gz4#bM0N0g2N8i1/4ubc4S1l2'05f60_0QfS9ogH4B1m004:1s2s0Fa?gO0ha|gYeGfvg#020G0=0^9Val0}1z8cbX0Hdrbub/h57S7u7Ug07X0Iaz0*0a39hfa4cue!090)cu8D089N84bBc|0rfVhx8qgN8ub@hK4#0b0)0P9K9OhO5jhn0*bFaje|280qe b90)bxd@1T08hT9TbqfShVfVgS8fgVh47rh$4H8zhhd{020%1mb79T0=0r2E9Ler9O9Q4%1_b!42h4aT1^f!9)6h6j8sa@8vf-3^8ydU148C8EbcdSa:8;glb~8Ogna}a4ideHfx053diefw9v161-0W0A0'1yc}4B99cr9R0JaI4*0Q034#0z2L0d1Y1{0L0I0(0n0n0d0N0K0Z0q0'12081S0i0K3U0k0nj9jb0n0B6A7v0m0/0m0RgNiKeh9p0h9O0z4v0^aE3tbx051C0ia59F1i0^080d2g4|aod^1Ni#i)i+i-9Pi#0/0;0?0I02.