Rupture d'arbre non ordonné

🧓 Cet exercice utilise une modélisation d'arbre non ordonné, avec la liste des parents.

Rupture d'une branche

On définit la rupture d'un arbre non ordonné à l'indice i comme le fait de couper le lien de parenté du nœud d'indice i, ce qui produit un arbre réduit par rapport à l'initial et un nouvel arbre, la branche coupée. On souhaite conserver le même type de représentation : une liste de parents ainsi qu'un dictionnaire d'association.

Exemple

Prenons un arbre non ordonné

graph TB
    R3("Ga") --> P1("Bu")
    R3    --> P2("Zo")
    R3    --> P3("Zo")
    P1   --> P4("Meu")
    P1   --> P5("Meu")
    P1 --> Un("Un")
    Un --> Deux("Deux")
    Un --> Zéro("Zéro")

    S3("0") --> Q1("2")
    S3    --> Q2("3")
    S3    --> Q3("1")
    Q1   --> Q4("4")
    Q1   --> Q5("5")
    Q1 --> ZUn("7")
    ZUn --> ZDeux("8")
    ZUn --> ZZéro("6")

Avec une modélisation possible :

🐍 Script Python

# Indices     0  1  2  3  4  5  6  7  8
parents = [None, 0, 0, 0, 2, 2, 7, 2, 7]
assoc = {0: "Ga", 1: "Zo", 2: "Bu", 3: "Zo", 4: "Meu", 5: "Meu", 6: "Zéro", 7: "Un", 8: "Deux"}

On choisit de couper à l'indice 7 ("Un" ; ce n'est pas la racine de l'arbre). "Un" devient alors la racine de la branche coupée. On obtient :

L'arbre réduit

graph TB
    R3("Ga") --> P1("Bu")
    R3    --> P2("Zo")
    R3    --> P3("Zo")
    P1   --> P4("Meu")
    P1   --> P5("Meu")

Avec une modélisation possible

🐍 Script Python

reduit_parents = [None, 0, 0, 0, 2, 2]
reduit_assoc = {0: "Ga", 1: "Zo", 2: "Bu", 3: "Zo", 4: "Meu", 5: "Meu"}

La branche coupée

graph TB
    Un("Un")
    Un --> Deux("Deux")
    Un --> Zéro("Zéro")

Avec une modélisation possible

🐍 Script Python

coupe_parents = [1, None, 1]
coupe_assoc = {0: "Zéro", 1: "Un", 2: "Deux"}

Exercice

Coder une fonction rupture qui prend en paramètres

• parents et assoc qui définissent un arbre étiqueté non ordonné.
• i_rupture un entier positif et inférieur à la taille de l'arbre.

Et qui renvoie le résultat de la rupture : un tuple à quatre éléments composé

• d'une liste des parents de l'arbre réduit
• d'un dictionnaire d'association de l'arbre réduit
• d'une liste des parents de l'arbre branche coupée.
• d'un dictionnaire d'association de l'arbre branche coupée.

On garantit que l'indice de rupture ne correspond pas à la racine de l'arbre initial.

On pourra donner n'importe quelle modélisation valable pour l'arbre réduit comme pour la branche coupée, tant que la greffe permettrait de reconstruire l'arbre initial.

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

.339.128013x/.Trnbylaeêu)*d63m(P+02-],59f!78 N_o=pcwgv4F1kRhtsSà[ji:050r0m0Z0l0)0k0!0J0P0k0l0!0!0N010Z0)0O010406050!0o0u0u0l0g0j040#0M0k0o0~0M0h050d1517191b130O04051r1k1u0d1r130r0)0S0?0^0`0|0Y0)0R0Y0k1I0Y0Z11050.0i0k0m1D0_0{011H1J1L1J0Z1R1T1P0Z0g1s0Z0Y1V1F010F0:0m0h0l0u0m010?1e0!0O0l0h0|0z1P20221:1X1?1T1_1{110b0J0w0g0M0O0M0!0)1h0h0J0,1~0g0g0m0P2p1k270h1s0d1.2C1+1-1,1Q0r290|1L0h1^2m1P1A1C0@1W2M0)2O0h0M2S1P0O2v1s2A2C2*14212q2U1;2Z0g180k110J0V2z2.122-282:1X2=2@2_0z2|222~2A2L01330l2^040J0t372B133a310|3d3f0J0T3j392.3b3p2_0D3t3l3v3n3c0M2?3e2_0s3A2 2/1E323F343g0H3K3m3N3o3P3H3g0I3T3C3V3E3G3q0E3#303%3x040V0y3,3M2V3(3Q0V2{1l2}3B3-3^3/0V363}383 3@2;3X3f0V3i453k3L3w4a110V3s4e3u40493)4j3z4m474h4q3:3J4t4g3D423S4z3U414i3:3!4E3$4G4w0V3+4K4o3O4w0z3=4Q484S3Q0z3|2*4u4B4H0z444$4A3.4)4d4,4F4p4Z4l4;4L4?3Y0z4s4_4R3W4T4y4 4X514Z4D544v4Z4J594(4T4P5d4.4w0t4V5h4M3Q0t4#3~4-5n3Y0t4+5r4=4Y5u4:5x4`5z3f0t4^5C503_5u4~5I555K5F535N5a5u585S5e5o5c5W5i5o5g5!5t3f0T5l5(4{5*5q465s5.110T5w5;5y563Y0T5B5`5D5|5*5H605J3/0T5M655O675R6a5T5*5V6e5X5}5Z6i5#5}5%6m5)110D5,6q5?040D5:4f5{5P6s5_2B1v2(1k2S2F0r1-2K3D0P2!1|1s6J1t6H2,4m056P0,2)61010W110,0F3t5=1X0Q2_6,6B0h0F110g0o0O0Z0o2v6;6$10040v6 6611212v0h0Z0!745O710C3t0J6-3o111W0M0P7c3b7e7g7i3c110)0L6_6{6}0m7o3D710p0*3A0J7H7h6B0!2504010X1^0S0M0)1U0,0o0c0J190i2v0=0)0`0o0=2s0^0J7x6|2v017G7I7s0h110.0:1T7r6B0M110N7}6$0h0i112c7B3%71736X6=76191^7a883^7D7=7H7@116P0h0!0m0g0S7A4m7J6$7 04818w7s710%8i1;0W0P110K1i8v2*8x5J6(040F3F8275040L8V5O0M6/042X8Z3w85040g220R8N2}8D118b2,8d047`0k7|8c70110p0B8l8P5O8R8T0g8)4B7u993%8#7u1j8C6=8+8-0h8/8G1X8a9n7j8`0/8|8:388=047E937I943w112Z0m0o0r9c3^8z8B8O8n8%9A7?8_0P0Y0m0u8(9h8y809J1;8E928w9C6O0V11030J0o2O0J0O1@9Q8m6B8R0Q1H8}9N9S1i8r8t9v6F6B8E9q7t049F9Ha8719(9 8y8$7%9#1X8I8K8Mad117F4t9Bat9R6$0P9,049.7,2%0M8T0h7V0g2r0o0J0h0a9H0J0m0!0Z0J2X8p0h0oa412auau7s8R0)6+9Y8W778g7b8~5Ja7a.6b9E0M9G9Ia;7p11af2}9*9daia-ag8Q8J048L2Oap04ar4$aZbda 3^ax9-0?00aPaR7,8-0P2X1U2X2o0)3eaX06beaZ9O8pa28ub98Fa`9aaaa@acbG89a|ak0|9LbO6%b50f6_bwby9_6$8R0m1La(b3a=bIa^bR9L9Ma~9O7v7.7zb9bb3~bXat7sbhazbjbl0J7,0Z0n0Z1U0$1~6`8s9^bebAa18sbDbL8j11bF8^83a?b+ch9$bNa)8!9!cs3bam040U3e8rcb9Ba#11b#cBcp9oaqcCbz9S9U9W9gcl5J8z0ea87^040l0O0O1^a_cR7d8?cVcnbKc%a{9ycLa!8_abc$b/7~cub(9D04a+79b28;a6cjc*b*c,d18 04a}46bxcMawayaA0l9=2jaEaGaIaKaM2Kc00q0qaUaWdrcb9OaQ0l6|0Zb,c`c^cm04bBcfaX9xckd78Wc?b9da3kbdcE049|9@cvbH9T9V9Xc{3D8z0Gb.38bfcq040%0Bb^46b`9OdOdX9ddDd+bAcOd#dMct04cUcI9r2l0Ob90v0pc:d,328ocea3bEd4d^c-7Ccrd$d`8AbRcWdydA3AdcbYa*8fc ehe4a9b;6`7/dJd2d9dCepd_3^cxb7bwevec0|8R6*a88$7heB6?8e0g0~eGd88@e0c|es1gb99zasdd8W0i0)0(2w2yeL1;bQe{cJd.a88z0Aa89W4jbR968Ue~9r8Yfa019e8%cQdE669j8.e%a/c)eY7_9t9~e*el9ydQaYe;b)0(eJd*2BeR01f5046udRfycw1197eq9bfdffd d|9i6^fle8d48{fs9weHe/bcbXdTa%fOdGefcgekbMf0fp9PeBaefBfC3gdx0.etf^cKe:b`ewb)e?e^2x0)1ieAf:41fPgcd-fwfEe}engd04fAg2g39Ogngke|110xf{fEfG6zfxc;dFfZ0m0L77e$fBf,gr3~eQcD8_c~7agF19gHfQd{fDdKa8eNaofdf898fdcWfcgs1XfRfhfT83fk9lfmc(72fYfrgEgG7Te.fwgMav8QfMf9g+9r0)b,aig.gWfU8,fWg0g^f?gDe.d;fJby9O0O0Lh7gUeKh5a9gPd0f#d8dLhx8Whqgfe g d?9`7ub%fig@e)hAb)hohChK3bfRhwhbaha?dBg#b5eOe.h87kaFbR9pf?dHeghfhza5dFhQhNc.gh7sb-f,e,hYhD0|7DhkgAgpgOeygQg|g?c.h:6#e=e@e_g9haicg@ibb:dPh_c_hshRbHg6ifgah/d4hPdPeudS8_7l0PgRe#g}hrgw7@8+1A2xe8eagogNbZh3g%htcWh?hVcSh9eqg;9mhfhMh;8Whihff%b_f)hH8%hJg/8Wh-f/ftf;ik8_iWiih^f`h|f~e-hfi2h0hmiB0`7miEgTh 01a:jecWisg8iujejgi`gli~9x0Bin9Zipi?b)iCgbjo2;gejAhEizfK3D8R2v7/ihfEcWhvjciGjm117fg(7kjaiDi8jFg4c|jO2v0r0o2ob9jTiUjV0!jbj%j)h~iqeoiIi5iFi9fui(i jHbTbVh$gohni60!0L7!22dZj+f,iCk89kkbiHf,jYi%gYb5cz0;j|f;iOf(j!jH6^0-6}jLk578gQj;j*hfj,j@glkekDj?h@fukGjwj#k6kfka9UkcjUcXjWkS0hkh4,0d6Z0m2C2%k)6I1B6K2F2I2D0l1Sk,0d6J13k_0-9t0!04.