Approche tableau

Dans un premier temps, on va gérer la collection triée avec un tableau de type list en Python. On notera au passage que le terme list est un abus de langage en termes de structure de données.

1. Créez la classe TableauTrie qui dérive de CollectionTriee (en instanciant l'attribut self._stockage comme une list) et qui implémente les méthodes insert(), contains() et delete(). Votre implémentation ne peut utiliser que des opérations basiques sur les tableaux (accès par l'opérateur [], itérations for et while). Vous utiliserez les résultats du TP précédent pour maximiser l'efficacité algorithmique pour la création et l'accès aux éléments. En revanche, les opérations avancées de Python sur les tableaux (slices, in - sauf dans le cas des for -, sort() ...) sont interdits.
2. Optimisez votre code au mieux pour exploiter le fait que le tableau est trié à tout moment.
3. Testez votre code en vérifiant notamment que des insertions/suppressions successives maintiennent le tableau trié.

Par exemple, le code ci-dessous

# Mettre les import appropriés

if __name__ == '__main__':

    lt = TableauTrie()
    l = [ 1, 10, 2, 9]
    for i in l:
        lt.insert(i)

    print(lt)
    print(lt.contains(10))
    print(lt.contains(3))

    print(lt.contains(9))
    lt.delete(9)
    print(lt)
    print(lt.contains(9))

Doit fournir comme sortie

[ 1, 2, 9, 10 ]
True
False
True
[ 1, 2, 10 ]
False

Des tests unitaires sont disponibles ici