Insertion et recherche dans un BST
Implémentez l’insertion et la recherche de manière récursive et itérative, suivez le chemin dans l’arbre pour différentes clés et analysez la complexité dans le pire cas pour les arbres déséquilibrés.
Insertion et recherche dans un BST est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Définition de la propriété des BST
Un arbre binaire de recherche respecte un invariant : pour chaque nœud, toutes les valeurs de son sous-arbre gauche sont strictement inférieures à la valeur du nœud, et toutes les valeurs de son sous-arbre droit sont strictement supérieures. Cette propriété d'ordre — maintenue dans l'ensemble du sous-arbre et pas seulement chez les enfants immédiats — permet d'effectuer les opérations de recherche, d'insertion et de suppression en O(log n) sur des arbres équilibrés, et distingue un BST d'un arbre binaire quelconque.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Valid BST:
# 4
# / \
# 2 6
# / \ / \
# 1 3 5 7
# For node 4: left subtree {1,2,3} < 4 < right subtree {5,6,7}
# This holds recursively for EVERY node in the tree.
print('BST property: left < node < right at every level')Recherche récursive dans un BST
La recherche dans un BST fonctionne comme une recherche binaire : comparez la cible à la valeur du nœud courant, puis explorez récursivement le sous-arbre approprié. Si la cible est égale à la valeur courante, renvoyez le nœud. Si elle est plus petite, allez à gauche ; si elle est plus grande, allez à droite. Renvoyez une valeur nulle si vous atteignez un nœud vide. La complexité temporelle est O(h) — O(log n) pour les arbres équilibrés et O(n) pour les arbres dégénérés.
def search_bst(root, val):
if not root:
return None # not found
if root.val == val:
return root # found
if val < root.val:
return search_bst(root.left, val)
else:
return search_bst(root.right, val)
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
result = search_bst(root, 2)
print(result.val if result else 'Not found') # 2
result = search_bst(root, 5)
print(result.val if result else 'Not found') # Not foundRecherche itérative dans un BST
La recherche itérative évite le coût lié à la pile d'appels et est privilégiée dans le code de production. Utilisez un pointeur curr qui parcourt l'arbre vers le bas en suivant le côté gauche ou droit selon les comparaisons. Il s'agit d'une simple boucle qui se répète tant que trois cas ne sont pas résolus : nul (introuvable), correspondance (trouvé) ou changement de direction. La recherche itérative est également en O(h), mais utilise O(1) espace au lieu de O(h) pour la version récursive.
def search_bst_iterative(root, val):
curr = root
while curr:
if val == curr.val:
return curr
elif val < curr.val:
curr = curr.left
else:
curr = curr.right
return None # not found
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
node = search_bst_iterative(root, 3)
print(node.val if node else 'Not found') # 3
print(search_bst_iterative(root, 9)) # NoneInsertion récursive dans un BST
L'insertion dans un BST trouve la position correcte en suivant les mêmes décisions gauche/droite que la recherche, puis rattache un nouveau nœud à la première position null atteinte. L'approche récursive renvoie la racine, éventuellement nouvelle, de chaque sous-arbre : si le nœud courant est nul, renvoyez un nouveau TreeNode ; sinon, mettez à jour root.left ou root.right avec le résultat de l'appel récursif. Ce schéma est clair et courant dans les solutions d'entretien.
def insert_bst(root, val):
if not root:
return TreeNode(val) # create new node here
if val < root.val:
root.left = insert_bst(root.left, val)
elif val > root.val:
root.right = insert_bst(root.right, val)
# val == root.val: duplicate, do nothing (or handle as needed)
return root
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root = insert_bst(root, 1)
root = insert_bst(root, 5)
# Tree is now: 4, left=2(left=1), right=7(left=5)
print(root.right.left.val) # 5Insertion itérative dans un BST
L'insertion itérative utilise un pointeur parent pour suivre le dernier nœud non nul avant d'atteindre le point d'insertion. Descendez dans l'arbre comme lors d'une recherche, en mémorisant le parent et la dernière direction suivie. Lorsque vous atteignez une valeur nulle, rattachez le nouveau nœud du côté approprié du parent. Gérez toujours séparément le cas limite de l'arbre vide (la racine est nulle).
def insert_bst_iterative(root, val):
new_node = TreeNode(val)
if not root:
return new_node
curr = root
while True:
if val < curr.val:
if curr.left is None:
curr.left = new_node
break
curr = curr.left
else: # val > curr.val
if curr.right is None:
curr.right = new_node
break
curr = curr.right
return root
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root = insert_bst_iterative(root, 3)
print(root.left.right.val) # 3BST dans le pire des cas : arbres dégénérés
Si vous insérez une séquence triée dans un BST, vous obtenez un arbre dégénéré qui se transforme en liste chaînée. Les opérations de recherche, d'insertion et de suppression passent toutes en O(n). C'est la raison d'être des BST équilibrés (arbres AVL, arbres rouge-noir). Lors d'un entretien, mentionnez toujours ce pire cas si l'on vous interroge sur la complexité d'un BST : dire « O(log n) en moyenne, O(n) dans le pire cas pour les arbres non équilibrés » démontre une bonne compréhension du sujet.
# Inserting 1, 2, 3, 4, 5 into a BST:
# 1
# \
# 2
# \
# 3
# \
# 4
# \
# 5
# This is a right-skewed tree: search is O(n) not O(log n)
root = None
for val in [1, 2, 3, 4, 5]:
root = insert_bst(root, val)
# Verify the skew
node = root
depth = 0
while node:
depth += 1
node = node.right
print(f'Height: {depth}') # 5 = O(n), not O(log n)Recherche du minimum et du maximum
Dans un BST, la valeur minimale se trouve toujours dans le nœud le plus à gauche (continuez vers la gauche jusqu'à atteindre une valeur nulle), et la valeur maximale dans le nœud le plus à droite. Ces opérations en O(h) sont souvent utilisées comme sous-fonctions lors de la suppression dans un BST (pour trouver le successeur en ordre infixe) et dans les requêtes d'intervalle. Connaître ces fonctions auxiliaires par cœur permet de gagner du temps lors des entretiens.
def find_min(root):
while root.left:
root = root.left
return root
def find_max(root):
while root.right:
root = root.right
return root
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.right = TreeNode(9)
print(find_min(root).val) # 1
print(find_max(root).val) # 9Successeur et prédécesseur en ordre infixe
Le successeur en ordre infixe d'un nœud est le nœud dont la valeur est la plus petite parmi celles qui lui sont supérieures. Si le nœud possède un sous-arbre droit, le successeur est find_min(node.right). S'il ne possède pas de sous-arbre droit, le successeur est l'ancêtre le plus proche pour lequel le nœud donné se trouve dans le sous-arbre gauche. Comprendre ce mécanisme est essentiel pour la suppression dans un BST et les problèmes d'itérateur de BST.
def inorder_successor(root, p):
successor = None
while root:
if p.val < root.val:
successor = root # possible successor
root = root.left
else:
root = root.right
return successor
def inorder_predecessor(root, p):
predecessor = None
while root:
if p.val > root.val:
predecessor = root # possible predecessor
root = root.right
else:
root = root.left
return predecessor
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
p = root.left # node with val=2
print(inorder_successor(root, p).val) # 3
print(inorder_predecessor(root, p).val) # 1Analyse de la complexité de la recherche dans un BST
Les performances d'un BST dépendent entièrement de la hauteur de l'arbre. Pour un BST équilibré comportant n nœuds, la hauteur est O(log n), ce qui donne une recherche, une insertion et une suppression en O(log n). Pour un BST dégénéré, la hauteur est O(n), et toutes les opérations sont donc en O(n). Python ne possède pas de BST équilibré intégré (contrairement au TreeMap de Java) ; vous devez donc soit implémenter vous-même un arbre AVL ou rouge-noir, soit utiliser sortedcontainers.SortedList, soit vous appuyer sur un tas pour les cas d'utilisation de file de priorité.
# Python's BST alternatives:
# 1. heapq - min/max heap, O(log n) push/pop
# 2. sortedcontainers.SortedList (third-party, often allowed)
# 3. Manual AVL or Red-Black (rarely required in interviews)
# When interviews say 'use a BST':
# - LeetCode: implement TreeNode-based solution
# - Real interview: mention sortedcontainers or Java TreeMap equivalent
# - O(log n) operations matter when you need ordered access
# For pure insert/lookup without ordering: use dict (O(1) average)
print('Use heap for priority, dict for lookup, BST for ordered range')Insertion dans un BST : cas limites
Vérifiez toujours que votre insertion gère les cas suivants : arbre vide (renvoyer le nouveau nœud comme racine), valeurs en double (définir s'il faut les ignorer, les insérer à gauche ou à droite — et rester cohérent), et valeurs très grandes ou très petites. Lors d'un entretien, indiquez votre hypothèse concernant les doublons avant de coder. La convention la plus courante dans les problèmes LeetCode est que toutes les valeurs sont distinctes, sauf indication contraire.
def insert_bst_no_duplicates(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert_bst_no_duplicates(root.left, val)
elif val > root.val:
root.right = insert_bst_no_duplicates(root.right, val)
# else: val == root.val -> duplicate, skip
return root
# Test all edge cases:
root = None
root = insert_bst_no_duplicates(root, 5) # empty tree
root = insert_bst_no_duplicates(root, 5) # duplicate
root = insert_bst_no_duplicates(root, 3)
root = insert_bst_no_duplicates(root, 7)
print(root.val, root.left.val, root.right.val) # 5 3 7BST à partir d'un tableau trié
Construire un BST équilibré en hauteur à partir d'un tableau trié (LeetCode n° 108) repose sur la méthode diviser pour régner : l'élément central devient la racine, la moitié gauche devient le sous-arbre gauche et la moitié droite devient le sous-arbre droit. Cela garantit un arbre équilibré de hauteur O(log n). La complexité temporelle est O(n), puisque chaque élément est traité une seule fois.
def sorted_array_to_bst(nums):
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = sorted_array_to_bst(nums[:mid])
root.right = sorted_array_to_bst(nums[mid+1:])
return root
nums = [-10, -3, 0, 5, 9]
root = sorted_array_to_bst(nums)
print(root.val) # 0 (middle element)
print(root.left.val) # -3
print(root.right.val) # 9Vérification rapide
Testez votre compréhension des concepts de structures de données et d'algorithmes — préparation aux entretiens de programmation — abordés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : la propriété des BST (sous-arbre gauche strictement inférieur, sous-arbre droit strictement supérieur), la recherche et l'insertion, récursives et itératives, en O(h), ainsi que les arbres dégénérés dans le pire des cas, où la hauteur est égale à n. Nous allons maintenant aborder la suppression dans un BST et ses trois cas.
Questions Fréquemment Posées
La leçon « Insertion et recherche dans un BST » est-elle gratuite ?
Oui — le texte complet de « Insertion et recherche dans un BST » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Insertion et recherche dans un BST » ?
Implémentez l’insertion et la recherche de manière récursive et itérative, suivez le chemin dans l’arbre pour différentes clés et analysez la complexité dans le pire cas pour les arbres déséquilibrés. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Insertion et recherche dans un BST » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Insertion et recherche dans un BST
- Suppression dans un BST : trois cas
- Valider un BST et les propriétés du parcours infixe
- K-ième plus petit élément, somme d’intervalle et BST vers tableau trié