Vérification d'un ABR (0)

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 un arbre binaire qui :

soit est l’arbre vide identifié par None ;
soit possède une valeur, un sous-arbre gauche sag et un sous-arbre droit sad, tous les trois regroupés dans un triplet (sag, valeur, sad).

Exemple

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

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

a0 = (None, 0, None)
a3 = (None, 3, None)
a2 = (None, 2, a3)
ab1 = (a0, 1, a2)

Arbre binaire de recherche

On définit un arbre binaire de recherche comme étant un arbre binaire qui respecte la propriété suivante : pour chaque noeud de l'arbre,

les valeurs du sous-arbre gauche sont toutes inférieures à celle de la racine ;
les valeurs du sous-arbre droit sont toutes supérieures à celle de la racine ;
les valeurs contenues dans l'ABR sont uniques.

Exemples

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

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))

Il est défini par le code suivant :

a4 = (None, 4, None)
a0 = (None, 0, a4)
a3 = (None, 3, None)
a2 = (None, 2, a3)
ab2 = (a0, 1, a2)

fonction maximum_abr

Écrire une fonction récursive maximum_abr qui prend en paramètre un arbre binaire arbre non vide, et qui renvoie sa valeur maximum.

propriété

On considérera que l'arbre binaire passé en paramètre respecte les propriétés d'un ABR.

Exemple

>>> maximum_abr(ab1)
3

Évaluations restantes : 10/10

.128013x3SytbiIq)Nf4_dug[:k!he sPar(5]lRvow21/mnép;=c050p0x0f0B0h0G0z0y0U0G0B0z0z0T010f0h0R010406050z0q0O0O0B0C0e040d0J0G0q0/0J0P0y020B0O0R0S0y0H0x0|0C0j0q0x0z050N0_0{0}0 0@0R041n1u051x0N1x1z1u0@0p0h0I0%0)0+0-0w0h0r0w0G1N0w0f0=050Y0g0G0x1I0*0,011M1O1Q1O0f1W1Y1U0f0g0J0p0 1V0C1v0f0w0%120z0R0B0P0-0L011!1K010m0!0x0P1a0x1U1 21261$291Y2c0O2e040a0y0A0C0J0R0J0z0h15170W1}0C0C0x0U2z1n2g0P1v0N1{2L0f1_1^1`0p2i0-1Q0P2b2w1U1F1H0(1#2V0h2X0P1=1G1U0R2E1v2J2L2?0^20172%272,0C0|0G0=0M2I2`0?2_2h2|1$2~300=0L3421362J2U013b0B31040c3f2K0@3i390-3l3n0n3q3h2`3j3w0=0E3z1w2;1n2#2O0p2S3j0U1=2o0V1G1v2:0x2=353G3P0W3X381J1$0u0=0W0m3G3t3(0-0K0=0y3.3B3u3k0m0=0|0b0h0O0`0o0B0g0C3^3%2(010;040D472{3:3k0=0}450x4e3j4b0k0t3z060y4t3@3/493*040h3-1o354v3_4g0P4i0C4k4m3`4b0s4L4g0O0h3d4P494b0F3z4E48270J3=4z1m4C3g4Z4f4x0U0=0l164l4*2K374-274b4q4@0?4u504,3j4y2E0f0q0C0P4Y4_3C4I4K4~5b4M0=4O5f4w274R324U4{0=4X4~4s4u5g4g4y0x0#4?2^5l1$4|4r515v5D0-540X57594~523`4H043~404244465k4F4V0=4d5Z4!3a5d2E5p5E5i5-0-5n043e5(4`5.040F0k4r1n3!3W3H610N3K1n0f3M662Q2M1;1?2O441Y2L3K1t3$5_0-2E0O0o0m0B0u0x0o0w0c0=1f1h1j1l0y4}2^1A361u0i0G0y1l0f0y2v0+0h1X1Z2B0C0Q3m0h0z0x0C0y0q2X0y0I6Z2x160y2y0Q0C0B0/6)0y2B0)0y0m162G0h6,0t0@6F3S2$4g1(1P1R1T6k3j2k2b2d0=2q0d0U0C0:6M0A0e1{163G3V6k2@3Y607a3`4y3,5:014%3@5^3C3|5T0B3 416o5X7A4b5%5C5!2}5+5B3Y5J4a0=4p5G5I7R3)0=0K1M1Y5a7W5S4j5,7E5h045j7Q5)5;4S5?7N5r7,7$0-0J0=0v0T7 7_010u4/044;2X7}046D355u5H5w497.4J7:2?5Q4g8204855P8k7S047/7U3g8w5`7@7V80015=5@7^6l7X5{7!4t8C5K0=555N868L8m5e8K4n5/7;4Q7{338$5#8N5t5 3Q2L7r3J3T1y8:36640X0Z0#04.

fonction minimum_abr

Écrire une fonction récursive minimum_abr qui prend en paramètre un arbre binaire arbre non vide, et qui renvoie sa valeur minimale.

propriété

On considérera que l'arbre binaire passé en paramètre respecte les propriétés d'un ABR.

Exemple

>>> minimum_abr(ab1)
0

Évaluations restantes : 10/10

.1280133SytbiIq)Nf4_dug[:k!he sPar(5]lRvow21/mn0ép;=c050o0w0e0A0g0F0y0x0U0F0A0y0y0T010e0g0R010406050y0p0N0N0A0B0d040c0I0F0p0/0I0O0x020A0N0R0S0x0G0w0|0B0i0p0w0y050M0_0{0}0 0@0R041n1u051x0M1x1z1u0@0o0g0H0%0)0+0-0v0g0q0v0F1N0v0e0=050Y0f0F0w1I0*0,011M1O1Q1O0e1W1Y1U0e0f0I0o0 1V0B1v0e0v0%120y0R0A0O0-0K011!1K010l0!0w0O1a0w1U1 21261$291Y2c0N2e040a0x0z0B0I0R0I0y0g15170W1}0B0B0w0U2z1n2g0O1v0M1{2L0e1_1^1`0o2i0-1Q0O2b2w1U1F1H0(1#2V0g2X0O1=1G1U0R2E1v2J2L2?0^20172%272,0B0|0F0=0L2I2`0?2_2h2|1$2~300=0K3421362J2U013b0A31040b3f2K0@3i390-3l3n0m3q3h2`3j3w0=0D3z1w2;1n2#2O0o2S3j0U1=2o0V1G1v2:0w2=353G3P0W3X381J1$0t0=0W0l3G3t3(0-0J0=0x3.3B3u3k0l0=0N2*0g0N0`0n0A0f0B3^3%2(010;040C472{3:3k0=0}450w4e3j4b0j0s3z060x4t3@3/493*040g3-1o354v3_4g0O4i0B4k4m3`4b0r4L4g3~0=0P4P494b0E3z4E48270I3=4z1m4C3g4Z4f4x0U0=0k164l4*2K374-274b4q4@0?4u504,3j4y2E0e0p0B0O4Y4_3C4I4K4~5b4M0=4O5f4w274R04335k4F4V0=4X4~4s4u5g4g4y0w0#4?2^5l1$4|4r515x5F0-540X57594~523`4H043~0O404244465q4!5G0=4d5$4`3a5d2E4U4{5i5:1$5n4T5+4n5t0j4r1n3!3W3H610M3K1n0e3M662Q2M1;1?2O441Y2L3K1t3$5,0-2E0N0n0l0A0t0w0n0v0b0=1f1h1j1l0x4}2^1A361u0h0F0x1l0e0x2v0+0g1X1Z2B0B0Q3m0g0y0w0B0x0p2X0x0H6Z2x160x2y0Q0B0A0/6)0x2B0)0x0l162G0g6,0s0@6F3S2$4g1(1P1R1T6k3j2k2b2d0=2q0c0U0B0:6M0z0d1{163G3V6k2@3Y607a3`4y3,5?3;3?7A3{3}3 416o5!7D4b5*5E5r2}5.5D3Y5L4a0=4p5I5K7O3)0=0J1M1Y5a7T5U4j5/5`5h045j7N5%0-5^7K5t7)7Z0-0I0=0u0T7{7?010t4/044;2X7_046D355w5J5y497+4J7-2?5S4g7~04815R8g7P047,7R3g8s5(7:7D7^7.4g4W7X4t8y5M0=555P826l4h8u8j8w4^7T4N8B0g328a5u2?717v626h3T1y2L1D3J0X0Z0#04.

fonction est_abr

Écrire une fonction récursive est_abr qui prend en paramètres un arbre binaire arbre, et qui renvoie True si l'arbre est un arbre binaire de recherche et False sinon.

fonctions maximum_abr et minimum_abr

On pourra s'aider des fonctions maximum_abr et minimum_abr créées précédemment et déjà chargées en mémoire.

Exemple

>>> est_abr(abr1)
True
>>> est_abr(abr2)
False

Évaluations restantes : 10/10

.1280133ytbq)N4ê_7uj:k8s(ar5.lRLvU21mép;=cxASVi,F6fdg[he P]Tow/n0-B9050T0X0d0t0O0x0r0Y0J0x0t0r0r0I010d0O0G010406050r0m0E0E0t0u0c040M0$0x0m110$0)0Y020t0E0G0H0Y0y0X1b0u0f0m0X0r050(181a1c1e160G041C1J051M0(1M1O1J160T0O0A0_0{0}0 0W0O0U0W0x1$0W0d14050;0e0x0X1X0|0~011#1%1)1%0d1/1;1-0d0e0$0T1e1.0u1K0d0W0_1h0r0G0t0)0 0C011?1Z010S0?0X0)1p0X1-2e2g2l1^2o1;2r0E2t040a0Y0Z0u0$0G0$0r0O1k1m0/2c0u0u0X0J2O1C2v0)1K0(2a2!0d2827290T2x0 1)0)2q2L1-1U1W0`1@2.0O2:0)241V1-0G2T1K2Y2!35172f1m2_2m2~0u1b0x140D2X3915382w3b1^3d3f140C3j2g3l2Y2-013q0t3g040b3u2Z163x3o0 3A3C0i3F3w393y3L140v3O3H3Q3J3z0$3e3B140R3V3m3a1Y3p3!3r040l3)3I3,3K3.3$040q3=3X3@3Z3#3C0-3O1L331C2@2%0T2+3y0J242D0.1V1K320X343k444d0/4l3n3 0p140/0S443?2`010%140Y4x3~4z0)0S141A0d0k0t0e0u4E4r4z13040s4Q3+4G141c4O0X4W3y4T0g0o3V0Y4-4D4y2m4t040O4w1D3k4/4F3c4Z0u4#3O4{4R2m0$4B4?1B4_3v524X4;0J140h1l4$592Z3*4(144+5j154.5r5b3y4=2T0d0m0u0)515l3Y0p5e040#0u1z4,4.5C4s4J1)4^355t3Y55142~0d5B4:3p4~505p5M4S140V4%3Y0E0O140*5,3 4T0!5Y4|1^5U575_531^5E5f5h5~5c5{562g0T643R5#2T5=5)045+5%5Z0 5.3h6e2m5@6a5T14020x0d0H0I6q3 0)141b0K0O0E194M4O6n1^4T4V6i5`3K6c5i376j014T6h6S6O016l045;6N5 0 5@4*5K5s5S5N045w5y5A5p6.4z61040Q3B0r6R3k065r5(4;5O4@6y4z5|5W774}044!6d6%656)5*6J6k5/043t7g5m045^6@7366140O585R7u0 6`5g2:7b7v7d0)697t6T6A7d4 7f6X6(6U7j7p5-7m3i7U5?147s7z6T0$6s0U6v6x7K6Y7M5.0)6E6G4N4P7Y6f6M7Q7h3z6Q7k7S6g806!7o7|7q0!6+5p716-6^746:0:6=7F7B5F6|0@6 3v8b4-7A014=0X8m804T5o358p5s8r5v8g5z8i7~044K6H7^863Y6L807M7e8n5k6T6V837m6$8M7Z7r0g8G5|688G7M8J7@8w147{4m7L7 7_6o7T8Z4z848.8#3)0(4o4k45920(481C0d4a972)2#23252%4N1;2!481I4q7}2T0E0k0S0t0p0X0k0W0b141u1w1y1A0Y8y4m1P3l1J0z0t0Y0r1h1j0O1l0Y322J2L0F1=0O0J0O0Y0)004K9Q0|0Y2J113f1=0J1c0Y0?0Y9$0)0F0J1A0r0=2T0Y2Q2f0u4d5y0O0u9Q1i2M0X5y0^0S0$7x0Y0x008R9C9)1ma0a20u0daf9B4O2g0J0W9B7:6E3B1=0:0Y6Cay1;9~9-0W0t9A9K0$0m0r0+ai2K5y0Y0A0F0u4@0O0Xa50r000?0^9L0)ap0/0^0L0,0y0P0_1=1y9Y6E0G1)aKaKag9P0A9J2f0}aZa6aNaYaa0Yacae18a51;0^0E0j2C0^2~a90T0r0(b01;aa0w1L9G040z9#0KaZ9X9_4D9J0W2T0S0 0w0w0(bI0(2q0k2(0tb00m0KboaZaX9.2O0ka.0y0k0C0(140NaVbW0t2O9~000B0h0Yb!0Y0s0C8$0(0t049QaZ2Ca+ah0x1;a5a`aNafad1mbcaq9K0m0n0:a;2q9:1q2L2gap0naN0d1v2qa+1=bp0O0/a5a,b?a/0YbQ2U9~aM1:1l0rci1m9N1)9{a*0Y0m2:aC0F2a4e9)0G9+azbs9F16950:0=0@04.

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