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:pbv(40i2edm3;sN7= 1o5w_lSnatf)9h6,crgTyPFku8/050l0k0D0C0i0z0p0t0K0z0C0p0p0s010D0i0c010406050p0S0m0m0C0L0O040A0v0z0S0/0v0B050U0_0{0}0 0@0c04181f051i0U1i1k1f0@0l0i0e0%0)0+0-0H0i0M0H0z1y0H0D0=050Y0d0z0k1t0*0,011x1z1B1z0D1H1J1F0D0d0v0l0 1G0L1g0D0H0%120p0c0C0B0-0j011L1v010E0!0k0B0C0m0k1F1-1/1@1N1`1J1}1 0=0a0t0P0L0v0c0v0p0i150B0t0W1+0L0L0k0K2k18220B1g0U1)2x0D1%1$1(0l240-1B0B1|2h1F1q1s0(1M2H0i2J0B1Z1r1F0c2q1g2v2x2#0^1.2l2P1^2U0L0|0z0=0t0u2u2)0?2(232+1N2-2/2;0j2@1/2_2v2G012~0C2:040t0n322w0@352|0-383a0t0g3e342)363k2;0w3o3g3q3i370v2.392;0I3v2`2*1u2}3A2 3b0r3F3h3I3j3K3C3b0T3O3x3Q3z3B3l0G3W2{3Y3s040u0h3%3H2Q3Z3L0u2?192^1h2Z182N2A0l2E360K1Z201g3}1j3{2%3^3305420W2!3X3:0R0=0W0E3o3G360x2;4m3P3:0B0E0=2q0K0H0k0L4y0k0y0C0d0L4r4g1^0;040f4I3(4t0=0}4G0k4O3/4K0=0J3o0t4n3y0B0=0e390k0S4H4a2w4$3Y4L0F0b3v0t4`4#4s1^4i040i4l4/3b4;4Q044S2q4!551^0v4p500p5a4}1N0R0K0=0q164U535b1N4L4^53064{5x4|4J5j4w0X4-17535z4P4~5l040Q390p5p2#065w4{5r3j0=0p0C0M4V364L4Z5G5U370=0(5P3_5i0-5$5h5A5V045X0l5=5I1N0v0=0s5{4W2}4R0L4T4_5T5/014 51613r5+1J6d3y5~04020M0D0o6h3)4)4+4-5!3y5t675y5H620-4 2q0D5E6p564x4z4B4z4E4G6u4=0=4N5q694(5^5Y6O3:5;5(6T6r1J6t6S5?014?6x6z364 0k1B522#6.4%6f5-336^3Y6j020z6n6G2,6$4,4.2%696w5v6y4`5)6C5D0L5F6@5)6U6I4A4C6M775.6*4L6R786*6U5_6X4X045%7j6#044*6%7q4b790=0F6-7e0=6;5O7z5s0=5u5Q7c6}4h5C6E7h735j5K0N0L0S6{3f184d0k2x2Y7;3|1r3~2A2C2y1Y1!2A4F1J2x3}0@0U0W0Y0!0p04.