Aller au contenu

Arbre binaire équilibré

Définition récursive

Un arbre binaire est dit équilibré,

  • s'il est vide,
  • ou bien si
    • son sous-arbre à gauche et son sous-arbre à droite ont une différence de hauteur de \(-1\), \(0\) ou \(1\),
    • et ces deux sous-arbres sont tous les deux équilibrés.

Un arbre équilibré

graph TB
    A("1")
    B("2")
    C("3")
    D("4")
    E((" "))
    F("5")
    G("6")
    H((" "))
    I((" "))
    J((" "))
    K((" "))
    L("7")
    M((" "))
    N((" "))
    O((" "))
    A --> B
    A --> C
    B --> D
    B --> E
    D --> H
    D --> I
    C --> F
    C --> G
    F --> J
    F --> K
    G --> L
    G --> M
    L --> N
    L --> O

Les nil et les feuilles depuis 7, 5 et 4 sont clairement des arbres équilibrés.

Depuis 6 ou 2, les sous-arbres sont équilibrés et de hauteurs 1 et 0, ces arbres sont équilibrés.

Depuis 3, les sous-arbres sont équilibrés et de hauteurs 1 et 2, cet arbre est équilibré.

Depuis 1, les sous-arbres sont équilibrés et de hauteurs 2 et 3, cet arbre est équilibré.

⚠ Si on supprime le nœud 5, l'arbre n'est pas équilibré !

Exercice

Coder une fonction est_équilibré qui prend ab un arbre binaire (représenté à l'aide de la classe Noeud) et qui renvoie un booléen

  • True si l'arbre ab est équilibré,
  • False sinon.
###(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 : /
.9888.128013.128165x/.Tr;nbylaeu)dVM63Am(P+02è-@,59fq78 N_o=pcwgv4F1kRIéhtsSàLCji:050r0o0)0n0:0m0*0N0T0m0n0*0*0R010)0:0S010406050*0p0x0x0n0h0l040+0Q0m0p150Q0j0N020n0x0S0i0N0#0o1f0h0K0p0o0*050e1c1e1g1i1a0S04051N1G1Q0e1N1a0r0:0W0}0 11130(0:0V0(0m1(0(0)18050^0k0m0o1Z1012011%1)1+1)0)1;1?1/0)0h1O0)0(1^1#010J0`0o0j1t0o010}1l0*0S0n0j130C1/2l2n291`2c1?2f0x2h040b0N0z0h0Q0S0Q0*0:1o1q0?2j0h0h0o0T2L1G2s0j1O0e272X2426251:0r2u131+0j2e2I1/1W1Y0~1_2+0:2-0j0Q2;1/0S2Q1O2V2X321b2m1q2?2a2{0h1f0m180N0Z2U3619352t381`3a3c3e0C3h2n3j2V2*013o0n3d040N0v3s2W1a3v3m133y3A0N0X3E3u363w3K3e0H3O3G3Q3I3x0Q3b3z3e0u3V3k371!3n3!3p3B0L3)3H3,3J3.3$3B0M3=3X3@3Z3#3L0I3}3l3 3S040Z0B443+2@403/0Z3g1H3i3W454d470Z3r4i3t4k4c393_3A0Z3D4q3F3*3R4v180Z3N4z3P4l4u414E3U4H4s4C4L483(4O4B3Y4n3;4U3?4m4D483|4H1R301G2;2!0r262)3Y0T2|2A0=1X1O2 0o313i3O054?0?4~4J1`0!180?0J504!2a0U3e5b3~4m0J181E0)0P0%1C0`0:0k0h0%5g551317040y5v4t3n180n0k5B3w5y0q0;3V0N5N0N4V3 0*2q04011y0j0W0Q0:1@0p1q0k0Q1l0%2e0G0N0g0h1D0N2J0N5F0N5l0N5o0p5q5s0%5-0Y3z0*1@2J2{0j013V065O5P5c1`0T0Z18030N0.0@0)1@0J1p2S0:1p5_0*0)0N0r0%2c0j5!0N0,0N0m002_0)0%0h5!0p0h6x1@6G0n1n2Q5M5O5Q4d5704595H3Y5e3B6$465j045l5n5p1+5 0P6S0d6*4d5y5A4)6e3J5E5G6}5h2a5J5L4O6c6c6X2a5S185V2e5Y6C5t0T6N2J0W1z2e6w5$0N5(5*2e0N0y5|5~2Q0q5_6w0 0N0(6S6n6N6P5@0k6977785N7a56180:5a4H6d735D045F3O7W5w010Q6(0:1F7V7Q130!0T180O1p0o6_741876326b7O787.016Z2Q0)6N0j7#816{7_567;045/1D8b5x180G886~010x0:184a727%5J6V7O816Z0o0{7^8s5C8i047|4j7 808m686-0K0P0V8h015y8k7-8K180(8O8l7X130Q180R8Z7%8L6.7x6;5t6?0p6^8C5I186|348V7Z718`8!7(180f8Q8L0V6S0T0(8B8~8t180q8v8I7$8D3x5k8N0r8Q8S8)9h8L8X9l8U8 8$048(9t8*5k6v6/5}8.0%8:8=9a9h8a8?4W708Q9v929L46582F2K994 8m8u7N9f9g3R9j9o3w9v9x329$9M8M8Y9y9h7)5E0j9s9-818+9k9)3Y9@7Z9_9 3 9K9I3R7L8|7,a73Ya69X8 9q9;9{8m9v0Ea44m8W0P9`af9b049d9=9*18020m0)0i9,3i9.3 8o4E9m9c9e8I9|8Wan2a9+aP1`aH48aS8#180AaW3xa91f9Has9J8^93ap8P9R6`8ja!ahar3t89aK9!9f8x188486a!aea^8{0o0KaJ048TajagaOa/7`au6a798m6g6i1x0@0Q7I6E7D6p0j6r6t2 2_0T163z9W4rbhbb8Mb7b9aEaN040(a!aRaw9/8,6:5r8/6@b78_a)9%8|b7av7}bC7%830@b0bN9SbE7VaF4dbj046j1?7r5)0m5+874U0e524}4*c00e4-1G0)4/c52%2Y5F1?2X4-1M549h2Q0x0P0J0n0!0o0P0(0v181y1A1C1E0N8Ga^1T3j0?0^0`0|3Y0r2n0V0o0h183G1d1A1i050:0x0V5@aA130c2i3Y0)0U1z0Q0/8p5=0h0T1$200S0*0;0eb~0r0j0f0/0*0?1+0W0h0f2-0)0e1)0e0/0?0Tcn0r2Yc$0xc(0:0F0Z0H0f0Z0f0B0e1_0@0*1H0W0V0e0Z0J0X0ndj0*dt2i150)1?130;7s0x0;010e3B0w7m0T5Pb 04670m0Q0T3z1GdT5PcScU3z0)cXcZ3 c#c%c)2i0*c,c.0)c:c=c@c_c{c}1Xd0d2d40(d6d8dadcd/dgdidkdmdo11dqdsdudwdydAdC0NdEdG01dI5)dKdM33cO1K3j1Qd%cVd*010ad,4dd.ded:c+c-1{c/c;c?0Tc^c`c|8zd d10@e2e42Re6eGdfdhdjdldndp0)drdBdu0C0u0n0B0fe.dD2Keo0;0U1g6B0j0VdLdN0N0-001n5q0*0n2L7J514@dU1pdWdY0md!fe6u6w240D0|6p0h6n2z0j6w6y4?0j640`b`1@7u0O0+0$0N1wf90p0J6D5=0n7g6O2m0hcl9Vfu7C000o0d0S1+cvd06kfY6v0N5$1@6n976Bcv0N2 0Q0J1E2J1p2-0mb@2Q4?1J9_5+6x2ncFcKcDfz0}109Q1U4_2=3 1|1*1,1.cg3w2w2e2g182C0+0T6L0S6w0z0l271p504|cg334 dTa}6!0o7Uac3 6(5Pbd3n6,bP9DbR5ugQ8EbVb3bD7!gX8R9ccy3Fb$9h7c5U5W7g5#5%b_b{5-8f650:7Kfm5{bQ5 6163g{677Mb#6W8{2Q1caAfabL8%a!7:18g`bgh88 b;6j6l206o6qfb5`6y6A6Cbp6Hfv6K6M6O2N6R6TbAg+hlb%58gK8QgO936,7F1n0o6NbUa,bYg%754b3wgO7 8Qc|7d017e5X5Z1@7i7k1X7nfv6F0n7E7GhThD1@g$7}81h)3B7 de1W2c1@dVdX3z0N5thb0^6w5?5^0jf*6w2m0|8-gVh!3Yi28Ih+h68Hh%8m6Zi9fia=a~0%iehda{g,3w6Z7TiChXba7%a17+hg8d7?2-b7g*199#7Piya~b)0hb|iO9haU8rh78wi#6-8AiWaLixbD8Xa.i*ax9wiMhR7H0hhVg%8Lh bWa091hW950p97hHgmada`i.a|8{9rhei~b+aobJh{hUhYa+j49Ng%9PhW0r9U6nbZi@i/8 iKgLbH8Ka95Fabj7a5jugMjpi`jmamjo39apa@2Wa_bfjW1`9v020VaBa!aU4hjRbeiX7~iZhJ9piDiF0)jmaD3tb/2ahh0462i=iHi^hK04a i(j-8paVj%aX04aZkfa#18a%j3j:7YjTjtb8i aqjD4O06j?k06f6hb=bl0)bn6Obph_brbt1qbvbsby1?9ebIbKkjbMi|9/j0h|knjOjpj6g!atb!iwi!jGi$85kbkj8Lid0phcj|b.81hn5=hT0m6F1@7sfC1q2{0p0|6I6Kf`1@0:bx3)b~fec1cd4`1V0@0_0{3wcHf0cKcM1bev1h040scKf{1qgK2cdY0T99lt1Lgf3wgi1~1-2r8 go2y2Agsgu16gxgz0(gB4)gD3*gFa^gHi:6#g%hOj4gS9Bio5 kZk%j_iNk!be5KkQ8mg.h,g;f,g?7t0jg_5:g{g}5`l/5th28A5=2_1pivbBj^bXk=k@j}iShim5hkk+7%k{hp6n0NkJhtf+hv2_hx6Fhz6J6Lh|7JhF24jekygIl)ko13l+mP3xhQjrj2krgZj!8{k$mZ8 hZ4Z8 h$8wg%i2iug:h.ic0%7j0h7lh?7Ch_kX7I2Nm#4Ig-0r3ei42|7T6CiAibmkifmdg}ij5`img gUl:m)7%is7 iujEkz7/18n9fjk:j`k?ifnqgIiLnwl@j 81iQjNnFiyiT7@i?k6jFk8kai)jJ8 i,nAi:8z64nNjiaMi:nCkVb,nbiGmS5yj=j@iIkWainTiPhfnDm}mWn-jQl^7Yn0nGj9jv04jbjdkvn#k79h8yk5n}8Fnqn$k,k9i%nSnJjGnLiVkwj@nBjIom9zk9iEnyn,n 8En/n:mrl?jlkTn_n)jSmVl;m$ovo1ako3mS8LjA5ZjCkrk)mh9#gInYjej#oCoDgInRmn04iUmLkyohk8n(n@l?n+k^oeo)n:osa=jL0knIoNa*5zhWkqoJaQ18jVp9kpkuoXjmj*j,kjj.n!k*oDmi9/o`mmkjk2k4nZnOo~i:o,ptoomLornXodoAg(ofpxo=obk-b*pd7/pCmqjjoipApP8nkdj/o^i}kipW0ja$0na(l=8@p6o4p8pH9nn`pfoeoY3Fkxn;3 k{1ykEboh^mwhs6skL6LkN2mkPa{kRpsp%8WoLmXhWoPm%jhpno+okiMprk_bikB6j64k?k b^m20Nl4l6hAha640Nlb0:ldgH1T4+c3li4,lkcE3jc3qQ0{cB1X3w0n0rde6BfblocJcLexqYq!1p2Kq50Een2Alwm^q55_0JlB0nlD5@dQdSfe240l0;5_0dlDgwfk531Rex1Oezd)13eD3we#eId=eK1-d^eNd{eRd~c eVd3d5d7eZ0odbrke9e(ece+e-dt0ee:e=e@elq=dHe}i(2_f1et0N0t0%gA2NfZ0Sg88Bge2;lI1,lKgl81lOgq2B0NgtgvlUgAolj!lZ344)l%oimOpHmRpH0jl-5mm9gWoemYjfb,qjk(o}i15Tl~m;7ql1g^5.m5nd5^m8h0ma0Npvh4mfpSk`qt6k6mhrbsmyfw6zmB1@hyl7mGm~6Q007G6Uqbl(hMl*5fl,qfhSjssaqi8}p;g)iqgNn4m,mSm.h+s+4dnn7Om:7hm?h;7mfWq2n{7Jn04Pirn3i37Of@5Yf=f-5_2PmHih0kqAikf?10ni7ys94ji1t5its;pxo nDn0nr7(7*p36)nK7=nMkro}pLiJpNk/pWnVttpFpwo|ogppb,p:ou9?oIp!kWqgs$o4setW049QoS18o698o8pntHn=jZtB9utXtVbXn{oMsck#s(p,j8t)jzjBo%9YqloZpTk8dpfsp070tAj#sbkRn?t`u2pctYtTp@s)j$pWj)aAaCkcaIkrbGul5RsiiUtl9EmghIo!pzqopkpYjmp$uo4mp)p+p4p-uijkukuUjgksp?t?j#p_19p{tSb:sBp kFfNbqq4buq7bxq9pDu,k118r3pmu9p|jSqduQjXjqs!n|uruWg#u0uZjPusqmnXr70or9tF7#txk{tbcK2Q7I0*tif@0r5}6n5-0r6qnWpUuLpWpuh3szqsbk0wjcvqtds#vhvEk.r`t@b%8dhjb}qKlZqN0WrdcRcTeArheE2arCd;d?eLrpd`ePd|eSc~e0eWrxe5rAe7eHrDebe*eee,egrJe;e?e^eme`0orPe~rSf23B0zu:tb7mq^6t5t8z1?s~f@f_11q5f}b@76gek?3j1+046tf71+qF7qfd2N3YlJgklMnQ0_tP4 le53u;h_f#q}1@2NwM1@wOr+wQt~u}7Zeeud4)wW4}f?u:t80Qf%m0fDvPhDf61q0)0lr#0}lW7+g|0@m00N2z110ncJ5@11dX0:601GwF1awF6t0V0D2Qxc6M0dq2fS151@w(r*1}w,o#vjvlr}d#7u0WhB2c2n7Cf.x4w$fYw gbgw6Ng4xab@xdf9xg1_xj0%9Qxn1GwD1av$qScCll0*04.