Arbre binaire de recherche équilibré

On s'intéresse dans cet exercice à des arbres binaires de recherche (ABR) sans doublons. On fournit différentes fonctions permettant de travailler avec de tels arbres :

  • abr_vide : crée et renvoie un ABR vide ;
  • est_vide : renvoie le booléen indiquant si l'ABR passé en argument est vide ou non ;
  • sag : renvoie le sous-arbre gauche de l'arbre passé en argument. Provoque une erreur si celui-ci est vide ;
  • valeur : renvoie la valeur portée par la racine de l'arbre passé en argument. Provoque une erreur si celui-ci est vide ;
  • sad : renvoie le sous-arbre droit de l'arbre passé en argument. Provoque une erreur si celui-ci est vide ;
  • insere : insère x dans l'ABR passé en argument. L'arbre est directement modifié : la fonction ne renvoie rien. Les doublons sont ignorés ;
  • infixe : renvoie la liste des valeurs rencontrées lors du parcours infixe de l'arbre passé en argument ;
  • representation : renvoie une chaîne de caractère décrivant l'arbre. Cette chaîne est au format :
    • ∅ si l'arbre est vide ;
    • (sous-arbre gauche, valeur, sous-arbre droit) dans le cas contraire.
Exemple d'utilisation
>>> abr = abr_vide()
>>> est_vide(abr)
True
>>> insere(abr, 2)
>>> insere(abr, 1)
>>> insere(abr, 3)
>>> est_vide(abr)
False
>>> representation(abr)
'((∅, 1, ∅), 2, (∅, 3, ∅))'
>>> infixe(abr)
[1, 2, 3]
Les fonctions utilisées 
def abr_vide():
    """Renvoie un ABR vide"""
    return [None, None, None]

def est_vide(a):
    """Détermine si l'ABR passé en argument est vide ou non"""
    return a[1] is None

def sag(a):
    """Renvoie le sous-arbre gauche de a
    Provoque une erreur si a est vide
    """
    if est_vide(a):
        raise ValueError("L'arbre est vide")
    return a[0]

def valeur(a):
    """Renvoie la valeur portée par la racine de a
    Provoque une erreur si a est vide
    """
    if est_vide(a):
        raise ValueError("L'arbre est vide")
    return a[1]

def sad(a):
    """Renvoie le sous-arbre droit de a
    Provoque une erreur si a est vide
    """
    if est_vide(a):
        raise ValueError("L'arbre est vide")
    return a[2]

def insere(a, x):
    """Insère x dans l'ABR a qui est modifié en place"""
    if est_vide(a):
        a[0:3] = [abr_vide(), x, abr_vide()]
    val = valeur(a)
    if x < val:
        insere(sag(a), x)
    elif val < x:
        insere(sad(a), x)

def infixe(a):
    """Renvoie la liste des valeurs rencontrées lors du parcours infixe de l'ABR"""
    def aux(a):
        if not est_vide(a):
            aux(sag(a))
            parcours.append(valeur(a))
            aux(sad(a))
        return parcours
    parcours = []
    return aux(a)

def representation(a):
    def aux(a):
        if est_vide(a):
            return "∅"
        return f"({aux(a[0])}, {a[1]}, {aux(a[2])})"

    return aux(a)
1. Hauteur d'un arbre

Écrire la fonction hauteur qui prend en paramètre un arbre binaire de recherche et renvoie sa hauteur. On rappelle que la hauteur d'un arbre binaire vide vaut 0.

Exemples 
>>> abr = abr_vide()
>>> for x in [1, 2, 3]:
...     insere(abr, x)
>>> hauteur(abr)
3
>>> abr = abr_vide()
>>> for x in [2, 1, 3]:
...     insere(abr, x)
>>> hauteur(abr)
2

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

.128013s3o_bcdufvg/0ly napSr1me,(P2=4:+twkihx)050h0y0H0s0K0o0b0q0g0o0s0b0b0D010H0K0t010406050b0i0x0x0s0v0p040u0d0o0i0(0d0r050m0/0;0?0^0-0t041118051b0m1b1d180-0h0K0k0W0Y0!0$0L0K0l0L0o1r0L0H0+050R0f0o0y1m0Z0#011q1s1u1s0H1A1C1y0H0f0d0h0^1z0v190H0L0W0{0b0t0s0r0$0C011E1o010j0T0y0r0s0x0y1y1$1(1-1G1:1C1?1^0+0a0q0B0v0d0t0d0b0K0~0r0q0P1!0v0v0y0g2d111{0r190m1Y2q0H1W1V1X0h1}0$1u0r1=2a1y1j1l0X1F2A0K2C0r1S1k1y0t2j192o2q2U0.1%2e2I1.2N0v0=0o0+0w2n2Y0,2X1|2!1G2$2(0+0C2,1(2.2o2z012?0s2)040c2`2p0-2}2;0$30320E352q2R0y2q2G2t0h2x2~0g1S1_193j1c2S2/2p3e053o0P2T2Y2~0J0+0P0j3x381n1G0I0+0q3I3C392 0j0+0L0s0}0y0i0v3P2:3K0$0*040A3#2Z3%2 0+0s3,2~3)0N0F3e060q3|3O3J2J013E040K3H122-3~3Q3.0r0+0y0b0H0e0k0K0P3=3R3)3+462{3v2~4b043;4o3w3 1.3@3_4v0,3}4D483$40422j0H3Z104B4F3-400x0K0+0n3`4D4q3R4I0Q4L3e4O2~4R2*4$4X3.0d0+0G4+4x2=0f0+0=0M4k3.4m4{404s3V3X3Z4~4y0+4n2W4=3a0+0b0s0l541G4}4B4,4 3:5f3(0+0N0N0z4;495k04510H3Y3!5i59015h585t2#5b0s0h5m5C565K4s4u5E4G55045p0N3`113z3h1a3u0m3s2r3l112u2t1R1T2t0s1B5Z5$1k2.5$0Q0S0U04.
2. Arbre binaire équilibré

Un arbre binaire est dit équilibré :

  • s'il est vide
  • ou si les hauteurs de ses sous-arbres gauche et droit ne diffèrent que d'une unité au maximum. Cette propriété doit être aussi vérifiée récursivement pour tous les sous arbres.

Dans la figure ci-dessous, l'arbre de gauche est équilibré mais pas celui de droite.

flowchart TD
    A0((2))
    B0((1))
    C0((4))
    D0((0))
    E0[ ]
    F0((3))
    G0((5))

    A0 --> B0
    A0 --> C0
    B0 --> D0
    B0 ~~~ E0
    C0 --> F0
    C0 --> G0

    a((5))
    b((3))
    c((9))
    d(( ))
    e((4))
    f((7))
    g(( ))
    i(( ))
    j(( ))
    k((8))

    a --> b
    a --> c
    b ~~~ d
    b --> e
    c --> f
    c ~~~ g
    e ~~~ i
    f ~~~ j
    f --> k

    style E0 fill:none, stroke:none
    style d fill:none, stroke:none
    style g fill:none, stroke:none
    style i fill:none, stroke:none
    style j fill:none, stroke:none

Écrire la fonction est_equilibre qui prend en paramètre un arbre binaire et renvoie le booléen indiquant s'il est équilibré ou non.

Une version valide de la fonction hauteur est accessible dans l'éditeur ci-dessous. Vous pouvez directement l'utiliser sans l'importer.

Exemples 
>>> abr = abr_vide()
>>> for x in (2, 1, 4, 0, 3, 5):
...     insere(abr, x)
>>> est_equilibre(abr)
True
>>> abr = abr_vide()
>>> for x in (5, 3, 4, 10, 7, 8):
...     insere(abr, x)
>>> est_equilibre(abr)
False

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

.128013s3Oo_;bcdufvg/T0lyàq napS.r1LF-meh,(P2=4:+twki][5REx)é6050j0H0R0x0U0r0b0v0i0r0x0b0b0N010R0U0y010406050b0k0G0G0x0B0s040z0e0r0k0{0e0w0v020x0G0y0g0v0Y0H150B0u0k0H0b050o12141618100y041w1D051G0o1G1I1D100j0U0m0:0=0@0_0I0U0n0I0r1W0I0R0~050+0h0r0H1R0?0^011V1X1Z1X0R1)1+1%0R0h0e0j181(0B1E0R0I0:1b0b0y0x0w0_0M011-1T010l0-0H0w1j0H1%282a2f1/2i1+2l0G2n040a0v0L0B0e0y0e0b0U1e1g0)260B0B0H0i2I1w2p0w1E0o242U0R2221230j2r0_1Z0w2k2F1%1O1Q0;1.2(0U2*0w1~1P1%0y2N1E2S2U2 11291g2:2g2^0B150r0~0C2R330 322q351/37390~0M3d2a3f2S2%013k0x3a040c3o2T103r3i0_3u3w0O3z3q333s3F0~0X3I3B3K3D3t0e383v0~0%3I1F2}1w2.2X0j2#3s0i1~2x0(1P1E2|0H2~3e3Z3,0)3@3h1S1/0T0~0)0l3Z3C3~0_0S0~0v443R463t0l0~1u0R0f0H1s0-0U0h2N4b3}2;010}040K4q344d0w0~0x4x3s4u0#0P3P0v4J4a454s40040U431x3e4L4c4s4A044h0f0m0U0)4D3S4u4w4S3p3g4y4W4B4(4d4F4H4,3A4K4{4U4r2g4O2N0R0k0B0w3I4}4/4 0i0~0p0B1t4I4K4.3L0~0I0f0n565h3S0e0~0N5n4M365j0x1d0H534=4s4*5B5v040b0x5m4_3|581/5D5K5o4z4;5P5u5N0~0#0#5f4J5Q4:045k0j5t4V2g5q045s5K575i5%5x0R5z0B5E5V4v5{3E0~5H5)5T5+5|4+315U5 044C634~5|5X5Z5;3S500*53555:5#5F4Z4k0k4m4o0H5~4t0~663^683t605I6w5O6764696b6H6d0_4F5Y6n6B0e486a0w622 6h5R4Y0b4i6r6t4p6c5M6N6y6w4X616F6-6*5=6K6A6I6x046f6Q6`6S4B6V5*6M015-0F6w0G0U3b736+750~020r0R0g5/6X6o3j5j5l7c3s767q3S4X5(7t4d5-7g7i7k4T7m0_797b5K100o3`3?3!7M0o3%1w0R3)7R2Z2V1}1 2X0x1*7O3%1C5L3s2N0G0f0l0x0T0H0f0I0c0~1o1q1s1u0v4^311J3f1D0D0x0v0b1b1d0U1f0v2|2D2F0$1,2k2L2N2P891g4h0v0m3v4$0H0A0v0Z0r1+8b0B0$0b2k5^0v0R0e5y0l0e0U0/0k2J8A0x8p0w0+0n1,0P0v0r00166u0v8n290B3,530k8b1c2G5_0/0r3U0/2K0y8-0U8/0v0x0y0y0H0.0v8z0i532G0l0/4^1M050k0r3f1Z1E7L3s1;1Y1!1$7)7u5w5y5A5P7K3-048b168)0B0R8W8Y0B8!0x2i2J1,930k0y0$2N0B8W7|0I5@8{0)0/860k0b0F8Z2N0/0n5x0i0I7|0*0v0j2C2H0/0g1w9f109f059h3S9j1?1#2o6`4X6q4l1Z6u3Z9t3{9w8(8G9z9B9!1,9F2?9-1,5^6#0H9O2G9P9V8G9Yafar8R0v0h8`1g0$a44n8z0b0A9?0U3f0o9c81040d1g8c2E8B0:0U0F9U9W8L2*8|1d2N85872I0v0w000H0l0l2O522a9A1s008M855z0raa9y0/2N0w0m0e0sa=0v0t0:9R7{a*1P0H5x9P269K8x9`3-9i1!9~9m7E6{6z4-6B4X0h6;040J7x5$0Ibw6P7 7L9v3,8R2kb58x1}1b8f1gbj2K9|bm9la074bua7bF0v4l0v2?1Obaap8Xaf0v0$521O0$8#6#b-aC4ob;9,8X8C8`9ObQ1,bS1=bU9n6ZbB9sbZb#bH0{8C0v0K0b000-b=9AaB6sa58z0#85849R9q9O993f2.blc31@bV7d2tbJ2w0~2z0z0i0B0|9A0L0s241f3Z3=5L303^bFbp4O426w6T4a6?7u4f6!6$b^6)6L7d6G6_bW5Sc.4E5W7~3e064{cX41a-c!496.c)5x0!bwbr2Tbp4X6^bs6`4@6gc}6B4O4Qbz6p6#4!8rd76.c?c;c/c_dg4|5!di0~516ldl656w0T5a045c5ec%4?0~by6~747G040qbCdwdya10~0h7pdL5CdNdD695k5J7l6R5rd(6C6a0kd6d#2gc:ddc=5G6Ed@dEd~6JbCbDc{dxdWd{dZ6Wdtc^bxd/7v0fe93p6Y4s5-7Cehda4Bd=dqe0d:6:erd_d9btdsd`du6|e33pc|e5c~4P4Rd,dX04dZd+7D6R6T2aeg2Tei5Fe8d/706UeS9vda0h4B0h1veu6=c@9o5%d!eJ747sdP7deee!bp4FeX7f7h7jd/dR3ce+04c`eDe54|eGdB54d/evc54NdHdJ6vf4dOe;7df2e}040Qede%0415d?e-dM5}ereeeNezebfleOeK7wf46}2 eEdxfa6kfce@ebd8ff590~0E3v8BbwfFem6BdRdTfJ3PfMeU3 dAfP6mfm6@epf4fTen6abC0W787adSbw0V3P1wcW1J3#7P3:7J0)0+0-0b04.
Aide

Un arbre binaire vide est équilibré.

Dans le cas où l'arbre n'est pas vide, la vérification nécessite trois étapes :

  • vérifier que le sous-arbre gauche est équilibré,
  • vérifier que le sous-arbre droit est équilibré,
  • vérifier que les hauteurs des sous-arbres gauche et droit diffèrent de moins d'une unité.

Si l'une de ses vérification échoue, l'arbre n'est pas équilibré.

3. Construire un arbre binaire équilibré

Écrire la fonction abr_equilibre qui prend en paramètre une liste triée, sans doublons, d'éléments comparables et renvoie un arbre binaire de recherche équilibré contenant ces valeurs. Cet arbre n'est pas nécessairement unique mais il doit impérativement être équilibré et contenir toutes les valeurs demandées.

En prenant valeurs_triees = [1, 2, 3], on obtient :

flowchart TD
    A((2))
    B((1))
    C((3))

    A --> B
    A --> C

En prenant valeurs_triees = [5, 6], on peut obtenir deux arbres équilibrés :

flowchart TD
    A((5))
    B[ ]
    C((6))

    A ~~~ B
    A --> C
    style B fill:none, stroke:none

    D((6))
    E((5))
    F[ ]

    D --> E
    D ~~~ F
    style F fill:none, stroke:none

En prenant valeurs_triees = [1, 2, 3, 4, 5, 6], on aussi peut obtenir deux arbres équilibrés :

flowchart TD
    A((4))
    B((2))
    C((5))
    D((1))
    E((3))
    F[ ]
    G((6))

    A --> B
    A --> C
    B --> D 
    B --> E 
    C ~~~ F 
    C --> G 
    style F fill:none, stroke:none

    A1((4))
    B1((2))
    C1((6))
    D1((1))
    E1((3))
    F1((5))
    G1[ ]

    A1 --> B1
    A1 --> C1
    B1 --> D1 
    B1 --> E1 
    C1 --> F1 
    C1 ~~~ G1 
    style G1 fill:none, stroke:none

Insertion obligatoire

Compte-tenu des fonctions présentées plus haut, la seule façon d'insérer des valeurs dans un arbre est d'utiliser la fonction inserer.

Les tests de cet exercice utilisent les fonctions hauteur et est_equilibre. Des versions valides de ces fonctions sont donc accessibles dans l'éditeur ci-dessous.

Exemples 
>>> abr = abr_equilibre([1, 2, 3])
>>> est_equilibre(abr)
True
>>> infixe(abr)
[1, 2, 3]
>>> abr = abr_equilibre(["a", "b", "c", "d", "e", "f"])
>>> est_equilibre(abr)
True
>>> infixe(abr)
['a', 'b', 'c', 'd', 'e', 'f']
Aide

L'aspect trié de la liste des valeurs permet de définir astucieusement l'ordre dans lequel les insérer.

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

.128013s3_8ufv»y n7GaSû1me(P24C:jtw«i][h)6Oo;bcdg/0làqABp.r-,=+Nk95Rxé050P0t0B0o0E0T0b0k0O0T0o0b0b0%010B0E0Y010406050b0f0s0s0o0!0j040p0L0T0f130L0l0k020o0s0Y0M0k0-0t1d0!0V0f0t0b050R1a1c1e1g180Y041E1L051O0R1O1Q1L180P0E0h0{0}0 110H0E0Q0H0T1(0H0B16050?0N0T0t1Z0~10011%1)1+1)0B1;1?1/0B0N0L0P1g1:0!1M0B0H0{1j0b0Y0o0l110w011^1#010g0^0t0l1r0t1/2g2i2n1`2q1?2t0s2v040a0k0v0!0L0Y0L0b0E1m1o0;2e0!0!0t0O2Q1E2x0l1M0R2c2$0B2a292b0P2z111+0l2s2N1/1W1Y0|1_2:0E2=0l261X1/0Y2V1M2!2$37192h1o2{2o300!1d0T160k0r2Z3b173a2y3d1`3f3h3j0w3m2i3o2!2/013t0o3i040k0c3x2#183A3r113D3F0k0x3J3z3b3B3P3j0,3T3L3V3N3C0L3g3E3j0J3!3p3c1!3s3)3u3G0m3.3M3;3O3?3+3G0e3`3$3|3(3*3Q0+423q443X040r0S493:2|453@0r3l1F3n1N351E2_2)0P2-3B0O262F0:1X1M340t364o4n3y054x0;4F4a4i0*160;0g3T3/3B0C3j4T3{4i0l0g160o0N0!0d0t1A0^0E4)0t4Y434i15040u4=4N3e160h3E0t0f0!0b0d2*0E0t1C4{4h2o4^0I0z3!0k5h0k4U3%4P044R5a4V4X4H2#5k4b4$040o0f0.5p3%4^4`5s4M5b3s4Q0t0N1l5B444^0$3T5j4Z4}042q0l5N4@165e5g5i5%5u4O160E4S5F5S4?5U0;5L0B5R5)2o0L16020T0B0M0%5^5T5I5V2~5Y5c165f5F065%6d5i5_640s4.51625:1`5{04615.6g115D67645=5M6r63116o0(6l4|645W6v6t5!6E5H6B160R0R6L3B6i163w6b6e6e6s3C5+0l0b0t2V6I016u5F6Z0l4%6*5P6R3%6/044 1?525456581D6-6A6+160G6*6^6i1+6k716m6J040F0I5$6X6f726^5y5A7b6F7d5E397k5J5?6;165Q6z7c6!0478570f6?446o0#7G4i6T4d7w047g6W7i7j7A7l5z7O7r4o7t7C6j7F7z7p016C7K2o7M4m7s7A6=7(6M7B6H7o7@5d3!6c7T7)7l7,6n166q375/804%4)0d0h0E0;7X7Q377~5h6.4%7W7`3B6,7:7)7M4f8n5C7x823O0N162C7X764~506|550!57598u5O6K7?3B7I8x017.7O8g3n8i877@5m2V0B525X8O6@6:6b1E4K4E4p8/0R4s1E0B4u8@2+2%25272)4(1?2$4s1K5G3B2V0s0d0g0o0*0t0d0H0c161w1y1A1C0k6a391R3o1L0y0=0B1@0b1j1l0E1n0k0!0/2M0l2.7m2e0l2*0@9J9l2S0T000t0.6(0O0E0O1@0=0k5y2e1s3)9u2E9J2z0E9k0k0P000f1o0W0X0-9m0k1?0`2~6%0!2Q0`0b9Q0g0g2W8$2s0B0k2s0k2h9 2ia99O0o9B0o9U2=aaa9ab0;0b9W9Faf0k0A0f0b1A000U0k9;1@a50f0^1?0Z0k9s0`0D9.9D0}9W9)0B0`0i9`1@0T1n0Q9.aX001e4:9Z5Wa#0{0H9Ta.0!9`ai2M2O2Q9.009}6(a_1na90l0/2i0s0L9}aC3c0L0q0B0Z1N9q1ha{0T0k0/0?2Pac2N2O1=1@2S4x6$2*aG2VaW0`a(2V0`2S340L0Oa.aa1obDbF9X1o2~1W1Aau0}0k6`51a;9ObUajal9Xa99W0T9{a,6{530k9wax0#bz1C0$0k9A2M520!0@a9bJ0/0;a;0Y1k0`0ta49Vak1xa8aJ0K1o9y1+6%aW0k9abl9-b(b:0`0N2~0@bAb,a 9B0t340/6%9Jcxac1e9mbd180f0T3o1+1M8.3B1|1*1,1.958v04758L4O0O160)1n4;cV68047y866Z0*cX04cZ2=7Oc)3n8Y3Bc,cYc!7O0F4T0R8.3Gb^a;9Pb:bS8d1@0M1EcJ18cJ4J4ycM1,1~1-2w7;748D1h0W0nc;8R6^7n8q7{8w8)4b160pdpc|c~d0bm52b79Z0!a)301o8c0;bc0Rdb1EcG3o2_dg1}cPdk7)2B2s2u162H0p0O8I0Ya90v0j2c1n4T4D5G384od0c+5J5-dv5q3G765w4(4*4,aG1+4:8Cc$64bT8G6~8Ke0cS5#5.8Xd}5nc46*4We2ec3Oe48mei8M4_dn6x5@et73c(ds167_ex5Z7P9n8W7ien5,eGeo7vdy4i6o020Q5 eReI7Zdl04eM3y8XeO728!0=8%8R4^cUeJ2oc_c.c{eD7=c*e-c-c/c#e@1`e}c?c+f0e{f37dc}7R6Y7!7D7ae~7A6o85f6728pe$88eS6yfi7)7+eU5Ue#4Ifn8Nft7@6o6P8R7M6V8he,7U16dufmfj84eRee538H8J70faeEe?fp7@777$dDfd6den8#e:fwf4dmeD7VfNfze%7Yf@fqeBdrf.3O16fg7%fC8P167Jf~8S0E167/f!8o5!c=3yc@8*04f?5tfAeFg7f=ebfXf$79g2fOfu166Dg78Te|dxg3gifygle%0IfcfJ7 8Z16f,0!8(gDdz5xewgccSf_gG8rg9048tfXf5gg6.8z048BgBezf;8Eb*6}8I6 8U8R8Qgzg!gbf`dw7P3.c 4y2$d^4r4B188=0=0@0_04.

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

.128013s3_8ufv»y n7GaSû1me(P24C:jtw«i][h)6Oo;bcdg/0làqABp.r-,=+Nk95Rxé050P0t0B0o0E0T0b0k0O0T0o0b0b0%010B0E0Y010406050b0f0s0s0o0!0j040p0L0T0f130L0l0k020o0s0Y0M0k0-0t1d0!0V0f0t0b050R1a1c1e1g180Y041E1L051O0R1O1Q1L180P0E0h0{0}0 110H0E0Q0H0T1(0H0B16050?0N0T0t1Z0~10011%1)1+1)0B1;1?1/0B0N0L0P1g1:0!1M0B0H0{1j0b0Y0o0l110w011^1#010g0^0t0l1r0t1/2g2i2n1`2q1?2t0s2v040a0k0v0!0L0Y0L0b0E1m1o0;2e0!0!0t0O2Q1E2x0l1M0R2c2$0B2a292b0P2z111+0l2s2N1/1W1Y0|1_2:0E2=0l261X1/0Y2V1M2!2$37192h1o2{2o300!1d0T160k0r2Z3b173a2y3d1`3f3h3j0w3m2i3o2!2/013t0o3i040k0c3x2#183A3r113D3F0k0x3J3z3b3B3P3j0,3T3L3V3N3C0L3g3E3j0J3!3p3c1!3s3)3u3G0m3.3M3;3O3?3+3G0e3`3$3|3(3*3Q0+423q443X040r0S493:2|453@0r3l1F3n1N351E2_2)0P2-3B0O262F0:1X1M340t364o4n3y054x0;4F4a4i0*160;0g3T3/3B0C3j4T3{4i0l0g160o0N0!0d0t1A0^0E4)0t4Y434i15040u4=4N3e160h3E0t0f0!0b0d2*0E0t1C4{4h2o4^0I0z3!0k5h0k4U3%4P044R5a4V4X4H2#5k4b4$040o0f0.5p3%4^4`5s4M5b3s4Q0t0N1l5B444^0$3T5j4Z4}042q0l5N4@165e5g5i5%5u4O160E4S5F5S4?5U0;5L0B5R5)2o0L16020T0B0M0%5^5T5I5V2~5Y5c165f5F065%6d5i5_640s4.51625:1`5{04615.6g115D67645=5M6r63116o0(6l4|645W6v6t5!6E5H6B160R0R6L3B6i163w6b6e6e6s3C5+0l0b0t2V6I016u5F6Z0l4%6*5P6R3%6/044 1?525456581D6-6A6+160G6*6^6i1+6k716m6J040F0I5$6X6f726^5y5A7b6F7d5E397k5J5?6;165Q6z7c6!0478570f6?446o0#7G4i6T4d7w047g6W7i7j7A7l5z7O7r4o7t7C6j7F7z7p016C7K2o7M4m7s7A6=7(6M7B6H7o7@5d3!6c7T7)7l7,6n166q375/804%4)0d0h0E0;7X7Q377~5h6.4%7W7`3B6,7:7)7M4f8n5C7x823O0N162C7X764~506|550!57598u5O6K7?3B7I8x017.7O8g3n8i877@5m2V0B525X8O6@6:6b1E4K4E4p8/0R4s1E0B4u8@2+2%25272)4(1?2$4s1K5G3B2V0s0d0g0o0*0t0d0H0c161w1y1A1C0k6a391R3o1L0y0=0B1@0b1j1l0E1n0k0!0/2M0l2.7m2e0l2*0@9J9l2S0T000t0.6(0O0E0O1@0=0k5y2e1s3)9u2E9J2z0E9k0k0P000f1o0W0X0-9m0k1?0`2~6%0!2Q0`0b9Q0g0g2W8$2s0B0k2s0k2h9 2ia99O0o9B0o9U2=aaa9ab0;0b9W9Faf0k0A0f0b1A000U0k9;1@a50f0^1?0Z0k9s0`0D9.9D0}9W9)0B0`0i9`1@0T1n0Q9.aX001e4:9Z5Wa#0{0H9Ta.0!9`ai2M2O2Q9.009}6(a_1na90l0/2i0s0L9}aC3c0L0q0B0Z1N9q1ha{0T0k0/0?2Pac2N2O1=1@2S4x6$2*aG2VaW0`a(2V0`2S340L0Oa.aa1obDbF9X1o2~1W1Aau0}0k6`51a;9ObUajal9Xa99W0T9{a,6{530k9wax0#bz1C0$0k9A2M520!0@a9bJ0/0;a;0Y1k0`0ta49Vak1xa8aJ0K1o9y1+6%aW0k9abl9-b(b:0`0N2~0@bAb,a 9B0t340/6%9Jcxac1e9mbd180f0T3o1+1M8.3B1|1*1,1.958v04758L4O0O160)1n4;cV68047y866Z0*cX04cZ2=7Oc)3n8Y3Bc,cYc!7O0F4T0R8.3Gb^a;9Pb:bS8d1@0M1EcJ18cJ4J4ycM1,1~1-2w7;748D1h0W0nc;8R6^7n8q7{8w8)4b160pdpc|c~d0bm52b79Z0!a)301o8c0;bc0Rdb1EcG3o2_dg1}cPdk7)2B2s2u162H0p0O8I0Ya90v0j2c1n4T4D5G384od0c+5J5-dv5q3G765w4(4*4,aG1+4:8Cc$64bT8G6~8Ke0cS5#5.8Xd}5nc46*4We2ec3Oe48mei8M4_dn6x5@et73c(ds167_ex5Z7P9n8W7ien5,eGeo7vdy4i6o020Q5 eReI7Zdl04eM3y8XeO728!0=8%8R4^cUeJ2oc_c.c{eD7=c*e-c-c/c#e@1`e}c?c+f0e{f37dc}7R6Y7!7D7ae~7A6o85f6728pe$88eS6yfi7)7+eU5Ue#4Ifn8Nft7@6o6P8R7M6V8he,7U16dufmfj84eRee538H8J70faeEe?fp7@777$dDfd6den8#e:fwf4dmeD7VfNfze%7Yf@fqeBdrf.3O16fg7%fC8P167Jf~8S0E167/f!8o5!c=3yc@8*04f?5tfAeFg7f=ebfXf$79g2fOfu166Dg78Te|dxg3gifygle%0IfcfJ7 8Z16f,0!8(gDdz5xewgccSf_gG8rg9048tfXf5gg6.8z048BgBezf;8Eb*6}8I6 8U8R8Qgzg!gbf`dw7P3.c 4y2$d^4r4B188=0=0@0_04.