Aller au contenu

Interface et implémentations (Bac 🎯)⚓︎

Licence Creative Commons
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.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

🔖 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 Noeud et 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 Noeud et ABR : les méthodes de la classe ABR modifient 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.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞

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.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞

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, minimum
  • parcours_infixe
  • hauteur, taille
  • compte
🐍 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)