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
.128013; l6yg/vS)iucbtf489wFT0oe5Psa_d=(7Nh2,3n:1kmpr050F0z0p0D0l0d0C0c0n0d0D0C0C0G010p0l0T010406050C0m0S0S0D0U0f040j0y0d0m0/0y0O050h0_0{0}0 0@0T04181f051i0h1i1k1f0@0F0l0i0%0)0+0-0K0l0g0K0d1y0K0p0=050Y0o0d0z1t0*0,011x1z1B1z0p1H1J1F0p0o0y0F0 1G0U1g0p0K0%120C0T0D0O0-0L011L1v010q0!0z0O0D0S0z1F1-1/1@1N1`1J1}1 0=0a0c0B0U0y0T0y0C0l150O0c0W1+0U0U0z0n2k18220O1g0h1)2x0p1%1$1(0F240-1B0O1|2h1F1q1s0(1M2H0l2J0O1Z1r1F0T2q1g2v2x2#0^1.2l2P1^2U0U0|0d0=0c0Q2u2)0?2(232+1N2-2/2;0L2@1/2_2v2G012~0D2:040c0N322w0@352|0-383a0c0r3e342)363k2;0A3o3g3q3i370y2.392;0e3v2`2*1u2}3A2 3b0I3F3h3I3j3K3C3b0s3O3x3Q3z3B3l0t3W2{3Y3s040Q0x3%3H2Q3Z3L0Q2?192^1h2Z182N2A0F2E360n1Z201g3}1j3{2%3^3305420W2!3X3:0R0=0W0q3o3G360u2;4m3P3:0O0q0=2q0n0K0z0U4y0z0E0D0o0U4r4g1^0;040H4I3(4t0=0}4G0z4O3/4K0=0M3o0c4n3y0O0=0i390z0m4H4a2w4$3Y4L0k0P3v0c4`4#4s1^4i040l4l4/3b4;4Q044S2q4!551^0y4p500C5a4}1N0R0n0=0J164U535b1N4L4^53064{5x4|4J5j4w0X4-17535z4P4~5l040v390C5p2#065w4{5r3j0=0C0D0g4V364L4Z5G5U370=0(5P3_5i0-5$5h5A5V045X0F5=5I1N0y0=0G5{4W2}4R0U4T4_5T5/014 51613r5+1J6d3y5~04020g0p0b6h3)4)4+4-5!3y5t675y5H620-4 2q0p5E6p564x4z4B4z4E4G6u4=0=4N5q694(5^5Y6O3:5;5(6T6r1J6t6S5?014?6x6z364 0z1B522#6.4%6f5-336^3Y6j020d6n6G2,6$4,4.2%696w5v6y4`5)6C5D0U5F6@5)6U6I4A4C6M775.6*4L6R786*6U5_6X4X045%7j6#044*6%7q4b790=0k6-7e0=6;5O7z5s0=5u5Q7c6}4h5C6E7h735j5K0w0U0m6{3f184d0z2x2Y7;3|1r3~2A2C2y1Y1!2A4F1J2x3}0@0h0W0Y0!0C04.