Aller au contenu

Arbres binaires de recherche et programmation orientée objet⚓︎

D'après 2023, Sujet 0.a, Ex. 3

Dans un entrepôt de e-commerce, un robot mobile autonome exécute successivement les tâches qu'il reçoit tout au long de la journée.

La mémorisation et la gestion de ces tâches sont assurées par une structure de données.

1. Dans l'hypothèse où les tâches devraient être extraites de cette structure (pour être exécutées) dans le même ordre qu'elles ont été mémorisées, préciser si ce fonctionnement traduit le comportement d'une file ou d'une pile. Justifier.

Réponse

Ce fonctionnement traduit le comportement d'une file, c'est-à-dire que le premier élément qui entre dans la structure de données est aussi le premier à en sortir (FIFO pour First In, First Out).

Dans une pile, le dernier élément entré est le premier à sortir (LIFO pour Last In, First Out).

En réalité, selon l'urgence des tâches à effectuer, on associe à chacune d'elles, lors de la mémorisation, un indice de priorité (nombre entier) distinct : il n'y a pas de valeur en double.

Plus cet indice est faible, plus la tâche doit être traitée prioritairement.

La structure de données retenue est assimilée à un arbre binaire de recherche (ABR) dans lequel chaque nœud correspond à une tâche caractérisée par son indice de priorité.

Rappel

Dans un arbre binaire de recherche, chaque nœud est caractérisé par une valeur (ici l'indice de priorité), telle que chaque nœud du sous-arbre à gauche a une valeur strictement inférieure à celle du nœud considéré, et que chaque nœud du sous-arbre à droite possède une valeur strictement supérieure à celle-ci.

Cette structure de données présente l'avantage de mettre efficacement en œuvre l'insertion ou la suppression de nœuds, ainsi que la recherche d'une valeur.

Par exemple, le robot a reçu successivement, dans l'ordre, des tâches d'indice de priorité 12, 6, 10, 14, 8 et 13. En partant d'un arbre binaire de recherche vide, l'insertion des différentes priorités dans cet arbre donne la figure 1.

Figure 1

    graph TD
    N("12") --> Ng("6")
    N       --> Nd("14")
    Ng --> Ngg(" ")
    Ng --> Ngd("10")
    Ngd --> Ngdg("8")
    Ngd --> Ngdd(" ")
    Nd --> Ndg("13")
    Nd --> Ndd(" ")
    style Ngg fill:none, stroke-width:0px
    style Ngdd fill:none, stroke-width:0px
    style Ndd fill:none, stroke-width:0px

    linkStyle 2 stroke-width:0px
    linkStyle 5 stroke-width:0px
    linkStyle 7 stroke-width:0px

2. En utilisant le vocabulaire couramment utilisé pour les arbres, préciser le terme qui correspond :

2.a) au nombre de tâches restant à effectuer, c'est-à-dire le nombre total de nœuds de l'arbre ;

2.b) au nœud représentant la tâche restant à effectuer la plus ancienne ;

2.c) au nœud représentant la dernière tâche mémorisée (la plus récente).

Réponses

2.a) C'est la taille de l'arbre ; c'est-à-dire le nombre total de nœuds de l'arbre.

2.b) C'est la racine de l'arbre puisqu'il s'agit de la tâche ajoutée à l'arbre en premier.

2.c) C'est une feuille de l'arbre. Il n'y a pas d'autre nœud que lui même dans l'arborescence d'une feuille.

3. Lorsque le robot reçoit une nouvelle tâche, on déclare un nouvel objet, instance de la classe Noeud, puis on l'insère dans l'arbre binaire de recherche (instance de la classe ABR) du robot. Ces 2 classes sont définies comme suit :

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Noeud:
    """ Tache à accomplir et ses liens avec les autres """

    def __init__(self, tache, indice):
        self.tache = tache
        self.indice = indice
        self.gauche = ABR()
        self.droite = ABR()


class ABR: 
    """ arbre binaire de recherche initialement vide """

    def __init__(self): 
        self.racine = None  # modélisation de l'arbre vide
        # Remarque : si l'arbre n'est pas vide,
        #    racine est une instance de la classe Noeud

    def est_vide(self): 
        """ Détermine si l'arbre auto-référencé est vide """
        return self.racine == None

    def insere(self, nouveau_noeud):
        """ Insère un nouveau nœud,
          instance de la classe Noeud, dans l'ABR
        """
        if self.est_vide():
            self.racine = nouveau_noeud
        elif self.racine.indice ...... nouveau_noeud.indice
            self.racine.gauche.insere(nouveau_noeud)
        else: 
            self.racine.droite.insere(nouveau_noeud)

3.a) Donner les noms des attributs de la classe Noeud.

3.b) Expliquer en quoi la méthode insere est dite récursive et justifier rapidement qu'elle se termine.

3.c) Indiquer le symbole de comparaison manquant dans le test à la ligne 29 de la méthode insere pour que l'arbre binaire de recherche réponde bien à la définition de l'encadré « Rappel » précédent.

3.d) On considère le robot dont la liste des tâches est représentée par l'arbre de la figure 1. Ce robot reçoit, successivement et dans l'ordre, des tâches d'indice de priorité 11, 5, 16 et 7, sans avoir accompli la moindre tâche entretemps.

Recopier et compléter la figure 1 après l'insertion de ces nouvelles tâches.

Réponses

3.a) Les attributs de la classe Noeud sont tache, indice, gauche et droite.

3.b) La méthode insere est récursive car elle contient un appel à elle-même dans sa définition. Elle se termine car à chaque appel on descend d'un niveau dans l'arbre, ou bien on arrive dans un ABR vide.

3.c) On insère à gauche lorsque l'indice du nœud à insérer est inférieur à celui du noeud courant donc on complète la ligne 29 par :

🐍 Script Python
elif self.racine.indice > nouveau_noeud.indice

Il n'y a pas de cas d'égalité, les indices sont distincts. Ainsi, dans le cas contraire, on insère à droite un nœud d'indice supérieur.

3.d)

État initial

    graph TD
    N("12") --> Ng("6")
    N       --> Nd("14")
    Ng --> Ngg(" ")
    Ng --> Ngd("10")
    Ngd --> Ngdg("8")
    Ngd --> Ngdd(" ")
    Nd --> Ndg("13")
    Nd --> Ndd(" ")
    style Ngg fill:none, stroke-width:0px
    style Ngdd fill:none, stroke-width:0px
    style Ndd fill:none, stroke-width:0px

    linkStyle 2 stroke-width:0px
    linkStyle 5 stroke-width:0px
    linkStyle 7 stroke-width:0px

Après l'insertion de 11

    graph TD
    N("12") --> Ng("6")
    N       --> Nd("14")
    Ng --> Ngg(" ")
    Ng --> Ngd("10")
    Ngd --> Ngdg("8")
    Ngd --> Ngdd("11")
    Nd --> Ndg("13")
    Nd --> Ndd(" ")
    style Ngg fill:none, stroke-width:0px
    style Ndd fill:none, stroke-width:0px

    linkStyle 2 stroke-width:0px
    linkStyle 7 stroke-width:0px

Après l'insertion de 5

    graph TD
    N("12") --> Ng("6")
    N       --> Nd("14")
    Ng --> Ngg("5")
    Ng --> Ngd("10")
    Ngd --> Ngdg("8")
    Ngd --> Ngdd("11")
    Nd --> Ndg("13")
    Nd --> Ndd(" ")

    style Ndd fill:none, stroke-width:0px
    linkStyle 7 stroke-width:0px

Après l'insertion de 16

    graph TD
    N("12") --> Ng("6")
    N       --> Nd("14")
    Ng --> Ngg("5")
    Ng --> Ngd("10")
    Ngd --> Ngdg("8")
    Ngd --> Ngdd("11")
    Nd --> Ndg("13")
    Nd --> Ndd("16")

Après l'insertion de 7

    graph TD
    N("12") --> Ng("6")
    N       --> Nd("14")
    Ng --> Ngg("5")
    Ng --> Ngd("10")
    Ngd --> Ngdg("8")
    Ngdg --> Ngdgg("7")
    Ngdg --> Ngdgd(" ")
    Ngd --> Ngdd("11")
    Nd --> Ndg("13")
    Nd --> Ndd("16")

    style Ngdgd fill:none, stroke-width:0px
    linkStyle 6 stroke-width:0px

4. Avant d'insérer une nouvelle tâche dans l'arbre binaire de recherche, on s'assure que son indice de priorité n'est pas déjà présent.

Écrire une méthode est_present de la classe ABR qui répond à la description :

🐍 Script Python
def est_present(self, indice_recherche) : 
    """ Détermine si l'indice de priorité indice_recherche (int),
    passé en paramètre, est déjà l'indice d'un nœud de l'arbre.

    Renvoie un booléen.
    """
Réponse
🐍 Script Python
def est_present(self,indice_recherche):
    """ Détermine si l'indice de priorité indice_recherche (int),
    passé en paramètre, est déjà l'indice d'un nœud de l'arbre.

    Renvoie un booléen.
    """
    if self.est_vide():
        return False
    else:
        if self.racine.indice > indice_recherche:
            return self.racine.gauche.est_present()
        elif self.racine.indice < indice_recherche:
            return self.racine.droite.est_present()
        else:  # cas d'égalité
            return True

5. Comme le robot doit toujours traiter la tâche dont l'indice de priorité est le plus petit, on envisage un parcours infixe de l'arbre binaire de recherche.

5.a) Donner l'ordre des indices de priorité obtenus à l'aide d'un parcours infixe de l'arbre binaire de recherche de la figure 1.

5.b) Expliquer comment exploiter ce parcours pour déterminer la tâche prioritaire.

Réponses

5.a) On rappelle que dans un parcours infixe, on parcourt le sous arbre à gauche, puis la racine, puis le sous arbre à droite.

Dans le cas de l'arbre de la figure 1, on obtient : 6 → 8 → 10 → 12 → 13 → 14

5.b) La tâche prioritaire peut être obtenue avec la première tâche affichée.

6. Afin de ne pas parcourir tout l'arbre, il est plus efficace de rechercher la tâche du nœud situé le plus à gauche de l'arbre binaire de recherche : il correspond à la tâche prioritaire.

Recopier et compléter la méthode récursive tache_prioritaire de la classe ABR :

🐍 Script Python
def tache_prioritaire(self): 
    """ Renvoie la tache du noeud situé le plus 
    à gauche de l'ABR supposé non vide
    """
    if self.racine. ......... .est_vide():  # pas de nœud plus à gauche
        return self.racine. .........
    else: 
        return self.racine.gauche. .........()
Réponse
🐍 Script Python
def tache_prioritaire(self):
    """ Renvoie la tache du noeud situé le plus 
    à gauche de l'ABR supposé non vide
    """
    if self.racine.gauche.est_vide():
        return self.racine.tache
    else:
        return self.racine.gauche.tache_prioritaire()

7. Une fois la tâche prioritaire effectuée, il est nécessaire de supprimer le nœud correspondant pour que le robot passe à la tâche suivante :

  • Si le nœud correspondant à la tâche prioritaire est une feuille, alors il est simplement supprimé de l'arbre (cette feuille devient un arbre vide)
  • Si le nœud correspondant à la tâche prioritaire a un sous-arbre à droite non vide, alors ce sous-arbre à droite remplace le nœud prioritaire qui est alors écrasé, même s'il s'agit de la racine.

Dessiner alors, pour chaque étape, l'arbre binaire de recherche (seuls les indices de priorités seront représentés) obtenu pour un robot, initialement sans tâche, et qui a, successivement dans l'ordre :

  • étape 1 : reçu une tâche d'indice de priorité 14 à accomplir
  • étape 2 : reçu une tâche d'indice de priorité 11 à accomplir
  • étape 3 : reçu une tâche d'indice de priorité 8 à accomplir
  • étape 4 : accompli sa tâche prioritaire
  • étape 5 : reçu une tâche d'indice de priorité 12 à accomplir
  • étape 6 : accompli sa tâche prioritaire
  • étape 7 : accompli sa tâche prioritaire
  • étape 8 : reçu une tâche d'indice de priorité 15 à accomplir
  • étape 9 : reçu une tâche d'indice de priorité 19 à accomplir
  • étape 10 : accompli sa tâche prioritaire
Réponse

Étape 1 : ajout de 14

    graph TD
    N("14")

Étape 2 : ajout de 11

    graph TD
    N("14")
    N --> Ng("11")
    N --> Nd(" ")
    style Nd fill:none, stroke-width:0px
    linkStyle 1 stroke-width:0px

Étape 3 : ajout de 8

    graph TD
    N("14")
    N --> Ng("11")
    N --> Nd(" ")
    Ng --> Ngg("8")
    Ng --> Ngd(" ")
    style Nd fill:none, stroke-width:0px
    linkStyle 1 stroke-width:0px
    style Ngd fill:none, stroke-width:0px
    linkStyle 3 stroke-width:0px

Étape 4 : traiter 8 qui est prioritaire

    graph TD
    N("14")
    N --> Ng("11")
    N --> Nd(" ")
    style Nd fill:none, stroke-width:0px
    linkStyle 1 stroke-width:0px

Étape 5 : ajout de 12

    graph TD
    N("14")
    N --> Ng("11")
    N --> Nd(" ")
    Ng --> Ngg(" ")
    Ng --> Ngd("12")
    style Nd fill:none, stroke-width:0px
    linkStyle 1 stroke-width:0px
    style Ngg fill:none, stroke-width:0px
    linkStyle 2 stroke-width:0px

Étape 6 : traiter 11 qui est prioritaire

    graph TD
    N("14")
    N --> Ng("12")
    N --> Nd(" ")
    style Nd fill:none, stroke-width:0px
    linkStyle 1 stroke-width:0px

Étape 7 : traiter 12 qui est prioritaire

    graph TD
    N("14")

Étape 8 : ajout de 15

    graph TD
    N("14")
    N --> Ng(" ")
    N --> Nd("15")
    style Ng fill:none, stroke-width:0px
    linkStyle 0 stroke-width:0px

Étape 9 : ajout de 19

    graph TD
    N("14")
    N --> Ng(" ")
    N --> Nd("15")
    Nd --> Ndg(" ")
    Nd --> Ndd("19")
    style Ng fill:none, stroke-width:0px
    linkStyle 0 stroke-width:0px
    style Ndg fill:none, stroke-width:0px
    linkStyle 2 stroke-width:0px

Étape 10 : traiter 14 qui est prioritaire

    graph TD
    N("15")
    N --> Ng(" ")
    N --> Nd("19")
    style Ng fill:none, stroke-width:0px
    linkStyle 0 stroke-width:0px