Insertion dans un ABR (3)

Dans cet exercice, on considère des arbres binaires de recherche qui sont :

• soit l’arbre vide identifié par None ;
• soit un nœud, contenant une clé et deux sous-arbres gauche et droit et représenté par un triplet (g, v, d) où g et d sont les sous-arbres gauche et droit et v la clé.

Ainsi, l’arbre binaire de recherche abr1 ci- contre est créé par le code python ci- dessous

🐍 Script Python

n0 = (None, 0, None)
n3 = (None, 3, None)
n2 = (None, 2, n3)
abr1 = (n0, 1, n2)

Écrire une fonction récursive insertion_abr(a, cle) qui prend en paramètres une clé cle et un arbre binaire de recherche a, et qui renvoie un arbre binaire de recherche dans lequel cle a été insérée. Dans le cas où cle est déjà présente dans a, la fonction renvoie l’arbre a inchangé.

Exemples

🐍 Console Python

>>> insertion_abr(abr1, 4)
((None,0,None),1,(None,2,(None,3,(None,4,None))))
>>> insertion_abr(abr1, -5)
(((None,-5,None),0,None),1,(None,2,(None,3,None)))
>>> insertion_abr(abr1, 2)
((None,0,None),1,(None,2,(None,3,None)))

Compléter le script ci-dessous

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)

Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)

Entrer ou sortir du mode "plein écran"
(Esc)

Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)

Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Exécuter le code
(Ctrl+S)Valider
Ctrl+Enter
(Clic droit pour l'historique)TéléchargerTéléverserRéinitialiser l'éditeurSauvegarder dans le navigateur

Évaluations restantes : 5/5

.128013f:6S0d=4yr/Nopg2mcb1w37ve[ l,8P5)ti]kn;ua(_sh050g0z0I0P0J0C0S0B0s0C0P0S0S0h010I0J0o010406050S0O0r0r0P0k0j040e0n0C0O0.0n0M050l0^0`0|0~0?0o04051e171h0l1e0?0g0J0y0$0(0*0,0T0J0p0T0C1v0T0I0;050X0t0C0z1q0)0+011u1w1y1w0I1E1G1C0I0k1f0I0T0$110S0o0P0M0,0q011I1s010b0Z0z0M0P0r0z1C1#1%1,1K1/1G1=1@0;0a0B0F0k0n0o0n0S0J140M0B0V1Z0k0k0z0s2c171`0M1f0l1X2p1U1W1V1D0g1|0,1y0M1;291C1n1p0%1J2z0J2B0M0n2F1C0o2i1f2n2p2T0@1$2d2H1-2M0k0{0C0;0u2m2X0=2W1{2Z1K2#2%0;0q2+1%2-2n2y012=0P2(040w2_2o0?2|2:0,2 310i342{2X2}3a0;0G3d363f382~0n2$300;0d3k2.2Y1r2;3p2?040x3u373x393z3r040E3d1i2R172F2s0g1W2x3n0s2N1^1f3P1g3N2V182,053V0V2S3m3F010L0;0V0b3L3E2I010v0;0B3@3-3_0M0b0;2K0S0z0k2c0R0P0t0k3~2/3.0:040Q4d3w400;0P4j2}4g0D3d3}3^2!0;0%0z4o3n4g0H0c4s060B4G4t3 1-3:040J3?3%2`4I4e4l044n4P2o4R4k1-0n3{4M0S4s3v2}0L0s0;0m154y4W3,4S1-4g4D4=4F4H4}4*3n4L2i0I0O0k164=4Y4p0;4i4=4 3.4,4.4:4z4f0;4r575d4T4x5i3_4q4)4u1K5f044/2B5q4^0;0H3k4~5u0,4L0z1y4O2T583n0M4w1G5t4J1K0n0;020p0I0N5S4@2;4m5A1K4g0A5)0,0r0J2)5-014g0K4`2T4|4}4G5n4K0;5254565M5~5*5a5=5P4U5=5+5=5/0;0f6b0;0K5l645G2~5(5c6m6c6p5T5.5:042*6s5$0,5@6k2,5N3.694446484a4c6y4Z664h686o2V6q0;5,6M2}6e042^6W4A6i6C4Q65395Q4;6S6t5?5C5D4{5F6/5I5K5#6N6+045p5m6m5V04020C5Z6{3g6R3(6T046V6.6z016Y6x7e6|6:045^5E5|5}6m510W62776$6P6#6F430M45470J15494b6h7x7j786a7y5r6U6d6v6g7N5B7m6(4X6*6n6~5R7T6O0H7W046E4T4V7K7w7d7a6/7h7I6j7v7z7M7.5j7c7Q2@7@6=5`6@7f7s53557_7,3u0l3*0z2p2Q8e3O1o3Q2s2v2q4a1G2p3P0?0l0V0X0Z0S04.

Aide

Réfléchir à une fonction récursive