Aller au contenu

Test d'arbre binaire de recherche

La notion d'arbre binaire de recherche ne concerne que les arbres binaires dont les étiquettes sont comparables, par exemple toutes numériques, ou toutes des chaines de caractères.

Définition avec doublons à droite

Un arbre binaire de recherche est tel que, pour tout nœud, on a

  • son étiquette est strictement supérieure à toute valeur du sous-arbre à gauche,
  • son étiquette est inférieure ou égale à toute valeur du sous-arbre à droite.

Exemple d'ABR

graph TB
    A("8")
    B("3")
    C("15")
    D("2")
    E((" "))
    F("12")
    G("23")
    H((" "))
    I((" "))
    J((" "))
    K((" "))
    L((" "))
    M((" "))
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
    D --> H
    D --> I
    F --> J
    F --> K
    G --> L
    G --> M

Contre-exemple

graph TB
    A("8")
    B("3")
    C("15")
    D("2")
    E((" "))
    F("8")
    G("23")
    H((" "))
    I((" "))
    J((" "))
    K((" "))
    L((" "))
    M((" "))
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
    D --> H
    D --> I
    F --> J
    F --> K
    G --> L
    G --> M

Propriété récursive

Un arbre binaire de recherche est tel que

  • ou bien c'est un arbre binaire vide,
  • ou bien les trois points sont vérifiés.
    1. Sa racine porte une étiquette strictement supérieure à toute valeur du sous-arbre à gauche.
    2. Sa racine porte une étiquette inférieure ou égale à toute valeur du sous-arbre à droite.
    3. Les deux sous-arbres sont eux-même des arbres binaires de recherche.

Exercice

Coder une fonction est_ABR qui prend en paramètre ab un arbre binaire représenté à l'aide de la classe Noeud et qui renvoie un booléen :

  • True si ab est un Arbre Binaire de Recherche (ABR),
  • False sinon.

⚠ ab est défini comme dans la section précédente, à l'aide de la classe Noeud. Il n'y a pas de classe ABR dans cet exercice. ⚠

👍 On garantit que les étiquettes sont dans l'intervalle \([-10^9\;;\;+10^9[\).

###(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 : ∞/∞
.128013x/.Tr;nbOylae«u)*dV63Am(P+02è-,59fq»7B8 N_o=pcwgv4F1kRéhtsSji:050s0n0)0m0-0l0*0O0U0l0m0*0*0S010)0-0T010406050*0p0x0x0m0f0k040+0R0l0p120R0h0O020m0x0T0g0O0$0n1c0f0J0p0n0*050c191b1d1f170T04051K1D1N0c1K170s0-0X0`0|0~100(0-0W0(0l1#0(0)15050=0i0l0n1W0}0 011!1$1(1$0)1.1:1,0)0f1L0)0(1=1Y010I0@0n0h1q0n010`1i0*0T0m0h100C1,2i2k261@291:2c0x2e040a0O0z0f0R0T0R0*0-1l1n0:2g0f0f0n0U2I1D2p0h1L0c242U2123221-0s2r101(0h2b2F1,1T1V0{1?2(0-2*0h0R2.1,0T2N1L2S2U2 182j1n2:272^0f1c0l150O0!2R3316322q351@37393b0C3e2k3g2S2%013l0m3a040O0v3p2T173s3j103v3x0O0Y3B3r333t3H3b0G3L3D3N3F3u0R383w3b0u3S3h341X3k3X3m3y0L3$3E3)3G3+3Z3y0N3/3U3;3W3Y3I0H3`3i3|3P040!0B413(2;3}3,0!3d1E3f3T424a440!3o4f3q4h49363?3x0!3A4n3C3%3O4s150!3K4w3M4i4r3~4B3R4E1O2}1D2.2X0s232$3V0U2_2x0/1U1L2|0n2~3f3L054V0:4%4G1@0#150:0I4)3:4a0V3b4@3{4j0I151B0)0Q0w0M0$4|4.1014040y574q3k150m0i5d3t5a0q0.3S0O5p0O4y3V0*2n04011v0h0X0R0-1;0e0f1A0O2G0O5h0O510O0p1n540$0F0O0Z3w0*1;2G2^0h0d013S065q5r4^274:044=5j3V4`3y5:434 04510Q0X3w0-0:5@4a5a5c4L5+5f045h61275a0F3L5*4}36150x2?0-6a1@6c6e5s436i0m0b6l656g6n155m483t5=5)5)6m100*0s15016L0t0%0f0-295X0-0O6j0h6T020l0)0g0S5J0i0Q2b6)0h120n0f1o6Z1t1c6u6B5t6J3y6E5p0;5H6T5K5M5O6%6/5}1(604E4p3t6I3b6|0O6L5$795(7e6q4a5-2N0)0p0f0h6p663G5g5i4E6f58010R5=0-1C7y7l5,0U150P1m0n7t6x107C153X7O7A635o7e7Y7H6y5b6G3u6i6k7U5e7Q156Y6!0S7+3O7w7%0R150d7%0h15760n7q7=3V7_047/0g826r046?6v317u015l7X7Y5p7!7Q5=2k0s884j500*52765 7N6w7V15648d7P7(687x8B7A847{8x7,8D0W0m0p0U0(8w8G8L6o7G8e7}8a7*8K5k156d8W8C8Y698#837`7|7~3w800f7%8g798i5q8k7B8m0h8o8)7A8Y5{8u788T8$7$8-898,988.048J9e890s2C2H8S4(8e8V2 7z8L8+8F9o8C8I8:047 819b628%8p6h8a6t8c9w8y040q8h6E8}8_2 067j8j8e7n0;7q7s929t8r8t5~979L8U8z9z9d9,998(9r8}840E7%6j4B479D27840r0r9{0-15409 7#9?3f9s3t9|459~9i4aa1a3a810aea7ah6b6z3$0c4+4$4Mav0c4P1D0)4RaA2!2V5h1:2U4P1J4-8L2N0x0Q0I0m0#0n0Q0(0v151v1x1z1B0O5n4L1Q3g2.3t0m0s0x1m2H0-1m0O2?0I841Ja,a.a:2I0E120)1 040t6.2Ga?0m0X2O0O0i3X2*0_a^6k1B1O3g1K0+6T0l000w0$0M5L8s0O0h1a6O0-a!5S1c7E0O1z00a?2*2g0h2c2H0O2j0_1:0_bd7ra#6k128=0*5Sa?0T800)5N121(5W6/4*4W04a^1Dau3y0s0p6U2_0p1:5rb?1c24b=b/bF0p6T721n0I0l0R1}2kb(2N2|0%5W6,cd0Obpbh6W8J1R4Y2/3|1_1%1)1+aL3t2t2b2d152z0+0U6P0Tb(0z0k241m4)4#aL304(b?8}5-5/al016D7|5_5{5Q8^9.cX9uc(9N9G1@9_020W6!c.3G0i15bd1ic,a%9T6F8e5u6K5y5A5C0O5E5G5I71bv735Q5S5U0^6S5Z5#9PcU8Y0-1r3X0)7%cZc*8Yc00(5%d08CcV0n4?cXdtap3kc#8s5|9*9n3q9Rc)dG7v8Ec,aa3qac3Vdv8!dQ8f9F9$7?9I6@cX9Sab9^150Ec;c?d%dXc_04c{0lc}6^3|6D7kcX7c5w6Mbz6R6 6U6k6:6!6%6+6+6-6/866$8bd}4ae27Y6~da0ibub(735h75dL7gdy7k9X157o9!c@8D9:dV9^7D7F9@9X7J047L2*eE7R047Td?3|7W8`8{9Q9pdP9;dX7)6WeR7.6;eEc+cX9yc*8;1:9CeL9xe,7:e.6sd*d!d,4oeZdW3|eS8ne}5`dJ96dM2TdO9ad!e/d!e;fg158N8P8RdTf86V9KdNe#04dU2Tf48qdSe:8/e=9A8=e^e%eWareY8{eI5g90f895dLc,8AfHfzeGfd8efjfU9H9k5B0)fccy3V9qd-8X7@fB9g9z9B8@d+d$e_93e~fsfX8Cf13C7Zfu9O7idz7A9Y7p7rfPfafRf^fff!67fWf*fIfve+049`fDdw7^fCfkb:0hdDf0f_f-e`040A9zgqf:9hggdRb;geg49Tc24,awaI4Z17aygRcra|a/6W2Ia@gva`1MgWa~a=0hb02Hb3b50fb71n0(3X0_bx0xbza!bkaKbnclbq55erbK8s2H0p0%0O2K8Q0?bfh91;0U1d0m2P0D2N0_0y0Rb_0s008O21a#0R0i0,0;0_4V1rhh1/a#2bht5L0p0b0q5S6~bGbI1;1T2i2F1;bPhebSbea#051w68bO6P3X6vh!b!1nb$1kb)0@7E6.b~b/eP8wb?bOho6/2?1Ta!6/0.0O0o5H2kbQdo9m0O0K0d0O0j1n0m5Jcag:clhf4WbO1jhz0R1r1:0b5Xc55}6,a$g}gV3Vcu1{1*2o8CcA2v2xcEcG13cJcLg?9#31cP3%cRdNcTeA5.dCds4{c*dI52c%gefTft8*f/gxgleVfzfrgr047;cX0#eNh^fpi;9Hejf:i_d!i{7K7Mc,gLgz8Hd/d;87i 3kd^d`d|798}d 8je16`exjkd16`5)d45B5D5F6S6%h3dd55df5Vdi1mgG4o8}em5q6N6Pe65Ifrea1t5hedhF5Ceg6;ei9J5Lb(euek27jL6|h^6 0W6WjPi6cli8f(j)1@j+7f6LdliXeCgajfdRgifya0eJeEj5eOj7k28~7Sf@f`9-gff2eZfe0yi+f~f{8Ze*kceS7Ek8i|kbi/j9eHfY5=eUkg99kngji=dZja8L8486f8gid.f;fDf?j8kzg1ez9x8 91kEf+8zkG8}dv9JeRk7kck9i}gKk,keeEeXgtkPfYgsgH8DkTkse{6#fqk+gKkV16g2kYfNk!kKd(c$55fS9/9vi,jbkRgtfm8Qf)fefw5?f.kqf}kHaqi:k#9clikokLk|lj9%fEe@kfk}g03y9Ve!l968fOkc94dJi)i/k(ltk`gAjIlCd(f$9mi~lzfVlBlwc/lEl$e(lH8?l*lcl=j1kyj~f fJgMatb/gP4OgUgT0X3gay0;0?0^04.