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

.128013; l6yg/vS)iucbtf489w0oe5Psa_d=(7Nh2,3n:1kmpr050D0x0p0B0l0d0A0c0n0d0B0A0A0E010p0l0R010406050A0m0Q0Q0B0S0f040j0w0d0m0-0w0M050h0@0_0{0}0=0R04161d051g0h1g1i1d0=0D0l0i0#0%0)0+0I0l0g0I0d1w0I0p0:050W0o0d0x1r0(0*011v1x1z1x0p1F1H1D0p0o0w0D0}1E0S1e0p0I0#100A0R0B0M0+0J011J1t010q0Y0x0M0B0Q0x1D1+1-1=1L1^1H1{1}0:0a0c0z0S0w0R0w0A0l130M0c0U1)0S0S0x0n2i16200M1e0h1%2v0p1#1!1$0D220+1z0M1`2f1D1o1q0$1K2F0l2H0M1X1p1D0R2o1e2t2v2Z0?1,2j2N1?2S0S0`0d0:0c0O2s2%0;2$212)1L2+2-2/0J2=1-2@2t2E012|0B2.040c0L302u0=332`0+36380c0r3c322%343i2/0y3m3e3o3g350w2,372/0e3t2^2(1s2{3y2}390G3D3f3G3h3I3A390s3M3v3O3x3z3j0t3U2_3W3q040O0v3#3F2O3X3J0O2;172?1f2X162L2y0D2C340n1X1~1e3{1h3_2#3?3105400U2Y3V3.0P0:0U0q3m3E340u2/4k3N3.0M0q0:2Q0A0x0S2i0C0B0o0S4p4e1?0/040F4E3$4r0:0{4C0x4K3-4G0:0K3m0c4l3w0M0:0i370x0m4D482u4Y3W4H0k0N3t0c4?4X4q1?4g040l4j4+394-4M044O2o4W511?0w4n4|0A564_1L0P0n0:0H144Q4 571L4H4;4 064@5t4^4F5f0:2o0p4)154 5v4L4T4I4R345g5i5k5I3w4H4V5D5n3h4#4%4)5N4.4U4W5E4S5f5h045j2H5X3.4/3t5s4@5S350:0A0B0g5,5G5Q2Z5#3p0:0$5l2#5e0+5P5d5w5T045^0D685F1L0w0:0E6e5$6a54632?5:4?5=4{4}6k6004626v3w6h04020g0p0b6z3%5U1H5W5m65015p4=5u6r6N4{5z5B6H5-0:4J6M695?4|0M4w4y0l144A4C5{5o6Z6:6a5^5`6#6f665Z5R6N4!044$6K4*646$4/5}2?5 4Z611H6?6O6}5~5=706c7e5.5r5t6s0:0x1z4~7h6 7c6o317a3W6B020d6F6X2*6J4(743@6N6P7n6R7z4f5y0V6W6~766=6`6l6%6^7l7g797i7w7#04787y7(6(6*4z4B7J497L7W756{7Z0B6d7X34677U7{70727I7*0k0k4W6q7P4`7q0Z7x4,7^045q2Z8b7o6T7R5A0S5C7u6$706n3D0h4b0x2v2W8A3`1p3|2y2A2w1W1Y2y4B1H2v3{0=0h0U0W0Y0A04.

###(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

.128013; l6yg/vS)iucbtf489w0oe5Psa_d=(7Nh2,3n:1kmpr050D0x0p0B0l0d0A0c0n0d0B0A0A0E010p0l0R010406050A0m0Q0Q0B0S0f040j0w0d0m0-0w0M050h0@0_0{0}0=0R04161d051g0h1g1i1d0=0D0l0i0#0%0)0+0I0l0g0I0d1w0I0p0:050W0o0d0x1r0(0*011v1x1z1x0p1F1H1D0p0o0w0D0}1E0S1e0p0I0#100A0R0B0M0+0J011J1t010q0Y0x0M0B0Q0x1D1+1-1=1L1^1H1{1}0:0a0c0z0S0w0R0w0A0l130M0c0U1)0S0S0x0n2i16200M1e0h1%2v0p1#1!1$0D220+1z0M1`2f1D1o1q0$1K2F0l2H0M1X1p1D0R2o1e2t2v2Z0?1,2j2N1?2S0S0`0d0:0c0O2s2%0;2$212)1L2+2-2/0J2=1-2@2t2E012|0B2.040c0L302u0=332`0+36380c0r3c322%343i2/0y3m3e3o3g350w2,372/0e3t2^2(1s2{3y2}390G3D3f3G3h3I3A390s3M3v3O3x3z3j0t3U2_3W3q040O0v3#3F2O3X3J0O2;172?1f2X162L2y0D2C340n1X1~1e3{1h3_2#3?3105400U2Y3V3.0P0:0U0q3m3E340u2/4k3N3.0M0q0:2Q0A0x0S2i0C0B0o0S4p4e1?0/040F4E3$4r0:0{4C0x4K3-4G0:0K3m0c4l3w0M0:0i370x0m4D482u4Y3W4H0k0N3t0c4?4X4q1?4g040l4j4+394-4M044O2o4W511?0w4n4|0A564_1L0P0n0:0H144Q4 571L4H4;4 064@5t4^4F5f0:2o0p4)154 5v4L4T4I4R345g5i5k5I3w4H4V5D5n3h4#4%4)5N4.4U4W5E4S5f5h045j2H5X3.4/3t5s4@5S350:0A0B0g5,5G5Q2Z5#3p0:0$5l2#5e0+5P5d5w5T045^0D685F1L0w0:0E6e5$6a54632?5:4?5=4{4}6k6004626v3w6h04020g0p0b6z3%5U1H5W5m65015p4=5u6r6N4{5z5B6H5-0:4J6M695?4|0M4w4y0l144A4C5{5o6Z6:6a5^5`6#6f665Z5R6N4!044$6K4*646$4/5}2?5 4Z611H6?6O6}5~5=706c7e5.5r5t6s0:0x1z4~7h6 7c6o317a3W6B020d6F6X2*6J4(743@6N6P7n6R7z4f5y0V6W6~766=6`6l6%6^7l7g797i7w7#04787y7(6(6*4z4B7J497L7W756{7Z0B6d7X34677U7{70727I7*0k0k6Q6S6$4{7r4w7*5q2Z6q5u7p046V0S5C7u7V5H7 7b6b5_7*7,2u7P7G6x7d8t5Y7+7F2{5@7}873D0h4b0x2v2W8P3`1p3|2y2A2w1W1Y2y4B1H2v3{0=0h0U0W0Y0A04.