Intermédiaire
🧠 Fondamentaux
20 XP
0 personnes ont réussi
Recherche dans un BST
Maintenant que tu sais insérer des valeurs dans un BST, voyons comment y chercher une valeur. C'est comme chercher un mot dans un dictionnaire papier : tu ne lis pas toutes les pages une par une. Tu ouvres au milieu, et selon que le mot cherche est avant ou apres, tu vas a gauche ou a droite.
Dans un BST, c'est pareil. Si la valeur cherchee est plus petite que le noeud courant, elle ne peut etre que dans le sous-arbre gauche. Si elle est plus grande, elle ne peut etre qu'a droite. Et si c'est la meme valeur, tu l'as trouvee.
Écris une fonction rechercher(racine, valeur) qui retourne True si la valeur est dans l'arbre, False sinon.
Exemple :
racine = None for v in [5, 3, 7, 1]: racine = insérer(racine, v) rechercher(racine, 3) renvoie True rechercher(racine, 99) renvoie False
Tests (2/4)
Valeur presente
racine = None
for v in [5, 3, 7, 1]:
racine = insérer(racine, v)
assert rechercher(racine, 3) == True
Valeur absente
racine = None
for v in [5, 3, 7]:
racine = insérer(racine, v)
assert rechercher(racine, 99) == False
+ 0 tests cachés
Indices (3 disponibles)
Solution officielle
class Node:
def __init__(self, valeur):
self.valeur = valeur
self.gauche = None
self.droite = None
def inserer(racine, valeur):
if racine is None:
return Node(valeur)
if valeur < racine.valeur:
racine.gauche = insérer(racine.gauche, valeur)
else:
racine.droite = insérer(racine.droite, valeur)
return racine
def rechercher(racine, valeur):
if racine is None:
return False
if racine.valeur == valeur:
return True
if valeur < racine.valeur:
return rechercher(racine.gauche, valeur)
return rechercher(racine.droite, valeur)