Vérification d'un ABR (2)

Série d'exercices

Le but de cet exercice est de vérifier si un arbre binaire est un arbre binaire de recherche.

Les exercices suivants ont le même but mais avec des approches différentes :

Arbre binaire

On considère des arbres binaires qui sont :

soit l’arbre vide identifié par None ;
soit un nœud, contenant une clé et deux sous-arbres gauche et droit et représenté par un triplet (valeur, sag, sad) où valeur est la clé, et sag et sad sont les sous-arbres gauche et droit.

Exemple

graph
a((4)) --- b((1))
b --- d((0))
b --- n5((3))
a --- c((5))
c --- e((" "))
c --- n3((6))
style e fill:none,stroke:none,color:none

Ainsi, l’arbre binaire ci-dessus est créé par le code python suivant :

ab_5 = (4, (1, (0, None, None),
               (3, None, None),
           ),
           (5, None,
               (6, None, None),
           )
       )

Arbre binaire de recherche

On définit un arbre binaire de recherche stockant les doublons à droite comme étant un arbre binaire qui respecte les propriétés suivantes :

les valeurs du sous-arbre gauche sont toutes inférieures à celle de la racine ;
les valeurs du sous-arbre droit sont toutes supérieures ou égales à celle de la racine.

Exemples

Ainsi l'arbre précédent est bien un ABR.

L'arbre ci-dessous en est un également, avec une valeur en doublon "à droite" :

graph
a((4)) --- b((1))
b --- d((0))
b --- n5((3))
a --- c((5))
c --- e((4))
c --- n3((6))

L’arbre binaire ci-dessus est créé par le code python suivant :

ab_6 = (4, (1, (0, None, None),
               (3, None, None),
           ),
           (5, (4, None, None),
               (6, None, None),
           )
       )

En revanche l'arbre ci-dessous n'en est pas un :

graph
n1((1)) --- n0((0))
n0 --- n6((" "))
n0 --- n5((4))
n1 --- n2((2))
n2 --- n4((" "))
n2 --- n3((3))
style n4 fill:none,stroke:none,color:none
style n6 fill:none,stroke:none,color:none

Il est défini par le code suivant :

ab_4 = (1, (0, None,
               (4, None, None),
            2, None,
               (3, None, None),
           )
       )

Et celui-ci n'en est pas un non plus (le doublon est à gauche) :

graph
a((4)) --- b((1))
b --- d((0))
b --- n5((3))
a --- c((5))
c --- e((5))
c --- n3((6))

L’arbre binaire ci-dessus est créé par le code python suivant :

ab_7 = (4, (1, (0, None, None),
               (3, None, None),
           ),
           (5, (5, None, None),
               (6, None, None),
           )
       )

On souhaite écrire la fonction est_abr qui prend en paramètre un arbre binaire arbre, et renvoie True si l'arbre est un arbre binaire de recherche (avec les éventuels doublons à droite) et False sinon.

L'implémentation doit être optimale et le comportement doit donc être linéaire en nombre de valeurs dans l'arbre, $O(N)$.

Indices logiques

La valeur portée par la racine constitue une limite pour les valeurs envisageables pour ses deux enfants.

Indice 2

Imaginons que l'on sache que la racine en cours peut prendre n'importe quelle valeur comprise entre $L$ et $R$.

Si on nomme $V$ la valeur de la racine, que peut-on dire de l'intervalle des valeurs possibles pour l'enfant de gauche ? Et lm'enfant droit ?

Indice 3

Ne pas oublier qu'il peut y avoir des doublons ! Sur la droite !

Indice 4

Un des problèmes essentiels à résoudre est de trouver comment "démarrer".
Quelles sont les valeurs possibles au tout début, lorsqu'on est sur la racine de l'arbre passé en argument à la fonction est_abr ?

Indice 5

... Il y en a une infinité !

Indices techniques

Lors d'un appel de fonction, il sera nécessaire d'avoir des informations en plus de l'arbre lui-même. Il peut donc être intéressant de travailler avec une fonction auxiliaire, ou même mieux, une sous fonction. Cette fonction accepterait des arguments en plus de l'arbre à valider : autant que nécessaire pour répondre à la question.

Indice B

Pour chaque appel, il faut savoir quel est l'arbre à valider, et aussi quelle sont les bornes actuellement valides.

Indice C

Le module math contient différentes fonctions... Et constantes...
Comme par exemple, inf.

Évaluations restantes : 10/10

.65038.128203.128013.9875s3_8èufvIy 7naêS1me(P4C2V:jtwiDhE)6Oo;bcdgM?/T0lîàqABp.rL-,=Nk95Rxé050S0w0F0r0H0Z0e0o0R0Z0r0e0e0/010F0H0)010406050e0j0v0v0r0+0n040t0O0Z0j1a0O0q0o020r0v0)0P0o0@0w1k0+0$0j0w0e050W1h1j1l1n1f0)041L1S051V0W1V1X1S1f0S0H0l121416180J0H0T0J0Z1/0J0F1d050}0Q0Z0w1*1517011.1:1=1:0F1{1}1_0F0Q0O0S1n1`0+1T0F0J121q0e0)0r0q180B011 1,010k0 0w0q1y0w1_2n2p2u212x1}2A0v2C040c0o0y0+0O0)0O0e0H1t1v0{2l0+0+0w0R2X1L2E0q1T0W2j2-0F2h2g2i0S2G181=0q2z2U1_1%1)13202`0H2|0q2d1(1_0)2$1T2+2-3e1g2o1v322v370+1k0Z1d0o0u2*3i1e3h2F3k213m3o3q0B3t2p3v2+2_013A0r3p040o0f3E2,1f3H3y183K3M0o0z3Q3G3i3I3W3q0?3!3S3$3U3J0O3n3L3q0M3+3w3j1+3z3:3B3N0p3^3T3{3V3}3=3N0h413-433/3;3X0=493x4b3(040u0Y4g3`334c3~0u3s1M3u1U3c1L302:0S2@3I0R2d2M0`1(1T3b0w3d4v4u3F054E0{4M4h4p0;0q1d0k2R0v3!3_3I0G3q4$424p0q4X041k2j4+4a4p4)3N4?4U2v4W1d0H1z3:0F3!0o4%3.4/350k3+3,4|210;1d0{5a4O2,564b4_555j4T4o3l0k1d1J0F0g0r0Q0+4{5r211c040x5B3%1d1l5z0w5H3.5E0L0D5b0o5T554,4}5g0w5i3g5W215n5N4i5t04350F0w0+2|5)4p5E5G5p5l4-1d0v350H5=2v5E0.545`3l5J0Q605D1d635p5V4@664:0r0^5 5_5$185P5R5p065U6s6e5d185f5,5!3u6u5C180O4_37536d653z67696n1d6p3e6r6t6S6J6w1d2$0F0j5:646m010;0R1d0X0+1I3+6S5T6U3J1d0l3L6M01626#6f6K040e0r0T6_6{6I6$4/700S6|6v010O1d0/7a6C6=045y6.6/6;6x6X6Z0q7g5I4:5~7s3.7d04020Z0F0P7f756}3V6?6^7F7b6E5J0q797K7h4/6@0Z7w4b7y7A7C7V5{6h6j7!2v7M7j7O7(6~5-5/5;6l7G6`1d5^5#7?4/5}0q6k7`7b743e6B7t70727=816b7-7H047T731d0L8b7c4_2p7P836;580q5.5:5M887h5@6_7S7J808v8a7Q850r8m4v6$826A8o5|6i7 8H7?5P5S5U7n6W0|7q8i8p8r7;8A3I8w8u3I7y0-8x4 0q6z4P8I8C8n765J0+5L8f046c8@7{8.8:5k8=048h6q1L4R4L4w9a0W4z1L0F4B9f2=2.2c2e2:5y1}2-4z1R5q3I2$0v0g0k0r0;0w0g0J0f1d1D1F1H1J0o6P4N1#1W040,0r0o0e1q1s0H1u0o0l0O0j1r1~0H0R0H0o2$1H0H5/0F0o0j2|0o500)0Z0_2L8q0r2X0o2{0_0~2$0o2z0o5.1z116;1l2W0J4;0w0^1d090x0N0x0:0L09963e0.121~9-a50e9:1}12150o2S1a3o0o2T6Zata70n0)1~2Z9Iax9W1v0x0 0o9y1s9Y0_0+0H2x5/9;9?0k0O0H110F9!111}11370w0j0S112Z0Z005Ka42o160_a51v1l0T1i2z0F0L0*1U3v1S0:0O8r0o9I0o0S2pa:9R9T1r9 3b2S2U0_0was9X5.ax1~149Y3L0H1%0Fb2a{007/0+7Taz1h0+a09R7Ta@bQa64E6Z110r6@8qbk1~9y0Ha4a;0o0r0)aM109+0_0RbYa#0eas0r2x2Y1~a)a31~0Ra@0^0-9)9Sa@1}9|9:2VbRbD1}aI5vcfbF1~0xcd0w0Zaz9?a|159:b0asaUci359Vaz2ZaM0+0Sa40S0ja71E0)110#aVc1a09Jb.b:110+b?b^0k110DaC1v702Wbk0_0EcNbjcs8`a40q00cib0a(0o0%0(0@babc9s0m0Zaw9:5-aZ1J70b$9(9*2Z4E1z1la%b!2%cQbZb/2R0R0J9Jbs2T0ebva`bma0c=0^5/9)c3559R0J2$0k180*0*0WdH0Wagdy9(1J0W0l5/a#9(9~aR0gc`0@0W1d0CaZdT0RdV9X0S009=c_c{0o0x0u960r04bb1Ybd9Pdo9v0H0i2$a`a#0kd50qc3119Tb$6p9N1q3v1=9Pbo2;0j2(6ZaN9J6Y9_9Jdm2p0T1~c!4Q4F5F0las86eB8F96993Nd9as4E8qa4ex4Scm71aseA9SeE98eybkdubC4K5}e11~dR0+2V1u0*0o0A0|5.0o0v382xd)9 9?dq1~0rek9=aNe49(9#bHd`eg1feg0,9J0S9!1|1ue91u9:e}a.a!dr11d9a59:fb1(b80o0s2;e%bE0S0_11dc2L0o0_0}b$cNcFa+5.b{0Z3:11c-9Re!e0a4e(e*1v9?eK2Vfy0+0~cuaBb,fb0jfd0q0ef50H3v0Wee1f9D9u1E9x9z9B9D2tbF18bp9V1u0-cAa,2p0F0-7}501i5x5z0-0|ga8N0vgd5y0+1d1pbqaR9;1a1=d79:eN4Lgbgk9wgmeV4Sfo55eG1k6jgAge5A0WeG059R3.dn8F5/2{5f0odD5Z1803g22Xg5gtg78qga5~gKgmggg9gIgcgB5z2t1a0F1}180y5/1k36ay356x0d0a1Ld^1L9Dd|e.27e|dk0Odm1~ci9`0Te$cb9Sa/0-aD503Lc21la5cp9%510eenaG1lbXa!bQ9_0j2VbU11a*a,die;0s2La=0Oa@a_eXf-dva~0we,0Khx0oe`20aN1u0RhCa:eo5va`1~cDa*3;e71Jd`9N1S0Id-1v2T5-b%9Y1Ia00O0T0H9IascoazaMaXc3aM7Og8ftfve;a,1~cN0E9!hGis0o0Td5bQ4E2#2%a8fsbC7TbFd*b~a`fcfMhXa6e=1%2xik2V1zcaiD1~2c1v2SaZ9~bUi4dc2of#a,e+c~05f^3.9vf{9A9C9E9@0S6n150-0{0-g$aR0-dg0Rg50q0-i)hE0e0-590Hdxjb9)1d0yaB2Zj09Xj3c^j8isfm8/jdbw9@9)gP3IgS0{0+gV2tgYdF0103b0i}0wi 9Ug%j3j5j7hDjqjbjsjed9g_2Wg|01g~h_iDh31dh5h72-ha9s0Ni1isi*d31ki92|bQ2$4K7Ob+bojMgrjniejRbY9@jUh!1f5z04hce:cSdldnd2fD0Ththnhr3ohi1v8rfCdb0OiTag2Wb2a6a8cLeB9*idhiaxb=bEdre|dRh-a.1s9JhA11fEb.9Ja1c111kycK110x0Rc=ax0-0#i}b*evcecVkHiHbkcIjpk5jcdxgFiEd%e@k:fPa0a,e:0O0Q5.0qi6ci0Q9.kpa!bv0L9Ki-f?05egji0+j9k62xdxew6$ac2jafah04ajalanap54aTd1c0aXfbe7h.gs0 iobQkse79~0_2A9 a{l11Jc}0Wf6lif:d$a!a$bQk gue:ci0R2Ra,gvh?hvi(1l0~eab%11bTk51h0Re82VdR0elq7?lsaei#lvlxamaoaq6A0xlG0ReDhXg6hAlM1~2;0HlWlYf=0Zd|0Ul^athdb-hfhhh(k$f%11mk9o9%c7d)bQ1g2;1u0T04cs5zb-1s3:iohOf*f,cMbkl.5.2*mN0qmPe,0N0+b{kKcQhClljqlnjtbxi15/2^a|59459 bPceax6,ela4bL9?bJhZicd3lDmDaG1r11dq2V1|hB709Zb*9S9*f)iKfehofGm#fJ1~9!0ocNkjekkg0xnA0)k+9Kc^0v0_14m*enh=0j0^ba0o0K1v5Z0k0|eJeol.bZc/fa1uh1a50^0r2(1EiVhPfCk?e)m^k_ec3v30jy1?251@2D7?2I2z2B1d0b0o0Xagm%5_4K5q3f4veG6/0o0?6/om6S0?6R6t0W6/ot096/09or5Uoo6toBoB6soqosokoI6soyoFoJoN5ToqgD9cof4y4If@0ff_9w9yi?f~i_g1hpa*e7g%9!j20+b6cbjai)jJaW1^1oo)h,9 nAb5b78qnihvfyo^0o0VjxgR0wgTjBj(gXdEg!9ThI0-o*2(j1o-o o;jQ0+o@fijXg{0wg}g 2pj%0qh4h60Wh80Wj-9Oj/mTj=aGcImka%0{p2f#0v0ifvpRc)p5aHhGh*bQb,2c8sh=dvbLbNfw1=2Z1%2$n:hncNbCpk9 gx045vgLoR3Ne}l0a@bkd-g)mla(1~phjap`grn|1$1(n 241?o_6;o52K2M2O0tl-1b9:0y0n2j1u4$oT3g5_gO6$6x5h6_5(8)575+p~gCqJ4b8(8$578_8{qO5?8?8K8^7u7~6_7y0/8,qV6g598|8~qY907$8O8;7?q%8-5,8/8|5Q7l6:6$7ydHd`6Qq09b9qoV9Oe.n(o:b8ffb$ih2zblb$1=fznBcefMi9bj2ZcVjlnX9:n90w0li*fsc@b)a 1l1ahBm~8q5/9ydAn/m00Hnlrma|mG5.aIqf059#eff:0Ik=a+b$2Z0li6bJrSbUcwnefQaB0Q1Jr$i%n+0r0!ima|kvbAh`i%cRo/p00Ff.1LlYegr!aGr$fpe%r*k=2R0TpS2L6Zn#rbs411hrn+core9:d.01fk9I2tc!d.r,aIpZpLcScoa%p_o|grbW0Ja+2V16ikb,l|n_b0kIniiup%3:2|b`mTq3cIa{l^q80ea}b/1=9Ip$9JsTpWp4fie,e.iEa@fpnJ1Hi0lJgui#sDj;f$aA16sI9Rroiar*bBa}0Z0TmVlth!s7f:1f0WrX9s0,q6lK70lSi0qao{o+sLkFmgq9aV3}aNc=lOcL9#iHeJktfC9Xif9:a6i)1}itaIeZshsjk:l30E0|lfd{1ftrlZehtGtB9Xoc7:1~j{rsb8tgbLrKf02n1urOazp^tut4rTbVccc9n;rfkDc60Hf/rYt/qbpjsK9Xi+azbCtdrqt^fzk0d+t|rI0+t~n-8!jut)kjf#8qc(c-erfgf#s5i7rp1Ie95/fg9+1JaM2(fzugtpt-9d0|0~1004.

Si une erreur est levée durant les tests secrets, l'arbre ayant provoqué l'erreur est affiché ci-dessous :

Dernier arbre testé (en cas d'erreur)

Votre tracé sera ici