Valeurs supérieures à une cible dans un ABR

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)

Écrire la fonction plus_grand qui prend en paramètres un arbre binaire de recherche ne contenant que des nombres entiers abr et un entier k.

Cette fonction renvoie la liste triée des valeurs présentes dans l'arbre supérieures ou égales à k.

Il est possible de résoudre ce problème en effectuant un certain parcours de l'arbre et en ne retenant a posteriori que les valeurs intéressantes. Cette solution est néanmoins inefficace car elle est amenée à visiter des sous-arbres que l'on pourrait ignorer en étant astucieux.

Les tests de cet exercice vérifieront donc que la solution proposée est efficace. Cette efficacité est mesurée à l'aide du nombre de valeurs lues lors de la résolution.

Exemples

>>> abr = abr_vide()
>>> for x in (1, 2, 3, 4, 5):
...     insere(abr, x)
>>> plus_grand(abr, 0)
[1, 2, 3, 4, 5]
>>> plus_grand(abr, 4)
[4, 5]
>>> plus_grand(abr, 6)
[]

Évaluations restantes : 10/10

.128013s3o_8;bcdufvg/0ly n7apS.r1me,(P2=4:twki9][5hx)6050j0C0K0v0N0q0b0s0i0q0v0b0b0H010K0N0w010406050b0k0B0B0v0z0r040x0d0q0k0:0d0t050o0`0|0~100^0w04191g051j0o1j1l1g0^0j0N0m0(0*0,0.0S0N0n0S0q1z0S0K0?050Z0h0q0C1u0+0-011y1A1C1A0K1I1K1G0K0h0d0j101H0z1h0K0S0(130b0w0v0t0.0G011M1w010l0#0C0t0v0B0C1G1.1:1^1O1{1K1~200?0a0s0F0z0d0w0d0b0N160t0s0X1,0z0z0C0i2l19230t1h0o1*2y0K1(1%1)0j250.1C0t1}2i1G1r1t0)1N2I0N2K0t1!1s1G0w2r1h2w2y2$0_1/2m2Q1_2V0z0}0q0?0s0A2v2*0@2)242,1O2.2:2=0G2^1:2`2w2H012 0v2;040s0c332x0^362}0.393b0s0I3f352*373l2=0R3p3h3r3j380d2/3a2=0V3w2{2+1v2~3B303c0u3G3i3J3k3L3D3c0f3P3y3R3A3C3m0O3X2|3Z3t040A0p3(3I2R3!3M0A2@1a2_3x3)3;3+0A323_341i2!192O2B0j2F370i1!211h461k442(412x054b0X2#3Y3;0M0?0X0l3p3H370L2=4v3Q3}0l0?0w140b0e0n0z1:0j4A4p1_0=040E4N3|2-0?0v4T3:4P0?0D3p0s4w3z0t0?0M4Y374Q0U0J3w0s4@4(4B1_4r044t4.3z4y3c4 3*4D040v0k0T533;4Q4S4j4o4U2~4W5a4!044;4?4^5o4)3Z4|0N4u5e4_4O1O0d512V0K4%5q3}0?0C0b0K0e0m0N0X5j1O5c5O3k5i5e5E5k5m5e065o5!4^5V5h040m3a5D4`5y0?0H5,5x5S5)3a0C0k0z5R015Q5U5-5?4X5 5=5}0?0U5n5#5p60015s5u2$5w5g5?4-5v5%0.0d0?020q0K0g5:6k6b4+5@0q5|4Q4=5Y696D6g4Z5(5759636h654R5|6w0b0v0n6z0?5d2(6v5T6W644:676C6E5#6l380?2r0`6q0v5C6K6G6m0?0y6O4W0w0w1}4M6=4/6U6`6x6T5l686E6*6w6I756V2_790?6Q6 6Z6L5~7j6?6+56750U6$2$5Z696*4|2r0K5`186u646w6-0k6/6;7t7u4@7f047F7H5;6L6n046t6f6*4Q0Q0P777w6,0Y7A7Q7n7a587c73627m71765Y194m0C2y2Z7_451s472B2D2z1Z1#2B0v1J7|0o460^890Y0!0$04.