Rechercher une clé dans un arbre binaire de recherche, insérer une clé
Objectifs
Connaissances visées
Algorithmes sur les arbres binaires de recherche (ABR)Compétences à développer
Rechercher une clé dans un arbre de recherche. Insérer une clé dans un arbre de recherche Coût de la recherche dans un arbre de recherche équilibréCaractéristiques d’un arbre binaire de recherche (ABR)
Un Arbre Binaire de Recherche (ABR) est un arbre dans lequel une clé (valeur) du sous-arbre gauche est inférieure à la clé (valeur) du nœud-racine, et la clé (valeur) du sous-arbre droit est supérieure à la clé (valeur) du nœud-racine.
Soit le nœud-racine suivant :
La clé ’12’ du sous-arbre gauche (SAG) est inférieure à 24 et la clé 33 du sous-arbre droit (SAD) est supérieure à 24..
La clé 18 du SAD du nœud 12 est inférieure à 24 mais supérieure à 12, et la clé 27 du SAG du nœud 33 est supérieure à 24 mais inférieure à 33..
Algorithme de recherche d’une clé dans un ABR.
Chercher clé dans ABR
si ABR est vide, alors FAUX et fin
sinon si cle est identique à cle de nœud racine, alors VRAI et fin
sinon si clé inférieure à clé de noeud-racine, alors Chercher clé dans SAG
sinon Chercher clé dans SAD
Algorithme d’insertion d’une clé dans un ABR.
Il s’agit d’ajouter une nouvelle valeur dans l’arbre.
Pour déterminer à quel endroit de l’arbre cette valeur doit être insérée, il faut parcourir l’arbre de façon dichotomique, c’est à dire en comparant la valeur à ajouter avec la valeur de la racine de l’arbre : si la valeur à ajouter est inférieure à la valeur de la racine, elle sera ajoutée dans le sous-arbre gauche, sinon elle sera ajoutée dans le sous-arbre droit.
L’ajout se fait sous la forme d’un arbre n’ayant pas de descendants (i.e. un sous-arbre gauche et un sous-arbre droit ‘vides’).
L’algorithme est le suivant :
mode récursif
insérer clé dans ABR
si la clé est strictement inférieure à la clé de la racine de l’arbre,
si l’arbre ne possède pas de sous-arbre gauche,
ajouter un sous-arbre gauche avec la clé à ajouter
renvoyer ‘Vrai’
sinon renvoyer insérer clé dans sous-arbre gauche
sinon si la clé est strictement supérieure à la clé de la racine de l’arbre,
si l’arbre ne possède pas de sous-arbre droit,
ajouter un sous-arbre droit avec la clé à ajouter
renvoyer ‘Vrai’
sinon renvoyer insérer clé dans sous-arbre droit
sinon renvoyer ‘Faux’mode itératif
Soit un arbre binaire de recherche non vide ‘abr’ :
Tant que ‘abr’ n’est pas vide
si la clé à insérer est strictement inférieure à la clé de la racine de l’arbre,
si l’arbre ne possède pas de sous-arbre gauche,
ajouter un sous-arbre gauche avec la clé à ajouter
renvoyer ‘abr’
sinon ‘abr’ prend la valeur du sous arbre gauche
sinon si la clé à insérer est strictement supérieure à la clé de la racine de l'arbre,
si l'arbre ne possède pas d’arbre droit,
ajouter un sous-arbre droit avec la clé à ajouter
renvoyer ‘abr’
sinon ‘abr’ prend la valeur du sous-arbre droit
sinon renvoyer ‘abr’
fin de Tant queImplémentation – Paradigme de programmation impérative (tableau (vs liste en Python) comme structure de base d’un arbre)
"""Lycée - Spécialité NSI - Terminale | Arbre Binaire de Recharche (ABR)."""
def make_abr(cle=None):
"""Création d'une arbre binaire de recherche.
Parameters
----------
cle : INT, FLOAT, STR, optional
Valeur de la clé d'un noeud de l'arbre binaire. The default is None.
Returns
-------
list
Liste vide = Arbre vide.
Liste de 3 éléments : clé, sous-arbre gauche (Liste vide), et
sous-arbre droit (vide vide)
"""
# mkabr : MaKe Arbre Binaire de Recherche
if cle is None:
return []
else:
return [cle, [], []]
def est_vide(arbre):
"""Détermine si l'arbre est vide.
Parameters
----------
arbre : LIST
Returns
-------
BOOL
True si vide, sinon False.
"""
return arbre == []
def get_cle(arbre):
"""Obtenir la valeur de la clé de la racine de l'arbre binaire.
Parameters
----------
arbre : LIST
Returns
-------
INT, FLOAT, STR
la valeur de la clé de la racine de l'arbre binaire s'il n'est pas vide
sinon None
"""
if not est_vide(arbre):
return arbre[0]
else:
return None
def get_sag(arbre):
"""Obtenir le sous-arbre gauche.
Parameters
----------
arbre : LIST
Returns
-------
LIST
"""
if not est_vide(arbre):
return arbre[1]
else:
return arbre
def get_sad(arbre):
"""Obtenir le sous-arbre droit.
Parameters
----------
arbre : LIST
Returns
-------
LIST
"""
if not est_vide(arbre):
return arbre[2]
else:
return arbre
def set_sag(arbre, cle):
"""Affecte un sag à 'arbre' avec une valeur de racine égale à 'cle'.
Parameters
----------
arbre : LIST
arbre binaire.
cle : INT; FLOAT, STR
valeur à affecter à la racine de l'arbre.
Returns
-------
arbre : LIST
"""
arbre[1] = [cle, [], []]
return arbre
def set_sad(arbre, cle):
"""Affecte un sad à 'arbre' avec une valeur de racine égale à 'cle'.
Parameters
----------
arbre : LIST
arbre binaire.
cle : INT; FLOAT, STR
valeur à affecter à la racine de l'arbre.
Returns
-------
arbre : LIST
"""
arbre[2] = [cle, [], []]
return arbre
def taille(arbre):
"""Détermine la taille de l'arbre binaire.
Parameters
----------
arbre : LIST
Returns
-------
INT
Taille = nombre de noeuds de l'arbre binaire.
"""
if est_vide(arbre):
return 0
return 1 + taille(get_sag(arbre)) + taille(get_sad(arbre))
def hauteur(arbre):
"""Détermine la hauteur de l'arbre binaire.
Parameters
----------
arbre : LIST
Returns
-------
INT
Hauteur : nombre de noeuds entre la racine (incluse) et la feuille
la plus éloignée de la racine.
"""
if est_vide(arbre):
return 0
return 1 + max(hauteur(get_sag(arbre)), hauteur(get_sad(arbre)))
def parcours_p_i(arbre):
"""Parcours en profondeur d'ordre infixe.
Parameters
----------
arbre : List
Arbre binaire de recherche.
Returns
-------
Tuple
Liste des clés de tous le noeuds.
"""
if est_vide(arbre):
return tuple()
return parcours_p_i(get_sag(arbre)) + (get_cle(arbre), ) +\
parcours_p_i(get_sad(arbre))
def cherche_i_abr(arbre, cle):
"""Cherche la valeur de "cle" dans "arbre".
Méthode itérative
Parameters
----------
arbre : LIST
arbre binaire.
cle : INT, FLOAT, STR
valeur de clé recherchée.
Returns
-------
bool
Vrai si "cle" est dans "arbre", sinon False
"""
trouve = False
while not est_vide(arbre) and trouve is False:
# si la clé recherchée est strictement inférieure
# à la clé de la racine de l'arbre,
if cle < get_cle(arbre):
arbre = get_sag(arbre)
# sinon si la clé recherchée est strictement supérieure
# à la clé de la racine de l'arbre,
elif cle > get_cle(arbre):
arbre = get_sad(arbre)
# sinon renvoyer 'Vrai'
# (la clé recherchée est identique à la clé de l'arbre)
else:
trouve = True
return trouve
def cherche_r_abr(arbre, cle):
"""Cherche la valeur de "cle" dans "arbre".
Méthode récursive
Parameters
----------
arbre : LIST
arbre binaire.
cle : INT, FLOAT, STR
valeur de clé recherchée.
Returns
-------
bool
Vrai si "cle" est dans "arbre", sinon False
"""
if est_vide(arbre):
return False
if cle == get_cle(arbre):
return True
if cle < get_cle(arbre):
return cherche_r_abr(get_sag(arbre), cle)
# cle > get_cle(arbre):
return cherche_r_abr(get_sad(arbre), cle)
def inserer_i_abr(arbre, cle):
"""Ajout de 'cle' dans 'arbre'.
Méthode itérative.
Parameters
----------
arbre : LIST
Arbre binaire de recherche.
cle : INT, FLOAT, STR
clé à insérer.
Returns
-------
arbre : LIST
Arbre binaire de recherche modifié.
"""
if est_vide(arbre):
arbre = [cle, [], []]
return arbre
suite, coparb = True, arbre
# coparb : alias de 'arbre' (on copie l'adresse en RAM)
while suite:
if cle < get_cle(coparb):
if est_vide(get_sag(coparb)):
coparb = set_sag(coparb, cle)
suite = False
else:
coparb = get_sag(coparb)
elif cle > get_cle(coparb):
if est_vide(get_sad(coparb)):
coparb = set_sad(coparb, cle)
suite = False
else:
coparb = get_sad(coparb)
else:
# cas où la clé existe déjà
suite = False
return arbre
def inserer_r_abr(arbre, cle):
"""Ajout de 'cle' dans 'arbre'.
Méthode récursive.
Parameters
----------
arbre : LIST
Arbre binaire de recherche.
cle : INT, FLOAT, STR
clé à insérer.
Returns
-------
arbre : LIST
Arbre binaire de recherche modifié.
"""
if est_vide(arbre):
arbre = [cle, [], []]
return arbre
if cle == get_cle(arbre):
return arbre
if cle < get_cle(arbre):
return [get_cle(arbre), inserer_r_abr(get_sag(arbre), cle),
get_sad(arbre)]
if cle > get_cle(arbre):
return [get_cle(arbre), get_sag(arbre),
inserer_r_abr(get_sad(arbre), cle)]
# =============================================================================
# Jeu de tests
# =============================================================================
if __name__ == "__main__":
abr1 = make_abr()
assert est_vide(abr1) is True
abr1 = inserer_i_abr(abr1, 10)
assert abr1 == [10, [], []]
abr1 = inserer_i_abr(abr1, 7)
assert abr1 == [10, [7, [], []], []]
abr1 = inserer_i_abr(abr1, 11)
assert abr1 == [10, [7, [], []], [11, [], []]]
abr1 = inserer_i_abr(abr1, 6)
assert abr1 == [10, [7, [6, [], []], []], [11, [], []]]
assert get_cle(abr1) == 10
assert get_sag(abr1) == [7, [6, [], []], []]
assert get_sad(abr1) == [11, [], []]
abr1 = inserer_r_abr(abr1, 9)
abr1 = inserer_r_abr(abr1, 15)
assert abr1 == [10, [7, [6, [], []], [9, [], []]],
[11, [], [15, [], []]]]
abr1 = inserer_r_abr(abr1, 12)
abr1 = inserer_r_abr(abr1, 2)
abr1 = inserer_r_abr(abr1, 18)
assert abr1 == [10,
[7, [6, [2, [], []], []], [9, [], []]],
[11, [], [15, [12, [], []], [18, [], []]]]]
assert taille(abr1) == 9
assert hauteur(abr1) == 4
assert cherche_i_abr(abr1, 12) is True
assert cherche_i_abr(abr1, 30) is False
assert cherche_r_abr(abr1, 18) is True
assert cherche_r_abr(abr1, 48) is False
assert get_cle(get_sad(get_sag(abr1))) == 9
assert get_cle(get_sag(get_sad(get_sad(abr1)))) == 12
assert parcours_p_i(abr1) == (2, 6, 7, 9, 10, 11, 12, 15, 18)
Implémentation – Paradigme de programmation Objet (instance de classe comme structure de base d’un arbre binaire de recherche)
"""Lycée - Spécialité NSI - Terminale | Arbre Binaire de Recharche (ABR)."""
class ABR:
"""Classe ABR : Arbre binaire de recherche."""
def __init__(self, cle=None):
"""Constructeur.
Parameters
----------
cle : INT, FLOAT, STR, optional
DESCRIPTION. The default is None.
Returns
-------
None.
"""
self.__cle = cle
# Les attributs '__SAG' et '__SAD' sont de type 'None'
# ou de type 'objet ABR'
self.__SAG = None
self.__SAD = None
def estVide(self):
"""Détermine si l'arbre est vide.
Returns
-------
BOOL
True si vide, sinon False.
"""
return self.__cle is None
def existeSAG(self):
"""Détermine s'il existe ou non un sous-arbre gauche.
Returns
-------
BOOL
True si self.__SAG est type objet ABR
False si self.__SAG est de type None
"""
return self.__SAG is not None
def existeSAD(self):
"""Détermine s'il existe ou non un sous-arbre droit.
Returns
-------
BOOL
True si self.__SAD est type objet ABR
False si self.__SAD est de type None
"""
return self.__SAD is not None
def getCle(self):
"""Obtenir la valeur de la clé de la racine de l'arbre binaire.
Returns
-------
INT, FLOAT, STR
la valeur de la clé de la racine de l'arbre binaire.
"""
return self.__cle
def getSAG(self):
"""Obtenir le sous-arbre gauche.
Returns
-------
OBJET de la classe ABR, ou None
"""
return self.__SAG
def getSAD(self):
"""Obtenir le sous-arbre droit.
Returns
-------
OBJET de la classe ABR, ou None
"""
return self.__SAD
def taille(self):
"""Détermine la taille de l'arbre binaire.
Returns
-------
INT
Taille = nombre de noeuds de l'arbre binaire.
"""
if self.estVide():
return 0
if self.existeSAG() and self.existeSAD():
return 1 + self.__SAG.taille() + self.__SAD.taille()
elif self.existeSAG() and not self.existeSAD():
return 1 + self.__SAG.taille()
elif not self.existeSAG() and self.existeSAD():
return 1 + self.__SAD.taille()
else:
return 1
def hauteur(self):
"""Détermine la hauteur de l'arbre binaire
Returns
-------
INT
Hauteur : nombre de noeuds entre la racine (incluse) et la feuille
la plus éloignée de la racine.
"""
if self.estVide():
return 0
if self.existeSAG() and self.existeSAD():
return 1 + max(self.__SAG.hauteur(), self.__SAD.hauteur())
elif self.existeSAG() and not self.existeSAD():
return 1 + self.__SAG.hauteur()
elif not self.existeSAG() and self.existeSAD():
return 1 + self.__SAD.hauteur()
else:
return 1
def parcoursPI(self):
"""Parcours en profondeur d'ordre infixe.
Returns
-------
TUPLE
les clés de l'arbre binaire.
"""
if self.estVide():
return tuple()
if self.existeSAG() and self.existeSAD():
return self.__SAG.parcoursPI() + (self.__cle, ) + \
self.__SAD.parcoursPI()
elif self.existeSAG() and not self.existeSAD():
return self.__SAG.parcoursPI() + (self.__cle, )
elif not self.existeSAG() and self.existeSAD():
return (self.__cle, ) + self.__SAD.parcoursPI()
else:
return (self.__cle, )
def cherche(self, cle):
"""Cherche la valeur de 'cle' dans l'arbre binaire.
Parameters
----------
cle : INT, FLOAT, STR
valuer de la clé à insérer.
Returns
-------
BOOL
True si 'cle' se trouve dans l'arbre binaire, sinon False.
"""
if self.estVide():
return False
if self.__cle == cle:
return True
if cle < self.__cle:
if self.existeSAG():
return self.__SAG.cherche(cle)
else:
return False
if cle > self.__cle:
if self.existeSAD():
return self.__SAD.cherche(cle)
else:
return False
def insere(self, cle):
"""Insère la valeur de 'cle' dans l'arbre binaire.
Parameters
----------
cle : INT, FLOAT, STR
DESCRIPTION.
Returns
-------
BOOL
True si insertion effectuée,
sinon False (valeur de la clé déjà présente dans l'arbre binaire.)
"""
if self.estVide():
self.__cle = cle
return True
if cle == self.__cle:
return False
if cle < self.__cle:
if self.existeSAG():
return self.__SAG.insere(cle)
else:
self.__SAG = ABR(cle)
return True
if cle > self.__cle:
if self.existeSAD():
return self.__SAD.insere(cle)
else:
self.__SAD = ABR(cle)
return True
# =============================================================================
# Jeu de tests
# =============================================================================
if __name__ == "__main__":
arb1 = ABR()
assert arb1.estVide() is True
assert arb1.insere(10) is True
assert arb1.getCle() == 10
assert arb1.getSAG() is None
assert arb1.getSAD() is None
assert arb1.existeSAG() is False
assert arb1.existeSAD() is False
for i in (7, 11, 9, 6, 15, 12, 2, 18):
arb1.insere(i)
assert arb1.taille() == 9
assert arb1.hauteur() == 4
assert arb1.getSAG().getCle() == 7
assert arb1.getSAG().getSAG().getCle() == 6
assert arb1.getSAG().getSAD().getCle() == 9
assert arb1.getSAD().getSAD().getCle() == 15
assert arb1.getSAD().getSAD().getSAG().getCle() == 12
assert arb1.parcoursPI() == (2, 6, 7, 9, 10, 11, 12, 15, 18)Article sous licence 
<< Cliquez pour plus d’informations <<
<< Cliquez pour plus d’informations <<