Aller au contenu

2021, Métropole, sujet 1, exercice 1⚓︎

Thème : Arbres binaires de recherche

Dans cet exercice, les arbres binaires de recherche de peuvent pas comporter plusieurs fois la même clé. De plus, un arbre binaire de recherche limité à un nœud a une hauteur de 1.

On considère l'arbre binaire de recherche représenté ci-dessous (figure 1), où val représente un entier :

Figure 1. Un ABR

Arbre Figure 1

Question 1a

Donner le nombre de feuilles de cet arbre et préciser leur valeur (étiquette)

Réponse

L'arbre de la figure 1 possède 4 feuilles dont les valeurs sont : \(12\), val, \(21\) et \(32\)

Question 1b

Donner le sous-arbre gauche du nœud \(23\).

Réponse

Il s'agit de l'arbre de racine 19 :

sous-arbre gauche 23

Question 1c

Donner la hauteur et la taille de l'arbre.

Réponse

L'arbre est de hauteur 4 (nombre de nœuds du chemin le plus long de la racine à une feuille) et de taille 9 (nombre de nœuds).

Question 1d

Donner les valeurs entières possibles de val pour cet arbre binaire de recherche.

Réponse

Puisque val se trouve dans le sous-arbre gauche de la racine dont la valeur est \(18\) alors les valeurs \(v\) possibles sont telles que \(v \lt 18\). Mais \(v\) est aussi dans le sous-arbre droit de l'arbre de racine \(15\) donc \(v\) vérifie aussi : \(v\gt 15\). Les valeurs entières possibles sont donc \(16\) et \(17\).

On suppose, pour la suite de cet exercice, que val est égal à \(16\).

On rappelle qu'un parcours infixe depuis un nœud consiste, dans l'ordre, à faire un parcours infixe sur le sous-arbre gauche, afficher le nœud puis faire un parcours infixe sur le sous-arbre droit.

Dans le cas d'un parcours suffixe, on fait un parcours suffixe sur le sous-arbre gauche puis un parcours suffixe sur le sous-arbre droit, avant d'afficher le nœud.

Question 2a

Donner les valeurs d'affichage des nœuds dans le cas du parcours infixe de l'arbre.

Réponse

Les valeurs dans un parcours infixe : \(12, 13, 15, 16, 18, 19, 21, 23, 32\).

Question 2b

Donner les valeurs d'affichage des nœuds dans le cas du parcours suffixe de l'arbre.

Réponse

Les valeurs dans un parcours suffixe : \(12, 13, 16, 15, 21, 19, 32, 23, 18\).

Remarque

Jusque là les questions sont simples : des questions de cours classiques.

On considère la classe Noeud définie de la façon suivante en Python :

classe Noeud
 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
class Noeud():
    def __init__(self, v):
        self.ag = None
        self.ad = None
        self.v = v

    def insere(self, v):
        n = self
        est_insere = False
        while not est_insere:
            if v == n.v:
                est_insere = True        # <------- Bloc 1
            elif v < n.v:
                if n.ag != None:         # <----
                    n = n.ag             #      |
                else:                    #      |-- Bloc 2
                    n.ag = Noeud(v)      #      |
                    est_insere = True    # <----
            else:
                if n.ad != None:         # <----
                    n = n.ad             #      |
                else:                    #      |-- Bloc 3
                    n.ad = Noeud(v)      #      |
                    est_insere = True    # <----

def insere_tout(self, vals):
    for v in vals:
        self.insere(v)
Remarque

On retrouve ici une maladresse classique dans les implémentations par classe :

  1. on amalgame arbre et nœud mais en gardant le nœud comme référence, du coup :
  2. un nœud peut être absent (None) ce qui oblige à prendre en compte ce cas particulier au lieu de manipuler des arbres vides
Question 3a

Représenter l'arbre construit suite à l'exécution de l'instruction suivante :

racine = Noeud(18)
racine.insere_tout([12, 13, 15, 16, 19, 21, 32, 23])
Réponse

Q3a

Question 3b

Écrire les deux instructions permettant de construire l'arbre de la Figure 1. On rappelle que le nombre val est égal à \(16\).

Réponse
fig_1 = Noeud(18)
fig_1.insere_tout([15, 23, 13, 16, 19, 32, 12, 21])
Question 3c

On considère l'arbre tel qu'il est représenté sur lla figure 1. Déterminer l'ordre d'exécution des blocs (repérés de 1 à 3) suite à l'application de la méthode insere(19) au nœud racine de cet arbre.

Réponse

L'appel fig_1.insere(19) provoque l'exécution des blocs dans cet ordre : bloc 3, bloc 2, bloc 1

Question 4

Écrire une méthode recherche(self, v) qui prend en argument un entier v et renvoie la valeur True si cet entier est une étiquette de l'arbre, False sinon.

Réponse
def recherche(self, v):
    if self.v == v:
        return True
    elif self.v < v:
        if self.gauche is None:
            return False
        else:
            return self.gauche.recherche(v)
    else:
        if self.droit is None:
            return False
        else:
            return self.droit.recherche(v)
Remarque

On retrouve ici l'inconvénient de devoir composer avec la valeur None. Voici une implémentation et une méthode recherche plus légères. Le nom de la classe a été changé car finalement cela correspond plus à un ABR qu'à un nœud (un nœud vide on ne sait pas bien ce que c'est).

De plus les arbres sont des structures récursives et il est dommage de ne pas les exploiter pour écrire des méthodes récursives (la méthode insere par exemple).

class ABR:

    def __init__(self, v=None):
        self.valeur = v
        if v is not None:
            self.gauche = ABR()
            self.droit = ABR()

    def est_vide(self):
        return self.valeur is None

    def insere(self, v):
        if self.est_vide():
            self.valeur = v
            self.gauche = ABR()
            self.droit = ABR()
        elif v < self.valeur:
            self.gauche.insere(v)
        else:
            self.droit.insere(v)

    def insere_tout(self, vals):
        for v in vals:
            self.insere(v)

    def recherche(self, v):
        if self.est_vide():
            return False
        elif v < self.valeur:
            self.gauche.recherche(v)
        else:
            self.droit.recherche(v)