Exercice 3 · Bac Numérique et Sciences Informatiques Polynésie 2021 (jour 2)

EXERCICE 3: Arbre binaire de recherche (4 points)

Cet exercice traite principalement du thème « algorithmique, langages et programmation » et en particulier les arbres binaires de recherche. La première partie aborde les arbres en mode débranché via l'application d'un algorithme sur un exemple. La suivante porte sur la programmation orientée objet. La dernière partie fait le lien avec les algorithmes de tri.

Partie A: Étude d'un exemple

Considérons l'arbre binaire de recherche ci-dessous.

1.

Indiquer quelle valeur a le nœud racine et quels sont les fils de ce nœud.

2.

Indiquer quels sont les nœuds de la branche qui se termine par la feuille qui a pour valeur 3.

3.

Dessiner l'arbre obtenu après l'ajout de la valeur 6.

Partie B: Implémentation en Python

Voici un extrait d'une implémentation en Python d'une classe modélisant un arbre binaire de recherche.

class ABR:

"""Implémentation d'un arbre binaire de recherche (ABR) """

def __init__(self, valeur=None):

self.valeur = valeur

self.fg = None

self.fd = None

def estVide(self):

return self.valeur == None

def insererElement(self, e):

if self.estVide():

self.valeur = e

else:

if e < self.valeur:

if self.fg:

self.fg.insererElement(e)

else:

self.fg = ABR(e)

if e > self.valeur:

if self.fd:

self.fd.insererElement(e)

else:

self.fd = ABR(e)

1.

Expliquer le rôle de la fonction __init__.

2.

Dans cette implémentation, expliquer ce qui se passe si on ajoute un élément déjà présent dans l'arbre.

3.

Recopier et compléter les lignes de code surlignées ci-dessous permettant de créer l'arbre de la partie A.

arbre = ABR(

)

arbre.insererElement(2)

arbre.insererElement(

)

arbre.insererElement(7)

arbre.insererElement(

)

Partie C: Tri par arbre binaire de recherche

On souhaite trier un ensemble de valeurs entières distinctes grâce à un arbre binaire de recherche. Pour cela, on ajoute un à un les éléments de l'ensemble dans un arbre initialement vide. Il ne reste plus qu'à parcourir l'arbre afin de lire et de stocker dans un tableau résultat les valeurs dans l'ordre croissant.

1.

Donner le nom du parcours qui permet de visiter les valeurs d'un arbre binaire de recherche dans l'ordre croissant.

2.

Comparer la complexité de cette méthode de tri avec celle du tri par insertion ou du tri par sélection.