Insertion dans un ABR

On considère un arbres binaires de recherche qui :

  • soit est l’arbre vide identifié par None ;
  • soit possède une valeur clé, un sous-arbre gauche sag et un sous-arbre droit sad, tous les trois regroupés dans un triplet (sag, clé, sad).
graph
    n1((1)) --- n0((0))
    n1 --- n2((2))
    n2 --- n4((" "))
    n2 --- n3((3))

Ainsi, l’arbre binaire de recherche abr_1 ci-dessus est créé par le code python suivant : 

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

Écrire une fonction récursive insertion_abr qui prend en paramètres un arbre binaire de recherche abr et une clé valeur, et qui renvoie un arbre binaire de recherche dans lequel valeur a été insérée dans un emplacement libre (c'est-à-dire à la place d'un arbre vide).

Doublons

L'arbre ne doit pas contenir de doublons.

Dans le cas où cle est déjà présente dans abr, celle-ci n'est doit pas être insérer.

L'arbre revoyé par la fonction devra ainsi être identique à l'arbre de départ.

Exemple

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

###(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
Évaluations restantes : 10/10

.128013ua/;(lbw8p)gdo 7ekhmf:v,P1Ssin9y0_t54Nr32c6=050n0r0J0c0D0g0C0p0Q0g0c0C0C0S010J0D0k010406050C0b0u0u0c0N0G040B0o0g0b0-0o0E050d0@0_0{0}0=0k04161d051g0d1g1i1d0=0n0D0x0#0%0)0+0t0D0m0t0g1w0t0J0:050W0h0g0r1r0(0*011v1x1z1x0J1F1H1D0J0h0o0n0}1E0N1e0J0t0#100C0k0c0E0+0P011J1t010v0Y0r0E0c0u0r1D1+1-1=1L1^1H1{1}0:0a0p0z0N0o0k0o0C0D130E0p0U1)0N0N0r0Q2i16200E1e0d1%2v0J1#1!1$0n220+1z0E1`2f1D1o1q0$1K2F0D2H0E1X1p1D0k2o1e2t2v2Z0?1,2j2N1?2S0N0`0g0:0p0A2s2%0;2$212)1L2+2-2/0P2=1-2@2t2E012|0c2.040p0O302u0=332`0+36380p0L3c322%343i2/0K3m3e3o3g350o2,372/0R3t2^2(1s2{3y2}390q3D3f3G3h3I3A390j3M3v3O3x3z3j0F3U2_3W3q040A0H3#3F2O3X3J0A2;172?1f2X162L2y0n2C340Q1X1~1e3{1h3_2#3?3105400U2Y3V3.0s0:0U0v3m3E340i2/4k3N3.0E0v0:2Q0C0r0N2i0I0c0h0N4p4e1?0/040f4E3$4r0:0{4C0r4K3-4G0:0y3m0p4l3w0E0:0x370r0b4D482u4Y3W4H0l0w3t0p4?4X4q1?4g040D4j4+394-4M044O2o4W511?0o4n4|0C564_1L0s0Q0:0M144Q4 571L4H4;4 064@5t4^4F5f0:2o0J4)154 5v4L4T4I4R345g5i5k5I3w4H4V5D5n3h4#4%4)5N4.4U4W5E4S5f5h045j2H5X3.4/3t5s4@5S350:0C0c0m5,5G5Q2Z5#3p0:0$5l2#5e0+5P5d5w5T045^0n685F1L0o0:0S6e5$6a54632?5:4?5=4{4}6k6004626v3w6h04020m0J0e6z3%5U1H5W5m65015p4=5u6r6N4{5z5B6H5-0:4J6M695?4|0E4w4y0D144A4C5{5o6Z6:6a5^5`6#6f665Z5R6N4!044$6K4*646$4/5}2?5 4Z611H6?6O6}5~5=706c7e5.5r5t6s0:0r1z4~7h6 7c6o317a3W6B020g6F6X2*6J4(743@6N6P7n6R7z4f5y0V6W6~766=6`6l6%6^7l7g797i7w7#04787y7(6(6*4z4B7J497L7W756{7Z0c6d7X34677U7{70727I7*0l0l4W6q7P4`7q0Z7x4,7^045q2Z8b7o6T7R5A0N5C7u6$706n3D0d4b0r2v2W8A3`1p3|2y2A2w1W1Y2y4B1H2v3{0=0d0U0W0Y0C04.

###(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
Évaluations restantes : 10/10

.128013ua/;(lbw8p)gdo 7ekhmf:v,P1Ssin9y0_t54Nr32c6=050n0r0J0c0D0g0C0p0Q0g0c0C0C0S010J0D0k010406050C0b0u0u0c0N0G040B0o0g0b0-0o0E050d0@0_0{0}0=0k04161d051g0d1g1i1d0=0n0D0x0#0%0)0+0t0D0m0t0g1w0t0J0:050W0h0g0r1r0(0*011v1x1z1x0J1F1H1D0J0h0o0n0}1E0N1e0J0t0#100C0k0c0E0+0P011J1t010v0Y0r0E0c0u0r1D1+1-1=1L1^1H1{1}0:0a0p0z0N0o0k0o0C0D130E0p0U1)0N0N0r0Q2i16200E1e0d1%2v0J1#1!1$0n220+1z0E1`2f1D1o1q0$1K2F0D2H0E1X1p1D0k2o1e2t2v2Z0?1,2j2N1?2S0N0`0g0:0p0A2s2%0;2$212)1L2+2-2/0P2=1-2@2t2E012|0c2.040p0O302u0=332`0+36380p0L3c322%343i2/0K3m3e3o3g350o2,372/0R3t2^2(1s2{3y2}390q3D3f3G3h3I3A390j3M3v3O3x3z3j0F3U2_3W3q040A0H3#3F2O3X3J0A2;172?1f2X162L2y0n2C340Q1X1~1e3{1h3_2#3?3105400U2Y3V3.0s0:0U0v3m3E340i2/4k3N3.0E0v0:2Q0C0r0N2i0I0c0h0N4p4e1?0/040f4E3$4r0:0{4C0r4K3-4G0:0y3m0p4l3w0E0:0x370r0b4D482u4Y3W4H0l0w3t0p4?4X4q1?4g040D4j4+394-4M044O2o4W511?0o4n4|0C564_1L0s0Q0:0M144Q4 571L4H4;4 064@5t4^4F5f0:2o0J4)154 5v4L4T4I4R345g5i5k5I3w4H4V5D5n3h4#4%4)5N4.4U4W5E4S5f5h045j2H5X3.4/3t5s4@5S350:0C0c0m5,5G5Q2Z5#3p0:0$5l2#5e0+5P5d5w5T045^0n685F1L0o0:0S6e5$6a54632?5:4?5=4{4}6k6004626v3w6h04020m0J0e6z3%5U1H5W5m65015p4=5u6r6N4{5z5B6H5-0:4J6M695?4|0E4w4y0D144A4C5{5o6Z6:6a5^5`6#6f665Z5R6N4!044$6K4*646$4/5}2?5 4Z611H6?6O6}5~5=706c7e5.5r5t6s0:0r1z4~7h6 7c6o317a3W6B020g6F6X2*6J4(743@6N6P7n6R7z4f5y0V6W6~766=6`6l6%6^7l7g797i7w7#04787y7(6(6*4z4B7J497L7W756{7Z0c6d7X34677U7{70727I7*0l0l6Q6S6$4{7r4w7*5q2Z6q5u7p046V0N5C7u7V5H7 7b6b5_7*7,2u7P7G6x7d8t5Y7+7F2{5@7}873D0d4b0r2v2W8P3`1p3|2y2A2w1W1Y2y4B1H2v3{0=0d0U0W0Y0C04.