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

.128013s3o_;bcdufvgI/lyq napS!r1meh(P2=4:Ntwki][5Rx)é050i0B0K0u0N0p0b0s0h0p0u0b0b0G010K0N0v010406050b0j0A0A0u0y0q040w0d0p0j0/0d0t0s020u0A0v0f0s0R0B0|0y0r0j0B0b050o0_0{0}0 0@0v041n1u051x0o1x1z1u0@0i0N0l0%0)0+0-0C0N0m0C0p1N0C0K0=050Y0g0p0B1I0*0,011M1O1Q1O0K1W1Y1U0K0g0d0i0 1V0y1v0K0C0%120b0v0u0t0-0F011!1K010k0!0B0t1a0B1U1 21261$291Y2c0A2e040a0s0E0y0d0v0d0b0N15170W1}0y0y0B0h2z1n2g0t1v0o1{2L0K1_1^1`0i2i0-1Q0t2b2w1U1F1H0(1#2V0N2X0t1=1G1U0v2E1v2J2L2?0^20172%272,0y0|0p0=0z2I2`0?2_2h2|1$2~300=0F3421362J2U013b0u31040c3f2K0@3i390-3l3n0H3q3h2`3j3w0=0Q3z1w2;1n2#2O0i2S3j0h1=2o0V1G1v2:0B2=353G3P0W3X381J1$0M0=0W0k3G3t3(0-0L0=0s3.3B3u3k0k0=0|0S0N0A0`0e0u0g0y3^3%2(010;040D472{3:3k0=0}450B4e3j4b0T0I3z060s4t3@3/493*040N3-1o354v3_4g0t4i0y4k4m3`4b0P4L4g0A0N3d4P494b0O3z4E48270d3=4z1m4C3g4Z4f4x0h0=0J164l4*2K374-274b4q4@0?4u504,3j4y2E0K0j0y0t4Y4_3C4I4K4~5b4M0=4O5f4w274R324U4{0=4X4~4s4u5g4g4y0B0#4?2^5l1$4|4r515v5D0-540X57594~523`4H043~404244465k4F4V0=4d5Z4!3a5d2E5p5E5i5-0-5n043e5(4`5.040O0T4r1n3!3W3H610o3K1n0K3M662Q2M1;1?2O441Y2L3K1t3$5_0-2E0A0e0k0u0M0B0e0C0c0=1f1h1j1l0s4}2^1A361u0n0p0s1l0K0s2v0+0N1X1Z2B0y0U3m0N0b0B0y0s0j2X0s0l6Z2x160s2y0U0y0u0/6)0s2B0)0s0k162G0N6,0I0@6F3S2$4g1(1P1R1T6k3j2k2b2d0=2q0w0h0y0:6M0E0q1{163G3V6k2@3Y607a3`4y3,5:014%3@5^3C3|5T0u3 416o5X7A4b5%5C5!2}5+5B3Y5J4a0=4p5G5I7R3)0=0L1M1Y5a7W5S4j5,7E5h045j7Q5)5;4S5?7N5r7,7$0-0d0=0x0G7 7_010M4/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

.128013s3o_;bcdufvgI/0lyq napS!r1meh(P2=4:Ntwki][5R)é050i0C0L0v0O0q0b0t0h0q0v0b0b0H010L0O0w010406050b0j0B0B0v0z0r040x0d0q0j0/0d0u0t020v0B0w0f0t0S0C0|0z0s0j0C0b050o0_0{0}0 0@0w041n1u051x0o1x1z1u0@0i0O0l0%0)0+0-0D0O0m0D0q1N0D0L0=050Y0g0q0C1I0*0,011M1O1Q1O0L1W1Y1U0L0g0d0i0 1V0z1v0L0D0%120b0w0v0u0-0G011!1K010k0!0C0u1a0C1U1 21261$291Y2c0B2e040a0t0F0z0d0w0d0b0O15170W1}0z0z0C0h2z1n2g0u1v0o1{2L0L1_1^1`0i2i0-1Q0u2b2w1U1F1H0(1#2V0O2X0u1=1G1U0w2E1v2J2L2?0^20172%272,0z0|0q0=0A2I2`0?2_2h2|1$2~300=0G3421362J2U013b0v31040c3f2K0@3i390-3l3n0I3q3h2`3j3w0=0R3z1w2;1n2#2O0i2S3j0h1=2o0V1G1v2:0C2=353G3P0W3X381J1$0N0=0W0k3G3t3(0-0M0=0t3.3B3u3k0k0=0B2*0O0B0`0e0v0g0z3^3%2(010;040E472{3:3k0=0}450C4e3j4b0T0J3z060t4t3@3/493*040O3-1o354v3_4g0u4i0z4k4m3`4b0Q4L4g3~0=0p4P494b0P3z4E48270d3=4z1m4C3g4Z4f4x0h0=0K164l4*2K374-274b4q4@0?4u504,3j4y2E0L0j0z0u4Y4_3C4I4K4~5b4M0=4O5f4w274R04335k4F4V0=4X4~4s4u5g4g4y0C0#4?2^5l1$4|4r515x5F0-540X57594~523`4H043~0u404244465q4!5G0=4d5$4`3a5d2E4U4{5i5:1$5n4T5+4n5t0T4r1n3!3W3H610o3K1n0L3M662Q2M1;1?2O441Y2L3K1t3$5,0-2E0B0e0k0v0N0C0e0D0c0=1f1h1j1l0t4}2^1A361u0n0q0t1l0L0t2v0+0O1X1Z2B0z0U3m0O0b0C0z0t0j2X0t0l6Z2x160t2y0U0z0v0/6)0t2B0)0t0k162G0O6,0J0@6F3S2$4g1(1P1R1T6k3j2k2b2d0=2q0x0h0z0:6M0F0r1{163G3V6k2@3Y607a3`4y3,5?3;3?7A3{3}3 416o5!7D4b5*5E5r2}5.5D3Y5L4a0=4p5I5K7O3)0=0M1M1Y5a7T5U4j5/5`5h045j7N5%0-5^7K5t7)7Z0-0d0=0y0H7{7?010N4/044;2X7_046D355w5J5y497+4J7-2?5S4g7~04815R8g7P047,7R3g8s5(7:7D7^7.4g4W7X4t8y5M0=555P826l4h8u8j8w4^7T4N8B0O328a5u2?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

.128013s3_8ufvy n7aêS1me(P24V:jtwi][h)6o;bcdUg/T0lqABp.rFL-,=Nk95Rxé050L0r0z0m0B0R0b0j0K0R0m0b0b0$010z0B0V010406050b0f0q0q0m0X0i040o0H0R0f110H0k0j020m0q0V0I0j0+0r1b0X0S0f0r0b050O181a1c1e160V041C1J051M0O1M1O1J160L0B0h0_0{0}0 0E0B0N0E0R1$0E0z14050;0J0R0r1X0|0~011#1%1)1%0z1/1;1-0z0J0H0L1e1.0X1K0z0E0_1h0b0V0m0k0 0u011?1Z010g0?0r0k1p0r1-2e2g2l1^2o1;2r0q2t040a0j0t0X0H0V0H0b0B1k1m0/2c0X0X0r0K2O1C2v0k1K0O2a2!0z2827290L2x0 1)0k2q2L1-1U1W0`1@2.0B2:0k241V1-0V2T1K2Y2!35172f1m2_2m2~0X1b0R140p2X3915382w3b1^3d3f140u3j2g3l2Y2-013q0m3g040c3u2Z163x3o0 3A3C0v3F3w393y3L140*3O3H3Q3J3z0H3e3B140G3V3m3a1Y3p3!3r040l3)3I3,3K3.3$040e3=3X3@3Z3#3C0)3O1L331C2@2%0L2+3y0K242D0.1V1K320r343k444d0/4l3n3 0(140/0g443?2`010A140j4x3~4z0k0g141A0z0d0m0J0X4E4r4z13040s4Q3+4G141c4O0r4W3y4T0F0x3V0j4-4D4y2m4t040B4w1D3k4/4F3c4Z0X4#3O4{4R2m0H4B4?1B4_3v524X4;0K140%1l4$592Z3*4(144+5j154.5r5b3y4=2T0z0f0X0k515l3Y0(5e040P0X1z4,4.5C4s4J1)4^355t3Y55142~0z5B4:3p4~505p5M4S140D4%3Y0q0B140Q5,3 4T0C5Y4|1^5U575_531^5E5f5h5~5c5{562g0L643R5#2T5=5)045+5%5Z0 5.3h6e2m5@6a5T14020R0z0I0$6q3 0k141b0,0B0q194M4O6n1^4T4V6i5`3K6c5i376j014T6h6S6O016l045;6N5 0 5@4*5K5s5S5N045w5y5A5p6.4z61040Y3B0b6R3k065r5(4;5O4@6y4z5|5W774}044!6d6%656)5*6J6k5/043t7g5m045^6@7366140B585R7u0 6`5g2:7b7v7d0k697t6T6A7d4 7f6X6(6U7j7p5-7m3i7U5?147s7z6T0H6s0N6v6x7K6Y7M5.0k6E6G4N4P7Y6f6M7Q7h3z6Q7k7S6g806!7o7|7q0C6+5p716-6^746:0:6=7F7B5F6|0@6 3v8b4-7A014=0r8m804T5o358p5s8r5v8g5z8i7~044K6H7^863Y6L807M7e8n5k6T6V837m6$8M7Z7r0F8G5|688G7M8J7@8w147{4m7L7 7_6o7T8Z4z848.8#3)0O4o4k45920O481C0z4a972)2#23252%4N1;2!481I4q7}2T0q0d0g0m0(0r0d0E0c141u1w1y1A0j8y4m1P3l1J0Z0m0j0b1h1j0B1l0j322J2L0-1=0B0K0B0j0k004K9Q0|0j2J113f1=0K1c0j0?0j9$0k0-0K1A0b0=2T0j2Q2f0X4d5y0B0X9Q1i2M0r5y0^0g0H7x0j0R008R9C9)1ma0a20X0zaf9B4O2g0K0E9B7:6E3B1=0:0j6Cay1;9~9-0E0m9A9K0H0f0b0!ai2K5y0j0h0-0X4@0B0ra50b000?0^9L0kap0/0^0T0U0+0#0_1=1y9Y6E0V1)aKaKag9P0h9J2f0}aZa6aNaYaa0jacae18a51;0^0q0n2C0^2~a90L0b0Ob01;aa0W1L9G040Z9#0,aZ9X9_4D9J0E2T0g0 0W0W0ObI0O2q0d2(0mb00f0,boaZaX9.2O0da.0+0d0u0O140waVbW0m2O9~000M0%0jb!0j0s0u8$0O0m049QaZ2Ca+ah0R1;a5a`aNafad1mbcaq9K0f0y0:a;2q9:1q2L2gap0yaN0z1v2qa+1=bp0B0/a5a,b?a/0jbQ2U9~aM1:1l0bci1m9N1)9{a*0j0f2:aC0-2a4e9)0V9+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