Aller au contenu

Rotations d'arbre binaire de recherche

Rotations

  • Les deux ABR suivants possèdent les mêmes valeurs, mais n'ont pas la même structure.
  • Les trois formes trapézoïdales représentent un schéma d'ABR (éventuellement vide).
  • On passe de l'un à l'autre par une rotation sur la racine !

Avec racine 10

graph TB
    R(10)
    R --> S[/"Valeurs\n x < 10"\]
    R --> A("20")
    A --> Ag/[/"Valeurs\n 10 ≤ x < 20"\]
    A --> Ad[/"Valeurs\n 20 ≤ x"\]

Avec une rotation à gauche on obtient l'ABR suivant :

Avec une rotation à gauche effectuée

graph TB
    R(20)
    R --> A("10")
    A --> S[/"Valeurs\n x < 10"\]
    A --> Ag/[/"Valeurs\n 10 ≤ x < 20"\]
    R --> Ad[/"Valeurs\n 20 ≤ x"\]

Avec une rotation à droite on obtient l'ABR précédent.

Exercice

Coder une fonction rotation_gauche qui prend en paramètre un ABR non vide, dont le sous-arbre à droite est non vide et qui modifie la racine de l'ABR suivant cette transformation.

De même, Coder une fonction rotation_droite qui prend en paramètre un ABR non vide, dont le sous-arbre à gauche est non vide et qui modifie la racine de l'ABR suivant cette transformation.

Ces fonctions ne renvoient rien.

  • 👍 la classe ABR (avec doublons à droite) est utilisée ; elle est disponible dans l'IDE.
  • 👍 On garantit que les tests proposent des ABR valides, prêts pour la rotation, ainsi, ils sont non vides et il y a aussi un sous-arbre non vide du bon côté.
###(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 : ∞/∞
.12801359/f.7B8rnb _o=ylaepcwgu)vd4613kRAmhtsP(S02i:050B0t0L0s0S0r0M0m0v0r0s0M0M0p010L0S0u010406050M0y0J0J0s0j0q040P0o0r0y0.0o0k050d0^0`0|0~0?0u04051e171h0d1e0?0B0S0A0$0(0*0,0K0S0x0K0r1v0K0L0;050X0l0r0t1q0)0+011u1w1y1w0L1E1G1C0L0j1f0L0K1I1s010e0Z0t0k0s0J0t010$110M0u0s0k0,0R1C1:1=1Z1K1$1G1)1+0;0a0m0N0j0o0u0o0M0S140k0m0V1.0j0j0t0v2c171`0k1f0d1X2p1U1W1V1D0B1|0,1y0k1(291C1n1p0%1J2z0S2B0k0o2F1C0u2i1f2n2p2T0@1;2d2H1!2M0j0{0r0;0m0E2m2X0=2W1{2Z1K2#2%2)0R2,1=2.2n2y012?0s2(040m0F2`2o0?2}2;0,30320m0C362|2X2~3c2)0b3g383i3a2 0o2$312)0D3n2/2Y1r2=3s2@330g3x393A3b3C3u330i3G3p3I3r3t3d0c3O2:3Q3k040E0Q3V3z2I3R3D0E2+182-3o3W3(3Y0E2_3-2{3/3%2!3K320E353^373y3j3}0;0E3f413h3:3|3S463m493`444d3Z3w4g433q3=3F4m3H3;453Z3N4r3P4t4j0E3U4x4b3B4j0R3#4D3{4F3D0R3,2T4h4o4u0R3@4P4n3X4S404V4s4c4M484!4y4$3L0R4f4)4E3J4G4l4/4K4;4M4q4@4i4M4w2V1k2R172F2s0B1W2x3q0v2N1,1f541g52502V5a0V2S4*1K0G0;0V0e3g4W3(0w2)5s4#2=0e0;260X2c0n0x0s0y0v0K0t5x5m0,0:040O5M4:2 0;0s0l0j5S4^015P0z0T3n0m5*0m5t2!0;0L0J0u3g5,5y0,0o0;0p5?5-2=5V5X5Z2~5`040f624o0;0A310t0y5Y4g5+5@5N5U040u0W2b0M5}5^01645|496h5T0k606e2V6q6466495~3b0;5G5I5K5)5+6F6j0J0o0q1(6o6u6N6s6p6i6x045W6z2-6V0;6D6A6Y5p262b5L6E6B6)673X6H5H5J6:4P6g6N6Z0x0j1=0B6T2T6v5!6W6U6q6Z6#6@3(6C7e5.040B6.0L6|6%6=657h5 7j7l7n3_066~7b6y7r5_6?6;6,046a1G6d6X5T79766 7A7E7L7D6+6w6-0o6/7B6r7S7o7F7H6c6$3_7y7F7d7Q787!2{7O046I6{7K7/046t7N7z040I0h0H7Y5P0O0z6L5*7=7-7T7`6*7#7U7?6`6K7.637:2o7=7%7J7a6i7M2-773j5/5;3n7x6M7~8a8e8c7Y708h7v8m7p8d7;7~7@8i7}8r5{7_8v6k6m0L753.7+8f8C8M8R7q8j688g6J8I5l7R8)8b8U7k7W7m8T3q8s2{8u8+6P6R0k8Y7*8A7,618*3Q7g983;7V7X8q8:7|8t7=71739337064Q3Q5o7j0t5r9b1!5v338F5A045C0s5E8@9e8=3q848F7P9H3Q5$5(6f958f5:5=9f7`9h8}89979M7f8l8/5!6Z8o7)378!9)0;6l0.8X8`998S9V8U8$8J8(8L9}8f8O8.6(8;8D8Ua2878~6^04906S9@9$7{af7i9|9(8ka58%a18H7Y9a9#7i9F8_9Q888N720k74ai1K8|2oaa9c6!9!a68{9%7=av8.9o9.9{aKao8E9v7s9+aD7Cah9`8+aka49 al8+a8aXa#a+8n6b8p6}9R9/aJ9,a,9^ana0a`aPa!7Za$8Q8f8082a/5#0;85a99Za|a*9K7t8^a38KbiaZa%a~9XaG7=9T8yaSa(aUb0ama;8Naqbpagbr9y7~9;6nbe8Bbya}agbB7Fb2baasaLaba.b69Wb36Zad92bL96bgbmba6ZbSataEaN7~b.9i7pbGaH7i9kaB9m2.0d5j0t2p2Qc2531o552s2v2q5W1G2p540?0d0V0X0Z0M04.