Exercice 3 · Bac Numérique et Sciences Informatiques Liban 2023 (jour 2)

Exercice 3 (5 Points)

Cet exercice traite des arbres et de l'algorithmique.

Dans cet exercice, la taille d'un arbre est égale au nombre de ses nœuds et on convient que la hauteur d'un arbre ne contenant qu'un nœud vaut 1.

On utilisera la définition suivante: un arbre binaire de recherche (ABR) est un arbre binaire dans lequel:

on peut comparer les valeurs des nœuds: ce sont par exemple des nombres entiers, ou des lettres de l'alphabet;

si $x$ est un nœud de cet arbre et $y$ est un nœud du sous-arbre gauche de $x$, alors il faut que $y.\text{valeur} < x.\text{valeur}$;

si $x$ est un nœud de cet arbre et $y$ est un nœud du sous-arbre droit de $x$, alors il faut que $y.\text{valeur} \ge x.\text{valeur}$.

1.

Parmi les trois arbres dessinés ci-dessous, recopier sur la copie le numéro correspondant à celui qui n'est pas un arbre binaire de recherche. Justifier.

Une classe ABR, qui implémente une structure d'arbre binaire de recherche, possède l'interface suivante:

class ABR:

def __init__(self, valeur, sa_gauche, sa_droit):

self.valeur = valeur # valeur de la racine

self.sa_gauche = sa_gauche # sous-arbre gauche

self.sa_droit = sa_droit # sous-arbre droit

def inserer_noeud(self, valeur):

"""Renvoie un nouvel ABR avec le nœud de valeur 'valeur'

inséré comme nouvelle feuille à sa position correcte"""

# code non étudié dans cet exercice On prendra la valeur None pour représenter un sous-arbre vide.

2.

La construction d'un ABR se fait en insérant progressivement les valeurs à partir de la racine: la méthode inserer_noeud place ainsi un nœud à sa « bonne place » comme feuille dans la structure, sans modifier le reste de la structure. On admet que la position de cette feuille est unique.

a.

En utilisant les méthodes de la classe ABR:

écrire l'instruction Python qui permet d'instancier un objet a0, de type ABR, ayant un seul nœud (la racine) de valeur 18.

écrire une séquence d'instructions qui permet ensuite d'insérer dans l'objet a0 les deux feuilles de l'arbre de valeurs 12 et 36.

Selon l'ordre dans lequel les valeurs sont insérées, on construit des ABR ayant des structures différentes. Voilà par exemple ci-dessous un ABR (nommé a1) obtenu en créant une instance de type ABR ayant un seul nœud (la racine) de valeur 24 puis en insérant successivement les valeurs dans l'ordre suivant: 21; 35; 19; 23; 32; 39; 3; 20.

b.

Dessiner sur la copie l'ABR (nommé a2) que l'on obtiendrait en créant une instance de type ABR ayant un seul nœud (la racine) de valeur 3 puis en insérant successivement les valeurs dans l'ordre suivant: 20; 19; 21; 23; 32; 24; 35; 39.

c.

Donner la hauteur des ABR a1 et a2.

d.

On complète la classe ABR avec une méthode calculer_hauteur qui renvoie la hauteur de l'arbre. Recopier sur la copie les lignes 10 et 13 en les complétant par des commentaires et la ligne 14 en la complétant par une instruction dans le code ci-après de cette méthode. On pourra utiliser la fonction Python max.

def calculer_hauteur(self):

"""Renvoie la hauteur de l'arbre"""

if self.sa_droit is None and self.sa_gauche is None:

# l'arbre est réduit à une feuille

return 1

elif self.sa_droit is None:

# arbre avec une racine et seulement un sous-arbre gauche

return 1 + self.sa_gauche.calculer_hauteur()

elif self.sa_gauche is None:

# Ligne 10: à compléter

return 1 + self.sa_droit.calculer_hauteur()

else:

# Ligne 13: à compléter

return à compléter # Ligne 14

3.

La différence de hauteur entre l'ABR a1 et l'ABR a2 aura des conséquences lors de la recherche d'une valeur dans l'ABR.

a.

Recopier et compléter sur la copie les lignes 6, 8, 11 et 13 du code ci-dessous de la méthode rechercher_valeur, qui permet de tester la présence ou l'absence d'une valeur donnée dans l'ABR:

def rechercher_valeur(self, v):

"""Renvoie True si la valeur v est trouvée dans l'ABR, False sinon"""

if...: # Ligne 6

return True

elif... and self.sa_gauche is not None: # Ligne 8

return self.sa_gauche.rechercher_valeur(v)

elif v > self.valeur and self.sa_droit is not None:

return... # Ligne 11

else:

return... # Ligne 13

b.

On admet que le nombre de fois où la méthode rechercher_valeur est appelée pour rechercher la valeur 39 dans l'ABR a2 est 7. Donner le nombre de fois où la méthode rechercher_valeur est appelée pour rechercher la valeur 20 dans l'ABR a1.

4.

Il existe des algorithmes pour modifier la structure d'un ABR, afin par exemple de diminuer la hauteur d'un ABR; on s'intéresse aux algorithmes appelés rotation, consistant à faire « pivoter » une partie de l'arbre autour d'un de ses nœuds. L'exemple ci-dessous permet d'expliquer l'algorithme pour réaliser une rotation droite d'un ABR autour de sa racine:

On admet que ces transformations conservent la propriété d'ABR de l'arbre. La méthode rotation_droite ci-après renvoie une nouvelle instance de type ABR, correspondant à une rotation droite de l'objet de type ABR à partir duquel elle est appelée:

def rotation_droite(self):

"""Renvoie une instance d'un ABR apres une rotation droite

On suppose qu'il existe un sous-arbre gauche"""

pivot = self.sa_gauche

self.sa_gauche = pivot.sa_droit

pivot.sa_droit = self

return ABR(pivot.valeur, pivot.sa_gauche, pivot.sa_droit) Pour réaliser une rotation gauche, on suivra alors l'algorithme suivant:

on appelle pivot le sous-arbre droit de la racine de l'arbre,

le sous-arbre gauche du pivot devient le sous-arbre droit de la racine,

la racine ainsi modifiée devient le sous-arbre gauche du pivot et la racine du pivot devient la nouvelle racine de l'ABR.

a.

En suivant les différentes étapes de cet algorithme, dessiner l'arbre obtenu après une rotation gauche de l'ABR suivant:

b.

Écrire le code d'une méthode Python rotation_gauche qui réalise la rotation gauche d'un ABR autour de sa racine.