Les arbres

Maintenir une collection triée

Nous allons étudier la façon la plus efficace de traiter le problème suivant : stocker des éléments dans une collection triée et faire des opérations régulières d'insertion et de suppression d'éléments en maintenant la collection triée à tout moment.

Travail préalable

Pour ce faire, nous allons étudier plusieurs façons de gérer une collection triée : avec des tableaux, des listes ou avec des arbres. Pour faciliter la cohérence de l'évaluation et les tests, chacune dérivera de la classe commune CollectionTriee.

from matplotlib import pyplot as plt

import PlotPerf
from random import randint


class CollectionTriee:

   def __init__(self, stockage):
      self._stockage = stockage

   def __repr__(self):
      return str(self._stockage)

   @property
   def stockage(self):
      return self._stockage

   def insert(self, valeur) -> None:
      """
      Insère la `valeur` dans la structure en la gardant triée
      :param valeur:
      :return: `None`
      """
      raise NotImplementedError

   def delete(self, valeur) -> None:
      """
      Enlève la `valeur` de la structure si elle s'y trouve, en gardant celle-ci triée.
      Si la valeur n'est pas dans la structure, ne fait rien, garde la structure identique et renvoie `None`.
      :param valeur: la valeur à effacer
      :return: `None`
      """
      raise NotImplementedError

   def contains(self, valeur) -> bool:
      """
      Vérifie si la `valeur` est dans la structure et renvoie `True` si c'est le cas et `False` sinon.
      :param valeur: la valeur à vérifier
      :return: `True` si `valeur` est dans la  structure `False` sinon
      """
      raise NotImplementedError

   def gen_collection_n(n: int, coll) -> None:
      l = ProfileRunner.gen_intList(n)

      for i in l:
         coll.append(i)

   def gen_collection_list(l: list[int], coll) -> None:
      for i in l:
         coll.insert(i)


'''
Ce qui suit est un hack pour permettre l'utilisation de structures persistantes
avec `ProfileRunner`

Le hack se base sur une variable globale qui stocke la structure persistante à
laquelle on peut accéder avec `setstructure()` et `getstructure()`

Ensuite les fonctions `test_insertion()`, `test_delete()` et `test_contains()`
peuvent être utilisées dans `ProfileRunner.addFunction()`. Il peut être nécessaire 
de spécialiser ces fonctions pour l'usage avec une strucure spécifique dérivée de
`CollectionTriee`
'''

# La structure persistente partagée
structure = None


def setstructure(val):
   """
   Initialise la structure persistante partagée
   :param val:
   :return:
   """
   global structure
   structure = val
   return structure


def getstructure():
   """
   Récupère la structure persistante partagée
   :return:
   """
   global structure
   return structure


def test_insertion(donnees):
   """
   Exécute l'opération `insert()` sur la structure persistente partagée
   de façon itérative sur toutes les données passées en argument
   :param donnees:
   :return:
   """
   global structure

   for i in donnees:
      structure.insert(i)


def test_contains(donnees):
   """
   Exécute l'opération `contains()` sur la structure persistente partagée
   de façon itérative sur toutes les données passées en argument
   :param donnees:
   :return:
   """
   global structure

   for i in donnees:
      structure.contains(i)


def test_delete(donnees):
   """
   Exécute l'opération `delete()` sur la structure persistente partagée
   de façon itérative sur toutes les données passées en argument
   :param donnees:
   :return:
   """
   global structure

   for i in donnees:
      structure.delete(i)


def gen_collection_n(n: int) -> list[int]:
   """
   Génère un tableau de n valeurs aléatoires tel qu'attendu par `ProfileRunner`
   et initialise en également la structure persistante partagée à une collection
   triée avec ces mêmes valeurs.

   Cette fonction sera à spécialiser en fonction des classes dérivées.
   :param n: nombre de donées à générer
   :return: tableau des données aléatoires généré
   """
   data = PlotPerf.gen_intList(n)
   setstructure(CollectionTriee())
   for i in data:
      getstructure().insert(i)

   return data


if __name__ == '__main__':
   tt = _  # À compléter avec le constructeur approprié d'une classe dérivée de `CollectionTriee`.

   pr = PlotPerf.ProfileRunner()

   # Remplacer `CollectionTriee.gen_collection_n par le générateur
   # approprié dans la classe dérivée.

   # test_insertion sera à spécialiser selon la structure effective utilisée
   pr.addFunction(test_insertion, PlotPerf.gen_intList)
   # gen_collection_n sera à spécialiser selon la structure effective utilisée
   pr.addFunction(test_contains, gen_collection_n)
   pr.addFunction(test_delete, gen_collection_n)

   pr.runProfiler(range(1, 300, 5))
   pr.plotResults()

   plt.show()

Exercices