Binary search trees · Arbres de recherche binaires
Binary search trees
- A binary search tree (BST) stores values so they stay sorted and are fast to find.
- Each node holds a value and links to up to two children: a
leftand aright. - The top node is the root. A node with no children is a leaf.
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.
The BST rule
- For every node: everything in its left subtree is smaller, everything in its right is larger.
- This one rule is what lets you find a value by going left or right — never both.
La règle ABR
- Pour chaque nœud : tout ce qui est dans son sous-arbre gauche est plus petit, tout ce qui est dans le droit est plus grand.
- 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
A node
- We model a node as a small object with a
value, aleft, and aright. - A brand-new node has no children yet, so
leftandrightstart asNone.
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
Inserting a value
- Start at the root. If the tree is empty, the new value becomes the root.
- If the value is smaller than the current node, go left; otherwise go right.
- Repeat until you reach an empty spot, and put the new node there.
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
In-order traversal gives sorted order
- In-order traversal visits: the left subtree, then the node, then the right subtree.
- Because of the BST rule, this visits the values in sorted order — for free.
- It is naturally recursive: traverse left, take the value, traverse right.
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]
Searching is fast
- To find a value, compare it with the node, then go left or right — skipping half the tree each step.
- In a balanced tree this takes about
O(log n)steps, much faster than scanning a list. - A badly-shaped tree (values inserted already sorted) can degrade to a line —
O(n).
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).
Common mistakes
- In a binary search tree: left child < node < right child.
- An unbalanced tree loses the speed advantage.
Erreurs courantes
- Dans un arbre binaire de recherche : enfant gauche < nœud < enfant droit.
- Un arbre déséquilibré perd l'avantage de vitesse.
Now you try
- Build the three core operations:
insert,in_order, andcontains. - The
Nodeclass (and a workinginsert, where you need it) is provided. - Press Check answer to test it on several trees.
À 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.
Searching a BST · Rechercher dans un ABR
Left is smaller, right is bigger — so each step skips half the tree. · Gauche est plus petit, droite est plus grand — donc chaque étape saute la moitié de l'arbre.
The · Le Node class is provided. Write insert(root, value) that adds value to the BST and returns the root. If root is None, return a new Node(value). If value < root.value go left, otherwise go right — and reassign that child to the result of inserting into it. · 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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Node and a working insert are provided. Write in_order(root) that returns a list of the values from an in-order traversal: left subtree, then this node's value, then right subtree. Thanks to the BST rule the list comes out sorted. An empty tree (None) gives []. · 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 [].
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Node and a working insert are provided. Write contains(root, value) that returns True if · si value is in the tree, else False. Use the BST rule: if it equals this node return True; if it is smaller search left · vers la gauche, otherwise search right · juste; an empty branch (None) means it is not there. · 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à.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.