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

Évaluations restantes : 5/5

.128013fd6nmi74=]3y_ pu08ts5[/v1b(P)l;gow-ah:rS2cekN,050c0R0t0K0g0E0u0o0Q0E0K0u0u0j010t0g0p010406050u0q0f0f0K0N0m040O0H0E0q0/0H0e050x0_0{0}0 0@0p04051f181i0x1f0@0c0g0y0%0)0+0-0)0e0G0q0K0G0R0J0p0m0t0L160o0L0g0G0L0E1K0L0t0=050Y0A0E0R1r0*0,011J1L1N1L0t1T1V1R0t0N1g1F0%120u0p0K0e0-0P011X1t010b0!0R0e0K0f0R1R1?1^1}1Z201V23250=0a0o0C0N0H0p0H0u0g150e0o0W1;0N0N0R0Q2q18280e1g0x1F2D1-1/1.1S0c2a1u0g0e222n1R1o1q0(1Y2N2P0e0H2T1R0p2w1g2B2D2*0^1@2r2V1~2Z0N0|0E1R0K1I2w0b0-030n0n0Q2!0R1N2Y0H0J0P0J0z0=0z180K2+2.0?2-292:1Z2=2@2_2{0R2}012 3133352Q38380=0P3e3g1^3i2B2M013n0K2^1g2`0L2|2~30320W3x2Z3z0l0=0l3D2A3h0@3H3l0-3K3M053O3Q3t3S3w2O3y390i0=0i3#193%3j2/1s3m0H2?3L3p3P3r3R3v3U3@3W390v0=0v3}2*3(2.3I3,473:3u3T344d37390d0=0d4j3 3)423+443o3N3q3s4r3?363z0h0=0h4A3F4l3k4D3J4F464H484J3=4c4M390s0=0s4R2C1j2(182T2G0c1/2L3*014s2S1p1g2%0R2)3h3$3F054s52290g0c0-302B3z3b4H5a5c4b4t4(3a1|2e0R5j4s3V4v5n2D3f403I0S0=0W0b544.4C2W010I0=0o5E58415H0e0b0=2O0u0R0N2q0n0K0A0N5M5y4`0;040B5$5G2;0=0K5,4m5(0=0U5M5L5-3m0=0(0R5;4U5H5)0D0M5_0@3~553H5i015d2.3z1{5h5b6c5k5t6f5o245q6j5s4u6m5w040o6w5`5=4V5A040g5D682C6y615.045:6F6v5%4V0H5J6C0u5_6O5H0S0Q0=0T165 6M6V1~5)656M672,6a6i6d1^3X3p6b4$5l3^0J3Y0o5p5r4L6{3Y6u6x756H5O1~6B2w0t0q0N176M773I5)5+6%5{0-6X6Z6#60781Z5)5^7g6(5|045~7r7i5@6U7m017o046!2P7B5?040D5M6-536/5j5e3_6@6:6k6s7V6~6o704%6{3`746x7x7n0=4t6E2*7h4`0e5}1V7E6z5H0H0=020G0t0F7{6I7y6L6.7|6)0=0w7L4V0f0g3c8d620=0k6+4k7B6^0n7U0J4g6h7%6`4e8s6n258v6l4f1R0x3f767,7F7a0X7d7f7=7-017j8i6J877R897t8b8S1Z8f0=0r8Z0-5)0k7v8O7F7^6K8(8Q8Y7l8W0-8#043d8@858)8k8,3h7?4V8/5T5V5X5Z5#8}7s8 5*8;8/8U698^8=048c9b3I8`3C9n7M8+849c3J7_6$888~9k0D7O6,8o7X8r4x8u6q718x4x7#8A9K7(9M8E8G8I9j6B7:9u4n9x9Z4`7~04020E829$945/8;5)9m9z9v8`8|9?7C048l7P9F7T6e394O9J6_8C0J4O9O6pa57Za79T6v8H936W0=7b8M9-8j9e9r9.6C0e5U5W0g165Y5!9:0=7k9`7@9/apan9=8V9A8`8%aF8a9|913Fah6J7AaM8X7NaP6G8P9gaz9l8;9^a#9t7w8.aEaC4V9;a%8g049qa.an0k9D8n9n8p8r4*a47Y5m4*a98Bacb03D758P8K7c7eam8T9~6%0x574/514;4~180t4@bp2J2E5Z1V2D4=670W0Y0!0u04.

Aide

Réfléchir à une fonction récursive