Arbres de recherche binaires
Arbres binaires de recherche
- Un arbre binaire de recherche (ABR) stocke des valeurs pour qu'elles restent triées et soient faciles à trouver.
- Chaque nœud contient une valeur et des liens vers jusqu'à deux enfants : un
leftet unright. - Le nœud supérieur est la racine. Un nœud sans enfants est une feuille.
La règle ABR
- Pour chaque nœud : tout ce qui se trouve dans son sous-arbre gauche est plus petit, tout ce qui se trouve dans son sous-arbre droit est plus grand ou égal (cette leçon envoie les valeurs égales à droite).
- Cette seule règle permet de trouver une valeur en allant à gauche ou à droite — jamais les deux.
5
/ \
3 8
/ \ \
1 4 9
left < node <= right, at every node
Un nœud
- Nous modélisons un nœud comme un petit objet avec un
value, unleftet unright. - Un nœuf neuf n'a pas encore d'enfants, donc
leftetrightcommencent àNone.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
n = Node(5)
print(n.value) # 5
print(n.left) # None
Insérer une valeur
- Commencez à la racine. Si l'arbre est vide, la nouvelle valeur devient la racine.
- Si la valeur est plus petite que le nœud actuel, allez à gauche ; sinon allez à droite.
- Répétez jusqu'à atteindre une place vide, et placez le nouveau nœud là.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
root = None
for v in [5, 3, 8, 1]:
root = insert(root, v)
print(root.value) # 5
print(root.left.value) # 3
print(root.right.value) # 8
Le parcours en ordre donne un ordre trié
- Le parcours en ordre visite : le sous-arbre gauche, puis le nœud, puis le sous-arbre droit.
- Grâce à la règle ABR, cela visite les valeurs dans un ordre trié — gratuitement.
- C'est naturellement récursif : parcourir à gauche, prendre la valeur, parcourir à droite.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root
def in_order(root):
if root is None:
return []
return in_order(root.left) + [root.value] + in_order(root.right)
root = None
for v in [5, 3, 8, 1, 4]:
root = insert(root, v)
print(in_order(root)) # [1, 3, 4, 5, 8]
La recherche est rapide
- Pour trouver une valeur, comparez-la au nœud, puis allez à gauche ou à droite — en sautant la moitié de l'arbre à chaque étape.
- Dans un arbre équilibré, cela prend environ
O(log n)étapes, bien plus rapide que de scanner une liste. - Un arbre mal formé (valeurs insérées déjà triées) peut se dégrader en une ligne —
O(n).
Erreurs courantes
- Dans un arbre binaire de recherche : enfant gauche < nœud <= enfant droit (les valeurs égales vont à droite ici).
- Un arbre déséquilibré perd l'avantage de vitesse.
À vous maintenant
- Implémentez les trois opérations fondamentales :
insert,in_orderetcontains. - La classe
Node(et une implémentation fonctionnelle deinsert, là où nécessaire) est fournie. - Appuyez sur Vérifier la réponse pour tester sur plusieurs arbres.
Rechercher dans un ABR
Gauche est plus petit, droite est plus grand — donc chaque étape saute la moitié de l'arbre.
Difficulté 5/5 · 400 pièces + un petit bonus lors de la première réussite aujourd'hui
La classe Node est fournie. Écrivez insert(root, value) qui ajoute value à l'ABR et retourne la racine. Si root est None, retournez un nouveau Node(value). Si value < root.value va à gauche, sinon allez à droite — et réassignez cet enfant au résultat de l'insertion dans celui-ci.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 5/5 · 400 pièces + un petit bonus lors de la première réussite aujourd'hui
Node et un insert fonctionnel sont fournis. Écrivez in_order(root) qui retourne une liste des valeurs issues d'un parcours en ordre : sous-arbre gauche, puis la valeur de ce nœud, puis le sous-arbre droit. Grâce à la règle de l'ABR, la liste ressort triée. Un arbre vide (None) donne [].
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 5/5 · 400 pièces + un petit bonus lors de la première réussite aujourd'hui
Node et un insert fonctionnel sont fournis. Écrivez contains(root, value) qui retourne True si value est dans l'arbre, sinon False. Utilisez la règle de l'ABR : s'il correspond à ce nœud, retournez True ; s'il est plus petit, cherchez dans le gauche, sinon cherchez dans le droit ; une branche vide (None) signifie qu'il n'est pas là.
Cliquez sur Exécuter pour voir le résultat ici.