Recherche et ajout (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.

programme

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

Recherche d'un élément dans un arbre binaire de recherche⚓︎

Point de cours 4 : recherche dans un ABR

Avertissement

Dans cette partie on considère des arbres binaires de recherche tels que pour chacun des sous-arbres l'élément stocké dans le noeud racine est supérieur ou égal à tous les éléments stockés dans les noeuds de son sous-arbre gauche et inférieur strictement à tous les éléments stockés dans les noeuds de son sous-arbre droit.

Pour rechercher un élément dans un arbre binaire présentant la propriété d'arbre binaire de recherche on exploite cette propriété pour procéder récursivement à l'instar d'une recherche dichotomique dans un tableau trié en éliminant une partie des noeuds restants chaque fois que la recherche doit se poursivre :

Étape 1 : Si l'arbre est vide, alors on termine la recherche et on renvoie False, sinon on compare l'élément stocké dans le noeud racine à l'élément cherché et on passe à l'étape 2.
Étape 2 : Trois alternatives sont possibles en fonction de la comparaison de l'élément stocké dans le noeud racine avec l'élément cherché.
- S'ils sont égaux, alors on termine la recherche et on renvoie True.
- Si l'élément cherché est inférieur à l'élément stocké dans le noeud racine, alors on poursuit la recherche dans le fils/sous-arbre gauche et on revient à l'étape 1 (appel récursif).
- Sinon, alors on poursuit la recherche dans le fils/sous-arbre droit et on revient à l'étape 1 (appel récursif).

⏱️ Complexité

⚠️ Pour simplifier, on considère que le coût de la comparaison de deux éléments est constant, dans notre étude de complexité on ne prend donc en compte que le nombre de comparaisons.

Le nombre de comparaisons effectuées lors de la recherche d'un élément dans un arbre binaire de recherche est au plus égal au nombre de noeuds dans le plus long chemin reliant la racine à une feuille. La complexité en temps de la recherche est donc majorée par une constante fois la hauteur de l'arbre binaire de recherche. On rappelle que la hauteur \(h\) d'un arbre binaire de taille \(n\) vérifie l'inégalité \(\log_{2}(n)< h \leqslant n\). La complexité en temps de la recherche dans un arbre binaire de recherche dépend donc de la forme de l'arbre, avec deux cas extrêmes :

Pire forme : dans un arbre binaire dégénéré, par un exemple un peigne, on aura une complexité linéaire en \(O(n)\) comme pour une recherche séquentielle dans une liste chaînée.
Meilleure forme : dans un arbre binaire presque complet ou parfait, on aura une complexité logarithmique, en \(O(\log_{2}(n))\) donc bien meilleure.

Forme de l'arbre binaire	Complexité de la recherche d'un élément par rapport à la taille
dégénéré	linéaire
presque complet ou parfait	logarithmique

Exercice 6

💻 Saisir ses réponses sur Capytale

Dans cet exercice, vous allez programmer la recherche d'un élément dans un arbre binaire de recherche pour les deux implémentations présentées précédemment.

Question 1

énoncésolution

Complétez le code de la fonction recherche dans l'interface fonctionnelle de l'implémentation d'arbre binaire immuable donnée ci-dessous.

Code

###

class Noeud:bksl-nl """Classe de noeud pour arbre binaire"""bksl-nl bksl-nl def py-undpy-undinitpy-undpy-und(self, g, e, d):bksl-nl self.gauche = g # lien vers fils gauche g éventuellement vide (None)bksl-nl self.element = e # élément e stocké dans le noeudbksl-nl self.droit = d # lien vers fils droit d éventuellement vide (None)bksl-nl bksl-nl# Interface fonctionnelle minimale pour Arbre Binaire de Recherchebksl-nlbksl-nldef abrpy-undvide():bksl-nl """Renvoie un arbre binaire de recherche vide représenté par None"""bksl-nl return Nonebksl-nlbksl-nldef estpy-undvide(abr):bksl-nl """Teste si un arbre binaire de recherche est vide, renvoie un booléen"""bksl-nl return abr is Nonebksl-nlbksl-nldef gauche(abr):bksl-nl """Renvoie le sous-arbre fils gauche de l'arbre binaire de recherche abrbksl-nl Provoque une erreur si arbre est vide"""bksl-nl assert not estpy-undvide(abr), "Arbre vide"bksl-nl return abr.gauchebksl-nlbksl-nldef droit(abr):bksl-nl """Renvoie le sous-arbre fils droit de l'arbre binaire de recherche abrbksl-nl Provoque une erreur si arbre est vide"""bksl-nl assert not estpy-undvide(abr), "Arbre vide"bksl-nl return abr.droitbksl-nlbksl-nldef elementpy-undracine(abr):bksl-nl """Renvoie l'élément à la racine de l'arbre binaire de recherche abrbksl-nl Provoque une erreur si arbre est vide"""bksl-nl assert not estpy-undvide(abr), "Arbre vide"bksl-nl return abr.elementbksl-nlbksl-nl# Extension de l'interface bksl-nldef recherche(abr, elt):bksl-nl """Renvoie un booléen indiquant si elt est stocké dans un noeudbksl-nl de l'arbre binaire de recherche abrbksl-nl """bksl-nl if estpy-undvide(abr):bksl-nl return Falsebksl-nl elif elt < abr.element:bksl-nl return recherche(abr.gauche, elt)bksl-nl # à compléterbksl-nl bksl-nl bksl-nldef afficherpy-undarbre(abr):bksl-nl """Affichage syntaxiquement correct d'un arbre binaire de recherche abr construit avec la classe Noeudbksl-nl Analogue à la fonction builtin repr"""bksl-nl if estpy-undvide2(abr):bksl-nl return repr(None)bksl-nl return f"Noeud({afficherpy-undarbre(abr.gauche)}, {repr(abr.element)}, {afficherpy-undarbre(abr.droit)})"bksl-nlbksl-nldef testpy-undabrpy-undimmuable2():bksl-nl a = Noeud(Noeud(None, 4, Noeud(None, 6, None)), 8, Noeud(Noeud(None, 9, None), 10, Noeud(None, 12, None)))bksl-nl assert recherche(a, 8) == Truebksl-nl assert recherche(a, 6) == Truebksl-nl assert recherche(a, 12) == Truebksl-nl assert recherche(a, 13) == Falsebksl-nl assert recherche(a, 7) == Falsebksl-nl print("Tests réussis")bksl-nlbksl-nl

🐍 Script Python

def recherche(abr, elt):
    """Renvoie un booléen indiquant si elt est stocké dans un noeud 
    de l'arbre binaire de recherche abr
    """
    if est_vide(abr):
        return False
    elif elt < abr.element:
        return recherche(abr.gauche, elt)
    elif elt > abr.element:
        return recherche(abr.droit, elt)
    else:
        return True

Question 2

énoncésolution

Complétez le code de la méthode recherche dans l'interface POO de l'implémentation d'arbre binaire mutable donnée ci-dessous.

Code

🐍 Script Python

class Noeud:
    """classe 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 mutable"""
    
    def __init__(self):
        """Constructeur, self.racine point 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 recherche(self, elt):
        """
        Renvoie True si element dans l'arbre binaire de recherche
        et False sinon        
        """
        if self.est_vide(): # cas de l'arbre vide
            return False
        elif elt < self.element_racine():
            return self.gauche().recherche(elt)
        # à compléter   

# tests unitaires
def test_abr_mutable():
    a = ABR()
    a.racine = Noeud(ABR(), 6,  ABR())
    b = ABR()
    b.racine = Noeud(ABR(), 4, a)
    c = ABR()
    c.racine = Noeud(ABR(), 9, ABR())
    d = ABR()
    d.racine = Noeud(ABR(), 12, ABR())
    e = ABR()
    e.racine = Noeud(c, 10, d)
    f = ABR()
    f.racine = Noeud(b, 8, e)
    assert a.recherche(8) == True
    assert a.recherche(6) == True
    assert a.recherche(12) == True
    assert a.recherche(13) == False
    assert  a.recherche(7) == False
    print("Tests réussis")

🐍 Script Python

def recherche(self, elt):
    """
    Renvoie True si element dans l'arbre binaire de recherche
    et False sinon        
    """
    if self.est_vide(): # cas de l'arbre vide
        return False
    elif elt < self.element_racine():
        return self.gauche().recherche(elt)
    elif elt > self.element_racine():
        return self.droit().recherche(elt)
    else:
        return True

Ajout d'un élément dans un arbre binaire de recherche⚓︎

Point de cours 5 : ajout dans un ABR

Pour ajouter un élément dans un arbre binaire présentant la propriété d'arbre binaire de recherche on effectue la même descente dans l'arbre que pour la recherche. Deux situations finales sont possibles :

Situation 1 : on atteint un arbre dont le noeud racine contient déjà l'élément stocké, dans ce cas :
- si on ne veut pas de doublons dans l'arbre binaire initial : on termine sans rien faire
- si on accepte les doublons dans l'arbre binaire initial : on poursuit alors l'ajout dans le fils/sous-arbre gauche
Situation 2 : on atteint un arbre vide :
- on crée alors à cet emplacement libre un arbre binaire dont le noeud racine contient l'élément

Différence entre arbres binaires immuables ou mutables

Si on implémente un arbre binaire immuable alors on renvoie un nouvel arbre binaire avec le constructeur de la classe Noeud lors de l'ajout d'un élément.

Si on implémente un arbre binaire mutable alors on ajoute l'élément en modifiant en place l'arbre auquel on rajoute un nouveau sous-arbre.¹

⏱️ Complexité

⚠️ Pour simplifier, on considère que le coût de la comparaison de deux éléments est constant, dans notre étude de complexité on ne prend donc en compte que le nombre de comparaisons.

Le nombre de comparaisons effectuées lors de la descente dans l'arbre est le même que pour la recherche. La complexité en temps de l'ajout est donc majorée par une constante fois la hauteur de l'arbre binaire de recherche.

Forme de l'arbre binaire	Complexité de l'ajout d'un élément par rapport à la taille
dégénéré	linéaire
presque complet ou parfait	logarithmique

L'ajout (comme la suppression) d'éléments dans l'arbre va modifier sa forme. Par exemple si on ajoute des éléments dans l'ordre croissant, on obtiendra un peigne droit. Or on veut maintenir une hauteur proche de l'optimum \(\log_{2}(n)\) où \(n\) est la taille de l'arbre. Différentes techniques de réarrangement des noeuds au cours d'un ajout (ou d'une suppression) permettent de maintenir un arbre équilibré, ou presque, tout en gardant une complexité logarithmique. ²

Exercice 7

Dans cet exercice, on utilisera le verbe insérer plutôt qu'ajouter (implicitement on peut imaginer qu'on manipule plutôt un arbre binaire mutable).

On veut insérer dans un arbre binaire de recherche vide les éléments entiers de l'ensemble \(\{8, 4, -1, 5, 17, 7, 13\}\). On va illustrer sur quelques exemples que l'ordre d'insertion détermine la forme de l'arbre binaire et donc la complexité des opérations de recherche ou d'ajout/insertion.

Question 1

énoncésolution

Quel arbre binaire obtient-on si on insère les éléments dans l'ordre de la séquence \([8, 4, -1, 5, 17, 7, 13]\) ?

alt

Question 2

énoncésolution

Quel arbre binaire obtient-on si on insère les éléments dans l'ordre croissant ?

On obtient un arbre binaire peigne à droite.

alt

Question 3

énoncésolution

Quel arbre binaire obtient-on si on insère les éléments dans l'ordre décroissant ?

On obtient un arbre binaire peigne à gauche.

alt

Question 4

énoncésolution

Donnez un ordre d'insertion permettant d'obtenir un arbre binaire parfait à partir des éléments de l'ensemble \(\{8, 4, -1, 5, 17, 7, 13\}\).

On a besoin de \(2^{3}-1=7\) noeuds donc on peut construire un arbre parfait de hauteur \(3\). Pour celà on peut d'abord trier les éléments dans l'ordre croissant. Ensuite on applique l'algorithme suivant qui peut se généraliser à toutes les séquences triées dans l'ordre croissant de \(2^{n}-1\) éléments pour obtenir un arbre parfait :

cas de base : on s'arrête lorsqu'on n'a aucun élément à traiter et on renvoie un arbre vide
traitement : on prend l'élément en position médiane (\(2^{n-1}\) si on compte à partir de \(1\) ou \(2^{n-1}-1\) si on compte à partir de \(0\)), on l'insère à la racine d'un arbre vide, puis on partage les éléments restants entre le sous-arbre gauche pour ceux de position inférieure et le sous-arbre droit pour les autres. On appelle ensuite récursivement l'algorithme sur les deux sous-arbres.

En appliquant cet algorithme on insère les éléments dans l'ordre préfixe \([7, 4, -1, 5, 13, 8, 17]\) ou dans l'ordre d'un parcours en largeur \([7, 4, 13, -1, 5, 8, 17]\) et on obtient l'arbre binaire parfait :

alt

Exercice 8

💻 Saisir ses réponses sur Capytale

Dans cet exercice, vous allez programmer l'ajout d'un élément dans un arbre binaire de recherche pour les deux implémentations présentées précédemment.

Question 1

énoncésolution

Complétez l'interface fonctionnelle de l'implémentation d'arbre binaire immuable donnée dans l'exercice 6, avec une fonction ajoute qui renvoie un nouvel arbre binaire construit par ajout d'un élément. Si l'élément est déjà présent dans le noeud racine, on l'ajoute récursivement dans le sous-arbre gauche.

🐍 Script Python

def ajoute(abr, elt):
    """Renvoie un nouvel arbre binaire de recherche construit par ajout de  elt comme feuille dans l'arbre binaire de recherche abr
    """
    if abr is None:
        return Noeud(None, elt, None)
    elif elt <= abr.element:
        return Noeud(ajoute(abr.gauche, elt), abr.element, abr.droit)
    # à compléter

🐍 Script Python

def ajoute(abr, elt):
    """Renvoie un nouvel arbre binaire de recherche construit par ajout de  elt comme feuille dans l'arbre binaire de recherche abr
    """
    if abr is None:
        return Noeud(None, elt, None)
    elif elt <= abr.element:
        return Noeud(ajoute(abr.gauche, elt), abr.element, abr.droit)
    else:
        return Noeud(abr.gauche, abr.element, ajoute(abr.droit, elt))

Question 2

énoncésolution

Reprendre la question 1 mais cette fois on considère que l'arbre binaire de recherche ne peut pas contenir d'éléments en doublons et la fonction ajoute renvoie une copie superficielle de l'arbre si l'élément s'y trouve déjà.

🐍 Script Python

def ajoute(abr, elt):
    """Renvoie un nouvel arbre binaire de recherche construit par ajout de  elt comme feuille dans l'arbre binaire de recherche abr
    """
    if abr is None:
        return Noeud(None, elt, None)
    elif elt < abr.element:
        return Noeud(ajoute(abr.gauche, elt), abr.element, abr.droit)
    elif elt > abr.element:
        return Noeud(abr.gauche, abr.element, ajoute(abr.droit, elt))
    else:
        return Noeud(abr.gauche, abr.element, abr.droit)

Question 3

énoncésolution

Complétez le code de la méthode ajoute dans l'interface POO de l'implémentation d'arbre binaire mutable donnée dans l'exercice 6. Si l'élément est déjà présent dans le noeud racine, on l'ajoute récursivement dans le sous-arbre gauche.

🐍 Script Python

def ajoute(self, elt):
    """Ajoute elt dans une feuille de l'arbre binaire de recherche
    Maintient la propriété d'arbre binaire de recherche."""
    if self.est_vide():
        self.racine = Noeud(ABR(), elt, ABR())
    # à compléter

🐍 Script Python

 def ajoute(self, elt):
    """Ajoute elt dans une feuille de l'arbre binaire de recherche
    Maintient la propriété d'arbre binaire de recherche."""
    if self.est_vide():
        self.racine = Noeud(ABR(), elt, ABR())
    elif elt <= self.element_racine():
        self.gauche().ajoute(elt)
    else:
        self.droit().ajoute(elt)

Question 4

énoncésolution

Reprendre la question 3 mais cette fois on considère que l'arbre binaire de recherche ne peut pas contenir d'éléments en doublons et la méthode ajoute ne fait rien si l'élément s'y trouve déjà.

🐍 Script Python

def ajoute(self, elt):
    """Ajoute elt dans une feuille de l'arbre binaire de recherche
    Maintient la propriété d'arbre binaire de recherche."""
    if self.est_vide():
        self.racine = Noeud(ABR(), elt, ABR())
    elif elt < self.element_racine():
        self.gauche().ajoute(elt)
    elif elt > self.element_racine():
        self.droit().ajoute(elt)

Dans l'implémentation proposée d'arbre binaire immuable, si on ajoute un élément, le nouvel arbre obtenu partage un sous-arbre avec l'arbre initial. Ce n'est pas gênant tant qu'on ajoute un élément, mais si on le supprime, il sera aussi supprimé par effet de bord de tous les arbres qui le partagent. ↩
Ces techniques d'équilibrage sont hors-programme :arbres rouge-noir ou AVL. ↩