Construction d'arbre binaire de recherche équilibré

Rappel : Définition récursive d'arbre équilibré

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.

Construction à partir d'un arbre binaire vide

Il est possible de construire un ABR en partant d'un arbre binaire vide et en insérant successivement, et dans l'ordre, par exemple, les nœuds suivants : [8, 3, 15, 2, 12, 23]. On obtient alors :

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

Cet arbre est équilibré !

Contre-exemple

En partant d'un arbre binaire vide et en insérant successivement, et dans l'ordre, les nœuds suivants : [3, 8, 15, 2, 12, 23], on obtient alors :

graph TB
    R(3)
    R --> S(2)
    R --> A("8")
    S1(" ")
    S2(" ")
    S --> S1
    S --> S2
    B(" ")
    C("15")
    F("12")
    G("23")
    J((" "))
    K((" "))
    L((" "))
    M((" "))
    A --> B
    A --> C
    C --> F
    C --> G
    F --> J
    F --> K
    G --> L
    G --> M

Ce n'est pas un arbre équilibré !

Exercice

Coder une fonction abr_équilibré qui prend en paramètre valeurs une liste d'étiquettes et qui renvoie un arbre binaire de recherche équilibré représenté avec la classe ABR. Il faudra donc probablement changer l'ordre des éléments à insérer !

• on garantit que la liste valeurs est triée dans l'ordre croissant.
• on garantit que la liste valeurs est sans doublon, sinon, la requête pourrait être impossible, comme avec valeurs = [42, 42, 42] qui ne peut pas donner un ABR équilibré avec la contrainte de placer les doublons à droite !
• Les tests utilisent une fonction équilibre_et_hauteur (disponible, mais uniquement utile pour les tests) qui prend en paramètre un ABR et qui renvoie un tuple : un booléen (l'arbre est-il équilibré ?) ainsi que la hauteur de l'arbre.

###(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

Exécuter le code
(Ctrl+S)Valider
Ctrl+Enter
(Clic droit pour l'historique)TéléchargerTéléverserRéinitialiser l'éditeurSauvegarder dans le navigateur

Évaluations restantes : ∞/∞

.128013x/.ùr;nbOylaeêu)dVM63×Am(P+02è-],59fq!7B}8 _o={pcwgv41kRéhtsàSLC[ji:050r0n0+0m0?0l0,0R0X0l0m0,0,0U010+0?0W010406050,0p0y0y0m0f0k040.0T0l0p180T0h0R020m0y0W0g0R0(0n1i0f0L0p0n0,050c1f1h1j1l1d0W04051Q1J1T0c1Q1d0r0?0!101214160*0?0Z0*0l1+0*0+1b050{0i0l0n1$1315011*1,1.1,0+1@1_1=0+0f1R0+0*1{1(010K0}0n0h1w0n01101o0,0W0m0h160D1=2o2q2c1}2f1_2i0y2k040a0R0A0f0T0W0T0,0?1r1t0_2m0f0f0n0X2O1J2v0h1R0c2a2!2729281?0r2x161.0h2h2L1=1Z1#111|2.0?2:0h0T2@1=0W2T1R2Y2!351e2p1t2_2d2~0f1i0l1b0R0$2X391c382w3b1}3d3f3h0D3k2q3m2Y2-013r0m3g040R0v3v2Z1d3y3p163B3D0R0#3H3x393z3N3h0I3R3J3T3L3A0T3e3C3h0u3Y3n3a1%3q3%3s3E0N3,3K3/3M3;3)3E0Q3^3!3`3$3(3O0J403o423V040$0C473.2`433=0$3j1K3l3Z484g4a0$3u4l3w1U331J2@2%0r292,3#0X2 2D0^1!1R320n343l3R054E0_4M4o2d0%1b0_0K4O3_4g0Y3h4Z414p0K1b0m0i0f0S0)1F0}0?4.0)4(4T1}1a040z4`4f3c1b0!3C0n0p0f1I4t2Z3-3z4}0q0@3Y060R5j0R5c3#4V044X503z4$3E5r3#0h4+040Z0)0h0E2T5v424}4 5a4S513q4,4.5F4g4}0H3R5l4!52040?5P2d5R5T5m491b0=5Z4|1b5f3Y5k5:5U4)4U1b0?4Y5J5=4{3M5)5$5V1}0T1b020Z0+0g605?5M5X5+164}5g5J5i5;6j5%4p1b0y695}0163040U6p5L6e1b5I37615~6c5{6l2d6s0B6v3U5 5J6F5,040q5T5|6w6r1b0c0c6J3#0y0?1b4s356i6j5:6N6C4-0f6d6U040d6:0h5^0h0,5D0n6:5H6@535557596A6a6x040;70046o6M6B014}0G6Q6h6*5;6,3A1b5A5C5E7d767f6y7a6.6:6s6?7s6q6^5z0m0p0X0*6}7B6T5#6E7e7D5Y7K5d1b5S7N7t7D7c756q5e5/7k5k7m7D7p6|6~7v7R5w5N6/7/427z7a0r2I2N7J7Z7L7T6Y5(7b814g6H842d6!1b4k7~7S047U356S6K045*7?5Q5-5h6+7O1b0f0)1f0l0{0+87621b6u7V7C1b0x0O0(7-4~7i6(8p7W7o5B7,8l5!7.8c7:048s8u8w8I8f3l8h6Z6#044d8R6O8#3w8%490i1b2A8I6z4N8q04541_738I0q8K4m8M6q5o2T0+570h8y6C8X0p8v0m8x6h1J4Q4L4v9l0c4y1J0+4A9q2*2#4-1_2!4y1P5K3z2T0y0S0K0m0%0n0S0*0v1b1B1D1F1H0R6g371W3m1Q0:0T1x1j1s0 0m0!2U0R0p2:0R7F271`0,1o1q0?1s9S1U3m2@3z1@0i0n0r0F0,0`0R9 a10F3C0+0n0f2iab2l0r9g0m0F1@1}0$0@2t1R2|0W1q107I0X9I0r167H2Uax2l0?ay010S0Sa70r0S0$aL2l2B0n16aHaJaNa60k0WaQ010f0m1Z630caq0has0+0RaEaRaI4-a0aKaM2t0RaPa/aT0$2l0+aWaYa!a$01a(4H2^42aJ0F12a00~1=bb0n0l0R0K3%a{a;a1aLaN040t0o2C0R2M0Zae577Jbf0l1RbAbibkaGa:0ia=boap0sac2M9_3C0l0)5Abz4-bg9y4I1Y1!9~bma24E0habb)1bbZb74gb91^0Tawb,b63z1 1-1/1;9B3#2z2h2j1b2F0.0X0f19a,0A0k2a1s4O4K5K364N9kb~425o5q8,165t5lco3A5y7+7r8U5G8T8`8N047xcs7M8g7)5^8!9b7n8j909T937(7e5o5_cK7D8kcG7e6s6567cUcIcE1bcO3w6)7l8{7Y8$7m6s8BcX7t6 cs7PcK868C6TcV906Rc;6V6Xc~3z89046%cP6k8{cDcx851b7Adf5W2|6{cwcA7!cz4u8{8}56588I79c`6n8I7h7$dccBcv7}do7 4~7w5Oc(8ec$6Ddj8-dOc/drc^8n5{dD6q0Xa}0403a-0X0?0R9_aX0f2,9,1`2|bjdCc-dE8PdndUdpdJdycCdLdQ778.2Z8:6m83d63#c}c@6qd88bdH8de45u8{cWeg3#7#dXe62dd!1bd%a50l0-9.0p147Q6(9j4F2!cf4xbYeH0!9|b!3#b:0lb=5ob-b_1/211:2u7tc0aPc30Rc5c70Wc9cb0*cd6MeG9U37cj7mcm0n5`e201cq6@cud`dGd|dI8_f18ieBemcydNe982elf4en5-c*3I946TcSe_c:ekc|646668fae7f6fdf8fg1c7kcHe8ec6Tc=cKc_e`c{fs6G1b6IfJ6bfc5b7eeo8geq8z046WcKd8dac+fzdde1f7dg6=7adl8Qe`fGf)5Wdt8 dMdxfHdzdMdB7j6*fAdF8^f,cJfN6CdTfQdV6Pd@fi8ig1dMf3g88DfBfm7tebgked8)effv8mf9fC8ifPckgs92c+eD4R9mbXeK1d9oeIgHgFeJ9W040:9R9)589^6`bu1sa,4E2S2Uab0,0H0R1i0?0 0W1p0 2Ag!0d0R0j2Pg)2Ka40R2Q0l002|1Z0X9ggSd+0e0Rg+0m0Xac0R1_0 f?58g$9/2qa,2hh52I2fab0f0R0M9{1d9e3m1.1md*9_0h00hj320Thm1`2pg#ha1`4Eat0rg}6`ac2O0R1Ha,7m1j2N0*1iab0b1b090z09eP0Zh%hZ0+0V0{0}1_0P0q09gze50Th412a60|0l1_hR0,a,hC0!g)0T0?2Th50T57ha001j4.0ng$g(0 ahgTh|0_ad0?6|g%i7180)g$h8ha0T0ZhV2abthS5l1C04b(i2hh1JiGg$2Q9=0fab0R9QhI2mat0+0T0{bhiEhjhUc7iC9g0nh!04h$0h0wh(iz0z0hh?h^3Eh`fU16iBhXi*i,i.h@5TiEh|h/h 1`0r0ph}1^0n7Fg`1`4PeEhd59cj7Ahv1dhv0.hx1thBhl7|g$i0hKa,hMdlhPh2iEiI0{b)g$9_i5g_1Z2T2V1C2hjA2q0 9,9.0fig0Ri52Q0M0R0/hJiba,iXiZjgid3C0Z3%hWiDi2hk2J3%2O2:bhexj6h~i02Qji4RjkgB4Lg:0xdl0?g$2KicjV6!h h22QjkjJ1t9gb*d/1tiA2|g`hA0K2fh0d)0+0)kujV9GjPicg{003%7`j91`0D0Cjn0?3m0chtgG0_j70,04.