Aller au contenu

Rappel : 🎯 la classe ABR

On utilisera une classe ABR minimaliste pour commencer.

Mutable ou immuable

Pour cette section (Arbre Binaire de Recherche), on fait le choix d'une structure clairement mutable, à dessein.

Un arbre binaire de recherche est une structure de données qui est faite pour vivre, évoluer.

On pourra souvent construire un abr en partant d'un arbre binaire vide et le peupler.

Dans les exercices, on considèrera que ses éléments sont, eux, immuables.

Méthodes classiques

Saurez-vous écrire très rapidement les méthodes suivantes pour la classe ABR ?

  • est_feuille qui renvoie un booléen, True si les deux sous-arbres existent et sont vides, False sinon.
  • taille qui renvoie un entier, le nombre de nœuds.
  • hauteur qui renvoie un entier, ⚠ avec 0 pour l'arbre vide.
  • est_présent qui renvoie un booléen, témoin de la présence d'un élément dans l'arbre.

👍 Dans cette classe, les doublons sont insérés à droite, c'est une bonne idée.

👍 Dans la plupart des exercices, il n'y aura pas de doublon.

⚠ Vérifier toujours le cadre de votre exercice.

###(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 : /
.339.128013x/.ùTr;nbOylaeêu)d63Am(P+02è-,59fq7B8 N_o=pcwgv4F1kRIéhtsSàCi:050t0p0)0o0.0n0*0N0T0n0o0*0*0R010)0.0S010406050*0r0x0x0o0h0m040+0Q0n0r130Q0j050d1a1c1e1g180S04051w1p1z0d1w180t0.0W0{0}0 110(0.0V0(0n1N0(0)16050?0k0n0p1I0~10011M1O1Q1O0)1W1Y1U0)0h1x0)0(1!1K010I0^0p0j0o0x0p010{1j0*0S0o0j110C1U25271^1$1{1Y1~20160b0N0z0h0Q0S0Q0*0.1m0j0N0;230h0h0p0T2u1p2c0j1x0d1?2H1:1=1;1V0t2e111Q0j1}2r1U1F1H0|1#2R0.2T0j0Q2X1U0S2A1x2F2H2/19262v2Z1_2(0h1d0n160N0Z2E2?172=2d2^1$2`2|2~0C3127332F2Q01380o2}040N0v3c2G183f36113i3k0N0X3o3e2?3g3u2~0G3y3q3A3s3h0Q2{3j2~0u3F342@1J373K393l0K3P3r3S3t3U3M3l0M3Y3H3!3J3L3v0H3*353,3C040Z0B3;3R2!3-3V0Z301q323G3=3}3@0Z3b423d443|2_3$3k0Z3n4a3p3Q3B4f160Z3x4j3z454e3.4o3E4r4c4m4v3^3O4y4l3I473X4E3Z464n3^3)4J3+4L4B0Z3:4P4t3T4B0C3`4V4d4X3V0C412/4z4G4M0C494+4F3?4.4i4;4K4u4(4q4_4Q4{3%0C4x4~4W3#4Y4D544$564(4I594A4(4O5e4-4Y4U5i4?4B0v4!5m4R3V0v4*434=5s3%0v4:5w4`4%5z4^5C4 5E3k0v4}5H553~5z535N5a5P5K585S5f5z5d5X5j5t5h5#5n5t5l5)5y3k0X5q5-505/5v4b5x5?160X5B5_5D5b3%0X5G5 5I615/5M655O3@0X5R6a5T6c5W6f5Y5/5!6j5$625(6n5*625,6r5.160G5;6v5{040G5^4k605U6x5~6F666H6C646K6b4M0G696P6g6R6e6U6k6x6i6Y6o3k0G6m6$6s6(6q6+6w6C6u6/6B0u6z6?5J160u6E4s6V4B0u6J6 6Z040u6O746%6|6T796,6|6X7d6:0u6#7h6@6*7l6{766.7o676|6=7s6M0K6_2H2,0p2H2X2K0t1=2P3I0T2)211x7E1y2-3Q2:32057K0;2.6L0!16363y5`1$0U2~7$6G0j0T160w0L0#7+6L15040/3{3g7)3l0N7 7?5O0*0t1601867{3I832~7 0N0-3S1Z7:0#0N0Q0f0N2q0r0h0{0(0o0J0r1Z0j0a0r0t883,8a7~7 0E0N0n000%138t0=0)1Z0t000r2v8w8y0N2T8m0~0N0q1:1Z0O1n0p8A3}8C8c0N8F1Y0`0%0n0%200j0)0`0,0N0V0o0r0T0(1Z0*1n0)0N020n0)0i0N8|0T0p1k0.2w0r8V8x8z4#3g8,8c8/0p8;8?8^8`9c2w2o2t9395970V9a0R9x9e9g9i9k8y3F4,8B848D0N0y0W3j0p8o0N0.0`8%8W0/2w0%2s0V8W8R0N8h0N0W0.0;0F9Y0n8V000o8X0`2x8T0t0s9N7%119p7 0$0T0.9@2$0*0D2A0N2A0j0W0Q0.8$8(8*1_a60N86019N8-a4017Z040;0I815T7}0NaC3g0I0x160P0P2$2taLaG3I7^0yaQ3,0k7^0*9faB4raw7^a24raF6G0Q160E029E0i3ya*7Y7.049#8)a#6G7^7`4y8-av6GaW16aY0na!2;a+160eaU46169U1Y8oa=awa,040Rbj6G0!a^a`3Fb18cawb404b6b87Tba04bca|6L0j168~9092bo6Lblbna)awbq16bsb0bua?5Obxbzbd1_blbEb9bG160t9z8NbM5ObOb/5TbSa_an4y06b27Yb+0pbA3dawaEb#370I169s0)0P9;0;c411aScd01bZaZcga%b=3gbla.a:cm4G0k160k0Q1jck16a 4+bWbXb?162A0)8o1obQb3aXcjbFb:bbcgbH04bg9W0hcr3,0Q7}9ZcX3}b@bU4+b{bvbpb~c02Gc27*cO6gc6041}0h0oa92Tcy04aTc?3gcib7c 0Fc$2_160cc a(2/cDcna-a/9ad81$c(b_b)5Oa~ao7(8bbucg8Casdra59QcC0-0h0%1Z0Q9j2A0x0S0}9e8G8v9l0Nc|cH9fdy01aq8-8 c{8G9|cU9Xdb9n89dAbW0=2w9W0c0N940r0*0E1e0k2A0`cb9sdUdW8cdxbVducLb5cNdo5Tb%cRbf9VbicKbN16bPdeawcSd(cBbWbwcMd5d23Ieaes3?bI8 91a{ejbCei32df4G7/7;c 0ydd43cCepe6ere8dgbDebazb-eAeEbkehdk3teH7=ev3}aSeL4bc+80c-azb cgc3e)2_c^acaeeXc1a}16d1eR3Id4c/7Xdp16d7ef6bdadce#01codia;fab?brdnbB7@czbteo6G0*2a04010l2ve{2A9@2s0N0k9sak2v0tdG1X1n9xb,ak8Nate3b1bR160.f5eFaVeqf5eZeTe^37c70*c9d}eJ0scAeMcCc,6Lf4cgeuf2ewc_0jc{c}e}c:e d0eUemfnf704e,3peNe:9ffVfeelfebl98djfjd3fZf^cQf%e$cTedcWgq01dqfRgbf?gngvf_g66gexbKg0f6e9gpf`be04fzgIa$f0g4fdgyf=5OaygdfWekfcglet16fhfef@gCgLgE3BecbhgugM1_gxenf;fX3}g,g@1$gDe~b*eVfOgQbCb(g/eGgO0jad2AeJgTgvclgVe/b}c_0_h6fo7_fqg{aw0T0Z16038d8Y8P0%8~1Q0)0%9@fLgPfMeWhrf;eObye7h9cYg.h2fbh49Agof$g grgPhfgvgghh16g917e.g|1_ayaAe?c=hZ3hc^c80P0I9W0^1Yh$h@g~hQe*h*ghdhcqg%3?ct04cvcxh)hqhjh.dlfUg!e5hOeQi3b$hSg1h3h`f,ifeKf/4bg{hkgXcF0=cIfeb@0Y3jaYhLb|iChmiKifiygaiAfT04cGiFi9g}gBh@h1ishUbJezhXh8hTgFc_f*ca9=hog7eKgh7}279meBgAePf!h7eUfNhWg-hYipf(i/f+i=f-augWcEe;j06Le@h@0jc^0?h~i?5Tcfgvi2i-3ghii}cP04cpgkjx6gib2$0)c iR17gziNgeiY1_jti%gKj6juhaiujbiwf.iLfrhliW0hcJjC3g0x0.167zh-iMjf9fiPh@g_f:hse:j$j(eY6Gj+4oi6040Ag+i!j711i$gJg:04i)bLj5i,jQkbjn0nh jXk2k4jN1$jPkag(jSkhhaj3b.kfeUkjklj@f0h+06h-iUh;gvjjk7h^168r1lcVi0kMkrgRg8k2jAfij)csfU8_jHjZiBjfjMk!fYi i+eUjVccjXjIj/j!iNj|fek004j.jKj;hnk(ihj:3gayk|kp11k~6~iik816kok-46ib1dg5jT3,jri1k6ln3}k9g#kceykei#irksf{kP8NeekDd00sf9lijOlrkvhRkulBgNkxjpeSkglQd904lDkRjXkFkHe:kJh@kLlse_f)c92,9)1}jGiwcgkUg2lJj~h3lmlNi4kWlaffi7jBl|6bibid0nl4g`fSe:k,m65Tl_eglPlvk=lTaRkEk^iAleaxiDcHj%iGa^iIl3ihiUgZgfg$lKh0g)99kZmggmk/kzh%g;l!lGmqiTj{iEmwm2mijylVlvkdmnlOm#7,l.0Pl:aYk%l@mP04l~lW1$jwj_mdhlmDm2h(mGlf04g*mYlMm^n2m*h3d$g?kMj^izmUj#mWj}3dmsmZjRn9hUlSk:m=h`m.l=kSl,j8m@kVkFl1l7c7mAmSk)m|5Ohuhw0{hz8IhC2t0%nHl63Il8nimx160g0h8u3P0d7V7C1A7Q0d7O2I7G1p2Ln:0o1Xn)n,1G33n,0=0@0_04.