Recherche 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 recherche_abr qui prend en paramètres un arbre binaire de recherche abr et une cible valeur, et qui renvoie True si l'ABR contient la cible et False sinon.

Exemple

>>> recherche_abr(abr_1, 4)
False
>>> insertion_abr(abr_1, 0)
True

Tests

Les tests de la fonction se dérouleront en deux temps :

  • les tests s'assureront d'abord que la fonction renvoie des réponses correctes ;
  • sa complexité en temps est ensuite testée, pour vérifier qu'elle respecte les spécifications attendues pour un ABR.

Tests aléatoires et performances

Votre tracé sera ici

###(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:vT,P1Ssin9y0_t54NrF32c6=050n0r0K0c0E0g0D0p0S0g0c0D0D0U010K0E0k010406050D0b0u0u0c0O0H040C0o0g0b0/0o0F050d0_0{0}0 0@0k04181f051i0d1i1k1f0@0n0E0x0%0)0+0-0t0E0m0t0g1y0t0K0=050Y0h0g0r1t0*0,011x1z1B1z0K1H1J1F0K0h0o0n0 1G0O1g0K0t0%120D0k0c0F0-0R011L1v010v0!0r0F0c0u0r1F1-1/1@1N1`1J1}1 0=0a0p0A0O0o0k0o0D0E150F0p0W1+0O0O0r0S2k18220F1g0d1)2x0K1%1$1(0n240-1B0F1|2h1F1q1s0(1M2H0E2J0F1Z1r1F0k2q1g2v2x2#0^1.2l2P1^2U0O0|0g0=0p0B2u2)0?2(232+1N2-2/2;0R2@1/2_2v2G012~0c2:040p0Q322w0@352|0-383a0p0M3e342)363k2;0L3o3g3q3i370o2.392;0T3v2`2*1u2}3A2 3b0q3F3h3I3j3K3C3b0j3O3x3Q3z3B3l0G3W2{3Y3s040B0I3%3H2Q3Z3L0B2?192^1h2Z182N2A0n2E360S1Z201g3}1j3{2%3^3305420W2!3X3:0s0=0W0v3o3G360i2;4m3P3:0F0v0=2q0S0t0r0O4y0r0J0c0h0O4r4g1^0;040f4I3(4t0=0}4G0r4O3/4K0=0z3o0p4n3y0F0=0x390r0b4H4a2w4$3Y4L0l0w3v0p4`4#4s1^4i040E4l4/3b4;4Q044S2q4!551^0o4p500D5a4}1N0s0S0=0N164U535b1N4L4^53064{5x4|4J5j4w0X4-17535z4P4~5l040P390D5p2#065w4{5r3j0=0D0c0m4V364L4Z5G5U370=0(5P3_5i0-5$5h5A5V045X0n5=5I1N0o0=0U5{4W2}4R0O4T4_5T5/014 51613r5+1J6d3y5~04020m0K0e6h3)4)4+4-5!3y5t675y5H620-4 2q0K5E6p564x4z4B4z4E4G6u4=0=4N5q694(5^5Y6O3:5;5(6T6r1J6t6S5?014?6x6z364 0r1B522#6.4%6f5-336^3Y6j020g6n6G2,6$4,4.2%696w5v6y4`5)6C5D0O5F6@5)6U6I4A4C6M775.6*4L6R786*6U5_6X4X045%7j6#044*6%7q4b790=0l6-7e0=6;5O7z5s0=5u5Q7c6}4h5C6E7h735j5K0y0O0b6{3f184d0r2x2Y7;3|1r3~2A2C2y1Y1!2A4F1J2x3}0@0d0W0Y0!0D04.