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

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

Python Console Session

>>> 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)TéléchargerTéléverserRéinitialiser l'éditeurSauvegarder dans le navigateur

Évaluations restantes : 5/5

.128013kg[: r);S/N(lo4y,6b=ac15ud3t28_Pw7evp-fh0mn]is050A0J0C0v0T0n0U0f0w0n0v0U0U0u010C0T0L010406050U0z0Q0Q0v0g0q040j0o0n0z0/0o0R050k0_0{0}0 0@0L04051f181i0k1f0@0A0T0K0%0)0+0-0)0R0c0z0v0c0J0M0L0q0C0O160f0O0T0c0O0n1K0O0C0=050Y0t0n0J1r0*0,011J1L1N1L0C1T1V1R0C0g1g1F0%120U0L0v0R0-0D011X1t010N0!0J0R0v0Q0J1R1?1^1}1Z201V23250=0a0f0G0g0o0L0o0U0T150R0f0W1;0g0g0J0w2q18280R1g0k1F2D1-1/1.1S0A2a1u0T0R222n1R1o1q0(1Y2N2P0R0o2T1R0L2w1g2B2D2*0^1@2r2V1~2Z0g0|0n1R0v1I2w0N0-030F0F0w2!0J1N2Y0o0M0D0M0x0=0x180v2+2.0?2-292:1Z2=2@2_2{0J2}012 3133352Q38380=0D3e3g1^3i2B2M013n0v2^1g2`0O2|2~30320W3x2Z3z0B0=0B3D2A3h0@3H3l0-3K3M053O3Q3t3S3w2O3y390p0=0p3#193%3j2/1s3m0o2?3L3p3P3r3R3v3U3@3W390y0=0y3}2*3(2.3I3,473:3u3T344d37390s0=0s4j3 3)423+443o3N3q3s4r3?363z0I0=0I4A3F4l3k4D3J4F464H484J3=4c4M390E0=0E4R2C1j2(182T2G0A1/2L3*014s2S1p1g2%0J2)3h3$3F054s52290T0A0-302B3z3b4H5a5c4b4t4(3a1|2e0J5j4s3V4v5n2D3f403I0b0=0W0N542C0f5y4`0R0N0=2O0U0J0g2q0F0v0t0g5E58412W010;040m5V5H4V0R0=0v5%4C5Y5!0r5V5G5.2;0=0(0J5-4m4`5!0h0e5=0@3~553H5i015d2.3z1{5h5b685k5t6b5o245q6f5s4u6i5w040f6s5?5}4V5A040T5D645F5(5Y5*045,6B6r6D1~0o0H5L0U5=6K1Z0b0w0=0l165{6I6R0-5!616I632,666e691^3X3p674$5l3^0M3Y0f5p5r4L6@3Y6q6t716u4U5Y6x2w0C0z0g176I735X1~5!5$6Z5@6S6U046W2P5|747f0=5;7c6!3J5_1V7p7e1Z5:6Q7j0-6T6V6X7z3I5 5V6)536+5j5e3_6:6,6g6o7S6`6k6|4%6@3`706t7v6x4t6A2*7d4n7x6Y7.7v0o0=020c0C0i7D6v6E5+7J5~0=0d824V0Q0T3c865/0=0S6%4k7J6;0F7R0M4g6d7!6?4e8l6j258o6h4f1R0k3f727)7E01760X797b7?8C7g8b5^6G8L7B848O0-880=0P8R5Z8d7t8I7 8M6H6*8#8P04857i8)8S89043d8-7q8*0S8Z3h7/5I5L0R5N5P0T165R5T8W8K8?7A3+81987K8Q9c4`8T043C9f4V5!8_7~8@9a045`960=0h0h7M8h7U8k4x8n6m6}8q4x7Y8t9D7#9F8x8z8B8.8D0=7,9o997w9r7y7u8C7^04020n7|9T7:8N9k8c8+8W9h8=8(9p8X048e9x9c8i8k4O9C6=8v0M4O9H6la07Wa29M6r8A8|6w0=778G9)835#8W6F5M5O5Q5S5U9,7rajar3m9b9=9U5!8,ax3I9h8Vau6#8Yah5)7;9t040h8`3Fac809+aBaiaA7O9P9:aL9n9Y9P6F8%aW9?az9/8:9jaT9l8d9w6(9y7Q6a4)7T8ua74*a4a|5m4*7(6s7*ae8F7aaIaRa(4S5%0k574/514;4~180C4@bk2J2E5S1V2D4=630W0Y0!0U04.

Aide

Réfléchir à une fonction récursive