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.
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).
- S'ils sont égaux, alors on termine la recherche et on renvoie
⏱️ 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
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
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
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
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")
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.1
⏱️ 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. 2
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
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]\) ?
Question 2
Quel arbre binaire obtient-on si on insère les éléments dans l'ordre croissant ?
On obtient un arbre binaire peigne à droite.
Question 3
Quel arbre binaire obtient-on si on insère les éléments dans l'ordre décroissant ?
On obtient un arbre binaire peigne à gauche.
Question 4
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 :
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
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.
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
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
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à.
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
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.
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
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
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à.
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. ↩
# Tests
(insensible à la casse)(Ctrl+I)