Interface et implémentations (Bac 🎯)⚓︎
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.
Sources et crédits pour ce cours
Pour préparer ce cours, j'ai utilisé :
- le manuel NSI chez Ellipses de Balabonski, Conchon, Filliâtre, Nguyen
- le manuel NSI chez Hachette sous la direction de Michel Beaudouin Lafon
- l'article sur les arbres en NSI de Sébastien Hoarau
- le cours de mon collègue Pierre Duclosson
- les cours de Gilles Lassus et de Franck Chambon
🔖 Synthèse de ce qu'il faut retenir pour le bac
Implémentation d'un arbre binaire de recherche⚓︎
Point de cours 4
Un arbre binaire de recherche est un arbre binaire vérifiant la propriété d'arbre binaire de recherche.
Pour implémenter la structure de données arbre binaire de recherche on peut donc reprendre une implémentation d'arbre binaire. La propriété d'arbre binaire de recherche sera un invariant de la structure préservé par l'ajout ou la suppression d'un nouvel élément dans l'arbre.
À partir des implémentations proposées pour la structure d'arbre binaire on va donner deux implémentations d'arbre binaire de recherche en étendant l'interface d'arbre binaire avec de nouvelles fonctions :
- une implémentation d'arbre binaire de recherche immuable à partir d'une classe
Noeudet d'une interface fonctionnelle : chaque fonction renvoie un nouvel arbre sans modifier en place l'arbre binaire auquel elle s'applique - une implémentation d'arbre binaire de recherche mutable à partir de deux classes
NoeudetABR: les méthodes de la classeABRmodifient en place l'arbre binaire.
Arbre binaire de recherche immuable⚓︎
Méthode 1 : arbre binaire de recherche immuable
On donne ci-dessous une interface minimale d'implémentation d'arbre binaire de recherche immuable à partir d'une classe Noeud et d'une interface fonctionnelle définie en dehors de cette classe. L'arbre binaire vide est représenté par None.
###
Exercice 4
💻 Saisir ses réponses sur Capytale
Complétez l'interface précédente avec les fonctions spécifiées ci-dessous :
🐍 Script Python
def hauteur(abr):
"""Renvoie la hauteur de l'arbre binaire de recherche abr"""
# à compléter
def taille(abr):
"""Renvoie la hauteur de l'arbre binaire de recherche abr"""
# à compléter
def maximum(abr):
"""Renvoie le maximum de l'arbre binaire de recherche abr"""
# à compléter
def minimum(abr):
"""Renvoie le minimum de l'arbre binaire de recherche abr"""
# à compléter
def parcours_infixe(abr):
"""Renvoie une trace du parcours infixe de l'arbre binaire de recherche abr
dans le tableau dynamique tab"""
# à compléter
tab = []
if est_vide(abr):
return ...
tab.extend(...)
tab.append(...)
tab.extend(...)
return tab
def propriete_abr(abr, minorant=-float('inf'), majorant=float('inf')):
"""Vérifie si un arbre binaire abr
satisfait la propriete d'arbre binaire de recherche
Appel initial avec minorant=-float('inf') et majorant=float('inf')
"""
if est_vide(abr):
return True
e = element_racine(abr)
prop_gauche = propriete_abr(abr.gauche, minorant, e)
# complétez les deux lignes suivantes
prop_droit = ...
prop_racine = ...
return prop_gauche and prop_droit and prop_racine
🐍 Script Python
def hauteur(abr):
"""Renvoie la hauteur de l'arbre binaire de recherche abr"""
if est_vide(abr):
return 0
return 1 + max(hauteur(droit(abr)), hauteur(gauche(abr)))
def taille(abr):
"""Renvoie la hauteur de l'arbre binaire de recherche abr"""
if est_vide(abr):
return 0
return 1 + taille(droit(abr)) + taille(gauche(abr))
def maximum(abr):
"""Renvoie le maximum de l'arbre binaire de recherche abr"""
assert not est_vide(abr), "arbre vide"
if est_vide(abr.droit):
return abr.element
return maximum(abr.droit)
def minimum(abr):
"""Renvoie le minimum de l'arbre binaire de recherche abr"""
assert not est_vide(abr), "arbre vide"
if est_vide(abr.gauche):
return abr.element
return minimum(abr.gauche)
def parcours_infixe(abr):
"""Renvoie une trace du parcours infixe de l'arbre binaire de recherche
dans le tableau dynamique tab
"""
tab = []
if est_vide(abr):
return tab
tab.extend(parcours_infixe(abr.gauche))
tab.append(abr.element)
tab.extend(parcours_infixe(abr.droit))
return tab
def propriete_abr(abr, minorant=-float('inf'), majorant=float('inf')):
"""Vérifie si un arbre binaire abr
satisfait la propriete d'arbre binaire de recherche"""
if est_vide(abr):
return True
e = element_racine(abr)
prop_gauche = propriete_abr(abr.gauche, minorant, e)
prop_droit = propriete_abr(abr.droit, e, majorant)
prop_racine = (minorant <= e and e <= majorant)
return prop_gauche and prop_droit and prop_racine
Arbre binaire de recherche mutable⚓︎
Méthode 2 : arbre binaire de recherche mutable
On donne ci-dessous une interface minimale d'implémentation d'arbre binaire de recherche mutable à partir d'une classe Noeud et d'une classe ABR.
###
Exercice 5
💻 Saisir ses réponses sur Capytale
Dans l'interface de la classe ABR définie ci-dessus, complétez les codes des méthodes :
maximum,minimumparcours_infixehauteur,taillecompte
🐍 Script Python
class Noeud:
"""Noeud pour arbre binaire"""
def __init__(self, g, e, d):
self.gauche = g # lien vers fils gauche g éventuellement vide (None)
self.element = e # élément e stocké dans le noeud
self.droit = d # lien vers fils droit d éventuellement vide (None)
class ABR:
"""Classe d'arbre binaire de recherche mutable"""
def __init__(self):
"""Constructeur, self.racine pointe vers None si arbre vide
ou le noeud racine"""
self.racine = None
def est_vide(self):
"""Teste si l'arbre est vide, renvoie un booléen"""
return self.racine is None
def droit(self):
"""Renvoie le sous-arbre (de type Arbre) fils droit de l'arbre
Provoque une erreur si arbre est vide"""
assert not self.est_vide()
return self.racine.droit
def gauche(self):
"""Renvoie le sous-arbre (de type ABR) gauche de l'arbre
Provoque une erreur si arbre est vide"""
assert not self.est_vide()
return self.racine.gauche
def element_racine(self):
"""Renvoie l'élément stocké dans le noeud racine de l'arbre
Provoque une erreur si arbre est vide"""
assert not self.est_vide()
return self.racine.element
# extension de l'interface
def parcours_infixe(abr):
"""Renvoie une trace du parcours infixe de l'arbre binaire de recherche
dans le tableau dynamique tab
"""
tab = []
if self.est_vide():
return tab
tab.extend(self.gauche().parcours_infixe())
tab.append(self.element_racine())
tab.extend(self.droit().parcours_infixe())
return tab
def minimum(self):
"""Renvoie le minimum de l'ensemble des éléments
stockés dans l'arbre"""
assert not self.est_vide(), "arbre vide"
if self.gauche().est_vide():
return self.element_racine()
else:
return self.gauche().minimum()
def maximum(self):
"""Renvoie le maximum de l'ensemble des éléments
stockés dans l'arbre"""
assert not self.est_vide(), "arbre vide"
if self.racine.droit.est_vide():
return self.racine.element
else:
return self.racine.droit.maximum()
def taille(self):
"""Renvoie la taille de l'arbre binaire de recherche"""
if self.est_vide():
return 0
return 1 + self.gauche().taille() + self.droit().taille()
def hauteur(self):
"""Renvoie la hauteur de l'arbre binaire de recherche"""
if self.est_vide():
return 0
return 1 + max(self.gauche().hauteur(), self.droit().hauteur())
def compte(self, elt):
"""Renvoie le nombre d'occurrences de elt dans l'arbre
"""
if self.est_vide():
return 0
c = 0
if self.element_racine() == elt:
c = c + 1
if self.element_racine() <= elt:
c = c + self.droit().compte(elt)
if self.element_racine() >= elt:
c = c + self.gauche().compte(elt)
return c
def __str__(self):
"""Affichage joli d'un arbre binaire construit avec la classe Noeud
Analogue à la fonction builtin str"""
def aux(arbre):
"""Fonction récursive auxiliaire"""
if arbre.est_vide():
return ['']
lignes_sag = aux(arbre.gauche())
lignes_sad = aux(arbre.droit())
decalage_horizontal = 2 + len(str(arbre.element_racine()))
rep = str(arbre.element_racine()) + '_' * 2 + lignes_sag[0] + '\n'
for ligne in lignes_sag[1:]:
rep = rep + '|' + ' ' * (decalage_horizontal - 1) + ligne + '\n'
rep = rep + '|\n'
rep = rep + '|' + '_' * (decalage_horizontal - 1) + lignes_sad[0] + '\n'
for ligne in lignes_sad[1:]:
rep = rep + ' ' * decalage_horizontal + ligne + '\n'
rep = rep.rstrip()
return rep.split('\n')
rep = aux(self)
return '\n'.join(rep)