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

.1280135[tf4)2IrR3sa!o iugxm1]PpNnlhe=céy:v(wq;S/b_dk050T0E0d0n0r0C0m0q0G0C0n0m0m0F010d0r0z010406050m0s0v0v0n0j0I040P0p0C0s0/0p0B0q020n0v0z0O0q0k0E0|0j0N0s0E0m050Q0_0{0}0 0@0z041n1u051x0Q1x1z1u0@0T0r0K0%0)0+0-0D0r0t0D0C1N0D0d0=050Y0R0C0E1I0*0,011M1O1Q1O0d1W1Y1U0d0R0p0T0 1V0j1v0d0D0%120m0z0n0B0-0h011!1K010e0!0E0B1a0E1U1 21261$291Y2c0v2e040a0q0y0j0p0z0p0m0r15170W1}0j0j0E0G2z1n2g0B1v0Q1{2L0d1_1^1`0T2i0-1Q0B2b2w1U1F1H0(1#2V0r2X0B1=1G1U0z2E1v2J2L2?0^20172%272,0j0|0C0=0w2I2`0?2_2h2|1$2~300=0h3421362J2U013b0n31040l3f2K0@3i390-3l3n0f3q3h2`3j3w0=0b3z1w2;1n2#2O0T2S3j0G1=2o0V1G1v2:0E2=353G3P0W3X381J1$0U0=0W0e3G3t3(0-0M0=0q3.3B3u3k0e0=0|0u0r0v0`0S0n0R0j3^3%2(010;040L472{3:3k0=0}450E4e3j4b0g0J3z060q4t3@3/493*040r3-1o354v3_4g0B4i0j4k4m3`4b0c4L4g0v0r3d4P494b0x3z4E48270p3=4z1m4C3g4Z4f4x0G0=0A164l4*2K374-274b4q4@0?4u504,3j4y2E0d0s0j0B4Y4_3C4I4K4~5b4M0=4O5f4w274R324U4{0=4X4~4s4u5g4g4y0E0#4?2^5l1$4|4r515v5D0-540X57594~523`4H043~404244465k4F4V0=4d5Z4!3a5d2E5p5E5i5-0-5n043e5(4`5.040x0g4r1n3!3W3H610Q3K1n0d3M662Q2M1;1?2O441Y2L3K1t3$5_0-2E0v0S0e0n0U0E0S0D0l0=1f1h1j1l0q4}2^1A361u0i0C0q1l0d0q2v0+0r1X1Z2B0j0H3m0r0m0E0j0q0s2X0q0K6Z2x160q2y0H0j0n0/6)0q2B0)0q0e162G0r6,0J0@6F3S2$4g1(1P1R1T6k3j2k2b2d0=2q0P0G0j0:6M0y0I1{163G3V6k2@3Y607a3`4y3,5:014%3@5^3C3|5T0n3 416o5X7A4b5%5C5!2}5+5B3Y5J4a0=4p5G5I7R3)0=0M1M1Y5a7W5S4j5,7E5h045j7Q5)5;4S5?7N5r7,7$0-0p0=0o0F7 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

.1280135[tf4)2IrR3sa!o iug0m1]PpNnlhe=céy:v(wq;S/b_dk050T0E0d0n0r0C0m0q0G0C0n0m0m0F010d0r0z010406050m0s0v0v0n0j0I040P0p0C0s0/0p0B0q020n0v0z0O0q0k0E0|0j0N0s0E0m050Q0_0{0}0 0@0z041n1u051x0Q1x1z1u0@0T0r0K0%0)0+0-0D0r0t0D0C1N0D0d0=050Y0R0C0E1I0*0,011M1O1Q1O0d1W1Y1U0d0R0p0T0 1V0j1v0d0D0%120m0z0n0B0-0h011!1K010e0!0E0B1a0E1U1 21261$291Y2c0v2e040a0q0y0j0p0z0p0m0r15170W1}0j0j0E0G2z1n2g0B1v0Q1{2L0d1_1^1`0T2i0-1Q0B2b2w1U1F1H0(1#2V0r2X0B1=1G1U0z2E1v2J2L2?0^20172%272,0j0|0C0=0w2I2`0?2_2h2|1$2~300=0h3421362J2U013b0n31040l3f2K0@3i390-3l3n0f3q3h2`3j3w0=0b3z1w2;1n2#2O0T2S3j0G1=2o0V1G1v2:0E2=353G3P0W3X381J1$0U0=0W0e3G3t3(0-0M0=0q3.3B3u3k0e0=0v2*0r0v0`0S0n0R0j3^3%2(010;040L472{3:3k0=0}450E4e3j4b0g0J3z060q4t3@3/493*040r3-1o354v3_4g0B4i0j4k4m3`4b0c4L4g3~0=0u4P494b0x3z4E48270p3=4z1m4C3g4Z4f4x0G0=0A164l4*2K374-274b4q4@0?4u504,3j4y2E0d0s0j0B4Y4_3C4I4K4~5b4M0=4O5f4w274R04335k4F4V0=4X4~4s4u5g4g4y0E0#4?2^5l1$4|4r515x5F0-540X57594~523`4H043~0B404244465q4!5G0=4d5$4`3a5d2E4U4{5i5:1$5n4T5+4n5t0g4r1n3!3W3H610Q3K1n0d3M662Q2M1;1?2O441Y2L3K1t3$5,0-2E0v0S0e0n0U0E0S0D0l0=1f1h1j1l0q4}2^1A361u0i0C0q1l0d0q2v0+0r1X1Z2B0j0H3m0r0m0E0j0q0s2X0q0K6Z2x160q2y0H0j0n0/6)0q2B0)0q0e162G0r6,0J0@6F3S2$4g1(1P1R1T6k3j2k2b2d0=2q0P0G0j0:6M0y0I1{163G3V6k2@3Y607a3`4y3,5?3;3?7A3{3}3 416o5!7D4b5*5E5r2}5.5D3Y5L4a0=4p5I5K7O3)0=0M1M1Y5a7T5U4j5/5`5h045j7N5%0-5^7K5t7)7Z0-0p0=0o0F7{7?010U4/044;2X7_046D355w5J5y497+4J7-2?5S4g7~04815R8g7P047,7R3g8s5(7:7D7^7.4g4W7X4t8y5M0=555P826l4h8u8j8w4^7T4N8B0r328a5u2?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

.1280135[4)2FR,Ba- iV8m16l7.e:9A;US/dktfrjT3sogu0x]PpNnh=cLéyvê(wq_b050E0w0G0k0n0t0M0m0Z0t0k0M0M0Y010G0n0U010406050M0P0q0q0k0I0$040C0N0t0P110N0W0m020k0q0U0A0m0h0w1b0I0+0P0w0M050D181a1c1e160U041C1J051M0D1M1O1J160E0n0%0_0{0}0 0X0n0O0X0t1$0X0G14050;0-0t0w1X0|0~011#1%1)1%0G1/1;1-0G0-0N0E1e1.0I1K0G0X0_1h0M0U0k0W0 0f011?1Z010H0?0w0W1p0w1-2e2g2l1^2o1;2r0q2t040a0m0T0I0N0U0N0M0n1k1m0/2c0I0I0w0Z2O1C2v0W1K0D2a2!0G2827290E2x0 1)0W2q2L1-1U1W0`1@2.0n2:0W241V1-0U2T1K2Y2!35172f1m2_2m2~0I1b0t140r2X3915382w3b1^3d3f140f3j2g3l2Y2-013q0k3g040L3u2Z163x3o0 3A3C0d3F3w393y3L140b3O3H3Q3J3z0N3e3B140s3V3m3a1Y3p3!3r040u3)3I3,3K3.3$040p3=3X3@3Z3#3C0y3O1L331C2@2%0E2+3y0Z242D0.1V1K320w343k444d0/4l3n3 0F140/0H443?2`010*140m4x3~4z0W0H141A0G0,0k0-0I4E4r4z13040)4Q3+4G141c4O0w4W3y4T0e0x3V0m4-4D4y2m4t040n4w1D3k4/4F3c4Z0I4#3O4{4R2m0N4B4?1B4_3v524X4;0Z140V1l4$592Z3*4(144+5j154.5r5b3y4=2T0G0P0I0W515l3Y0F5e040K0I1z4,4.5C4s4J1)4^355t3Y55142~0G5B4:3p4~505p5M4S140c4%3Y0q0n140Q5,3 4T0S5Y4|1^5U575_531^5E5f5h5~5c5{562g0E643R5#2T5=5)045+5%5Z0 5.3h6e2m5@6a5T14020t0G0A0Y6q3 0W141b0R0n0q194M4O6n1^4T4V6i5`3K6c5i376j014T6h6S6O016l045;6N5 0 5@4*5K5s5S5N045w5y5A5p6.4z61040g3B0M6R3k065r5(4;5O4@6y4z5|5W774}044!6d6%656)5*6J6k5/043t7g5m045^6@7366140n585R7u0 6`5g2:7b7v7d0W697t6T6A7d4 7f6X6(6U7j7p5-7m3i7U5?147s7z6T0N6s0O6v6x7K6Y7M5.0W6E6G4N4P7Y6f6M7Q7h3z6Q7k7S6g806!7o7|7q0S6+5p716-6^746:0:6=7F7B5F6|0@6 3v8b4-7A014=0w8m804T5o358p5s8r5v8g5z8i7~044K6H7^863Y6L807M7e8n5k6T6V837m6$8M7Z7r0e8G5|688G7M8J7@8w147{4m7L7 7_6o7T8Z4z848.8#3)0D4o4k45920D481C0G4a972)2#23252%4N1;2!481I4q7}2T0q0,0H0k0F0w0,0X0L141u1w1y1A0m8y4m1P3l1J0!0k0m0M1h1j0n1l0m322J2L0#1=0n0Z0n0m0W004K9Q0|0m2J113f1=0Z1c0m0?0m9$0W0#0Z1A0M0=2T0m2Q2f0I4d5y0n0I9Q1i2M0w5y0^0H0N7x0m0t008R9C9)1ma0a20I0Gaf9B4O2g0Z0X9B7:6E3B1=0:0m6Cay1;9~9-0X0k9A9K0N0P0M0lai2K5y0m0%0#0I4@0n0wa50M000?0^9L0Wap0/0^0z0j0h0i0_1=1y9Y6E0U1)aKaKag9P0%9J2f0}aZa6aNaYaa0macae18a51;0^0q0(2C0^2~a90E0M0Db01;aa0v1L9G040!9#0RaZ9X9_4D9J0X2T0H0 0v0v0DbI0D2q0,2(0kb00P0RboaZaX9.2O0,a.0h0,0f0D140oaVbW0k2O9~000B0V0mb!0m0)0f8$0D0k049QaZ2Ca+ah0t1;a5a`aNafad1mbcaq9K0P0J0:a;2q9:1q2L2gap0JaN0G1v2qa+1=bp0n0/a5a,b?a/0mbQ2U9~aM1:1l0Mci1m9N1)9{a*0m0P2:aC0#2a4e9)0U9+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