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:pbv(40i2edm3;sN7= 1o5w_lSnatf)9h6,crgyPku8/050l0k0D0C0i0z0p0t0K0z0C0p0p0s010D0i0c010406050p0Q0m0m0C0L0N040A0v0z0Q0-0v0B050S0@0_0{0}0=0c04161d051g0S1g1i1d0=0l0i0e0#0%0)0+0H0i0M0H0z1w0H0D0:050W0d0z0k1r0(0*011v1x1z1x0D1F1H1D0D0d0v0l0}1E0L1e0D0H0#100p0c0C0B0+0j011J1t010E0Y0k0B0C0m0k1D1+1-1=1L1^1H1{1}0:0a0t0O0L0v0c0v0p0i130B0t0U1)0L0L0k0K2i16200B1e0S1%2v0D1#1!1$0l220+1z0B1`2f1D1o1q0$1K2F0i2H0B1X1p1D0c2o1e2t2v2Z0?1,2j2N1?2S0L0`0z0:0t0u2s2%0;2$212)1L2+2-2/0j2=1-2@2t2E012|0C2.040t0n302u0=332`0+36380t0g3c322%343i2/0w3m3e3o3g350v2,372/0I3t2^2(1s2{3y2}390r3D3f3G3h3I3A390R3M3v3O3x3z3j0G3U2_3W3q040u0h3#3F2O3X3J0u2;172?1f2X162L2y0l2C340K1X1~1e3{1h3_2#3?3105400U2Y3V3.0P0:0U0E3m3E340x2/4k3N3.0B0E0:2Q0p0k0L2i0y0C0d0L4p4e1?0/040f4E3$4r0:0{4C0k4K3-4G0:0J3m0t4l3w0B0:0e370k0Q4D482u4Y3W4H0F0b3t0t4?4X4q1?4g040i4j4+394-4M044O2o4W511?0v4n4|0p564_1L0P0K0:0q144Q4 571L4H4;4 064@5t4^4F5f0:2o0D4)154 5v4L4T4I4R345g5i5k5I3w4H4V5D5n3h4#4%4)5N4.4U4W5E4S5f5h045j2H5X3.4/3t5s4@5S350:0p0C0M5,5G5Q2Z5#3p0:0$5l2#5e0+5P5d5w5T045^0l685F1L0v0:0s6e5$6a54632?5:4?5=4{4}6k6004626v3w6h04020M0D0o6z3%5U1H5W5m65015p4=5u6r6N4{5z5B6H5-0:4J6M695?4|0B4w4y0i144A4C5{5o6Z6:6a5^5`6#6f665Z5R6N4!044$6K4*646$4/5}2?5 4Z611H6?6O6}5~5=706c7e5.5r5t6s0:0k1z4~7h6 7c6o317a3W6B020z6F6X2*6J4(743@6N6P7n6R7z4f5y0V6W6~766=6`6l6%6^7l7g797i7w7#04787y7(6(6*4z4B7J497L7W756{7Z0C6d7X34677U7{70727I7*0F0F4W6q7P4`7q0Z7x4,7^045q2Z8b7o6T7R5A0L5C7u6$706n3D0S4b0k2v2W8A3`1p3|2y2A2w1W1Y2y4B1H2v3{0=0S0U0W0Y0p04.

###(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:pbv(40i2edm3;sN7= 1o5w_lSnatf)9h6,crgyPku8/050l0k0D0C0i0z0p0t0K0z0C0p0p0s010D0i0c010406050p0Q0m0m0C0L0N040A0v0z0Q0-0v0B050S0@0_0{0}0=0c04161d051g0S1g1i1d0=0l0i0e0#0%0)0+0H0i0M0H0z1w0H0D0:050W0d0z0k1r0(0*011v1x1z1x0D1F1H1D0D0d0v0l0}1E0L1e0D0H0#100p0c0C0B0+0j011J1t010E0Y0k0B0C0m0k1D1+1-1=1L1^1H1{1}0:0a0t0O0L0v0c0v0p0i130B0t0U1)0L0L0k0K2i16200B1e0S1%2v0D1#1!1$0l220+1z0B1`2f1D1o1q0$1K2F0i2H0B1X1p1D0c2o1e2t2v2Z0?1,2j2N1?2S0L0`0z0:0t0u2s2%0;2$212)1L2+2-2/0j2=1-2@2t2E012|0C2.040t0n302u0=332`0+36380t0g3c322%343i2/0w3m3e3o3g350v2,372/0I3t2^2(1s2{3y2}390r3D3f3G3h3I3A390R3M3v3O3x3z3j0G3U2_3W3q040u0h3#3F2O3X3J0u2;172?1f2X162L2y0l2C340K1X1~1e3{1h3_2#3?3105400U2Y3V3.0P0:0U0E3m3E340x2/4k3N3.0B0E0:2Q0p0k0L2i0y0C0d0L4p4e1?0/040f4E3$4r0:0{4C0k4K3-4G0:0J3m0t4l3w0B0:0e370k0Q4D482u4Y3W4H0F0b3t0t4?4X4q1?4g040i4j4+394-4M044O2o4W511?0v4n4|0p564_1L0P0K0:0q144Q4 571L4H4;4 064@5t4^4F5f0:2o0D4)154 5v4L4T4I4R345g5i5k5I3w4H4V5D5n3h4#4%4)5N4.4U4W5E4S5f5h045j2H5X3.4/3t5s4@5S350:0p0C0M5,5G5Q2Z5#3p0:0$5l2#5e0+5P5d5w5T045^0l685F1L0v0:0s6e5$6a54632?5:4?5=4{4}6k6004626v3w6h04020M0D0o6z3%5U1H5W5m65015p4=5u6r6N4{5z5B6H5-0:4J6M695?4|0B4w4y0i144A4C5{5o6Z6:6a5^5`6#6f665Z5R6N4!044$6K4*646$4/5}2?5 4Z611H6?6O6}5~5=706c7e5.5r5t6s0:0k1z4~7h6 7c6o317a3W6B020z6F6X2*6J4(743@6N6P7n6R7z4f5y0V6W6~766=6`6l6%6^7l7g797i7w7#04787y7(6(6*4z4B7J497L7W756{7Z0C6d7X34677U7{70727I7*0F0F6Q6S6$4{7r4w7*5q2Z6q5u7p046V0L5C7u7V5H7 7b6b5_7*7,2u7P7G6x7d8t5Y7+7F2{5@7}873D0S4b0k2v2W8P3`1p3|2y2A2w1W1Y2y4B1H2v3{0=0S0U0W0Y0p04.