Équilibrage d'arbre binaire de recherche

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.

Équilibrage

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é !

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é, alors qu'il comporte les même valeurs !

Exercice

Coder une fonction équilibre qui prend en paramètre un abr et qui renvoie un nouvel arbre binaire de recherche équilibré également représenté avec la classe ABR.

• on garantit que l'arbre est sans doublon.
• 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 booléen (l'arbre est-il équilibré ?) ainsi que sa hauteur.

###(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 : ∞/∞

.128013],59/f.q7B8r;nb _o=ylaepcwgu)vd4613kRAméhtsP(S0+2è[ji:050F0x0Q0w0#0v0R0q0z0v0w0R0R0t010Q0#0y010406050R0C0N0N0w0m0u040U0s0v0C0`0s0o050f111315170 0y04051n1g1q0f1n0 0F0#0E0/0;0?0^0P0#0B0P0v1E0P0Q0}050*0p0v0x1z0=0@011D1F1H1F0Q1N1P1L0Q0m1o0Q0P1R1B010g0,0x0o0w0N0x010/1a0R0y0w0o0^0X1L1|1~1,1T1/1P1=1@0}0a0q0S0m0s0y0s0R0#1d0o0q0(1`0m0m0x0z2l1g230o1o0f1*2y1%1)1(1M0F250^1H0o1;2i1L1w1y0:1S2I0#2K0o0s2O1L0y2r1o2w2y2$101}2m2Q1-2V0m140v0}0q0I2v2*0~2)242,1T2.2:2=0X2^1~2`2w2H012 0w2;040q0J332x0 362}0^393b0q0G3f352*373l2=0d3p3h3r3j380s2/3a2=0H3w2{2+1A2~3B303c0j3G3i3J3k3L3D3c0l3P3y3R3A3C3m0e3X2|3Z3t040I0V3(3I2R3!3M0I2@1h2_3x3)3;3+0I323_343{3:2-3T3b0I3e413g3H3s460}0I3o4a3q3|453#4f3v4i434d4m3,3F4p4c3z3~3O4v3Q3}4e3,3W4A3Y4C4s0I3%4G4k3K4s0X3.4i1r2!1g2O2B0F1)2G3z0z2W1^1o4W1p4U2(4S4$0(2#4H1-0K0}0(0g3p4w3Z0A2=4{4B2-0g0}0O0i0C0,0#0p2r504=1T0|040T5c4N3k0}0w5a5i445e0}0D0$3w0q5v0q4|3}0}0E3a0x0C0m0R3p5x511T0s0}0t5H5y1-5f0Z0b3w065w5I5d0^4@044_5o374~3c5%4x53041}0m4$5E5G4S5J0^5f5h5@5Y385l5n5|5j015f5s5u5W5w5P1T5!0#4`4i5X620s5)2V0Q5O5^5~045m0m5+3Z5L040h6r5z040x0R0Q0r0E0#0(6w5Q0}0T654p676M6f5p5k5.155;5F6G5q5g6V6Q6p6Y016t6v616P6n0B0w0C0z0P0x6#64666N686m0o5A5C5=6#6%6#6{6o0y0y1;0F6=6I715 6q6)37707d4x6|1P5E78040D6@6^6O3s0}5/6T5?2(6m5`7a6o607w5}7f7C62720F2f2k6;7g3Z6?4p5V6_5}5!5$7M3;5)5x7V520}0B0O0o0Y5b7Z6W5{7F6*726!7+5_0}0c6l5}720#7l7^6e696Q0!7l6K2$7Q6M80016b6d2$7q7h04827 6m6t020B0Q0n7_7G0}7|7=630}5t6L7p5v88720N8o6*6t5N8h5}7y8s7{8C7e0}0W8L8e8g7.377O8c8d6s0}0f0f8P3Z0N0#0}40858x8y6`7b6 0}6(8S8e2T0R7)7L8?7N798J7i5D6U8s5R7z8B930}0b7n8w8x8z7#7%8`7l7-2_9d7A7c8|3;7E9j8.046,6.6:7}8#6x8r9n6H047~8c9k969A6W9a8+8,9k7$7(7*9H7?6X8 9l8:6u7z7I0s7K9w8G8p049G2_8W9o8N9x1-8%4f9#9E9r8R9q8H5r5U5W9k7t0s6~979S9Q6n7;a48U9*9+1-0z0I0}030q0N2W6c0#1Q5B7j929K8-7`0}0m0O110v0*6k9$8D5M9.2~0}0M0k0L9h9J3`9}9r9N9ga29i349katavax9=9*889:044Ra77@aC3k0p0}289h7zam917v9_6264aJ34aq62acaeagai1/1QaT0Caw0wayapaa6aas0)5E1faz7r04b2b4b63`1g4/0x2y2Zbn4V1x4X2B2E2z5m1P2y4W0 0f0(0*0,0R04.