Suppression dans un BST : trois cas
Gérez la suppression d’une feuille, d’un nœud avec un seul enfant et d’un nœud avec deux enfants à l’aide du successeur infixe, en implémentant l’algorithme depuis zéro.
Suppression dans un BST : trois cas est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 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.
Pourquoi la suppression dans un BST est délicate
La suppression dans un BST est la plus complexe des trois opérations fondamentales, car retirer un nœud doit préserver la propriété du BST dans l'ensemble de l'arbre. Il existe trois cas distincts selon les enfants du nœud : aucun enfant (une feuille), un enfant ou deux enfants. Chaque cas nécessite une stratégie différente. Les examinateurs apprécient ce problème, car il évalue la manipulation des pointeurs, la réflexion sur les cas limites et la connaissance du concept de successeur en ordre infixe.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Three cases for deleting a node:
# Case 1: Leaf node (no children) -> simply remove it
# Case 2: One child -> replace node with its child
# Case 3: Two children -> replace value with in-order successor
# then delete the in-order successor
print('BST delete: 3 cases based on number of children')Cas 1 : supprimer une feuille
Une feuille ne possède aucun enfant. La suppression est simple : renvoyez None depuis l'appel récursif, ce qui amène le parent à définir son pointeur (gauche ou droit) sur une valeur nulle. C'est le cas de base que toute implémentation de suppression dans un BST doit gérer en premier. Vérifiez que cela fonctionne dans le cas particulier où l'arbre ne possède qu'un seul nœud (la racine est une feuille).
def find_min(node):
while node.left:
node = node.left
return node
# Demonstrating leaf deletion:
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.left = TreeNode(1) # leaf
root.left.right = TreeNode(4) # leaf
# To delete node 1 (leaf): set root.left.left = None
root.left.left = None
print(root.left.left) # None -- deleted
print(root.left.val) # 3 still intactCas 2 : nœud avec un seul enfant
Lorsqu’un nœud possède exactement un enfant, remplacez le nœud par cet enfant. Renvoyez l’enfant non nul depuis l’appel récursif afin que le pointeur du parent soit mis à jour et ignore le nœud supprimé. Cela fonctionne de la même manière que l’enfant unique soit à gauche ou à droite : il suffit de renvoyer celui qui existe.
# Demonstrating one-child deletion:
# Tree: 5
# / \
# 3 7
# \
# 4
# Delete node 3 (has only right child 4):
# Result: 5
# / \
# 4 7
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.right = TreeNode(4)
# In the recursive implementation:
# When we reach node 3 and it has no left child,
# we return root.right (node 4) to the parent.
# Parent sets its left pointer to 4, skipping 3.
print('One-child case: return the surviving child')Cas 3 : nœud avec deux enfants
Lorsqu’un nœud possède deux enfants, nous ne pouvons pas simplement le supprimer. Trouvez plutôt son successeur en ordre infixe (la plus petite valeur du sous-arbre droit), copiez sa valeur dans le nœud courant, puis supprimez le successeur en ordre infixe du sous-arbre droit. Le successeur possède au plus un enfant (aucun enfant gauche), donc sa suppression relève du cas 1 ou du cas 2 — que nous savons déjà traiter.
# Demonstrating two-child deletion:
# Tree: 5
# / \
# 3 7
# / \
# 6 9
# Delete node 5 (two children 3 and 7):
# In-order successor = 6 (smallest in right subtree)
# Step 1: replace 5's value with 6
# Step 2: delete 6 from right subtree
# Result: 6
# / \
# 3 7
# \
# 9
print('Two-child case: replace with in-order successor')Implémentation complète de la suppression dans un BST
La suppression récursive complète combine les trois cas. Trouvez le nœud à supprimer en comparant les valeurs, puis traitez le cas approprié. Le fait de renvoyer la racine (éventuellement modifiée) à chaque niveau et de la réaffecter à root.left ou root.right gère élégamment toutes les mises à jour des pointeurs sans suivi explicite du parent. La complexité temporelle est de O(h).
def delete_node(root, key):
if not root:
return None # key not found
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
else: # found the node to delete
if not root.left: # Case 1 or 2: no left child
return root.right
if not root.right: # Case 2: no right child
return root.left
# Case 3: two children -> find in-order successor
successor = find_min(root.right)
root.val = successor.val # copy successor value up
root.right = delete_node(root.right, successor.val) # delete successor
return root
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
root = delete_node(root, 5)
print(root.val) # 6 (successor replaced 5)Pourquoi le successeur en ordre infixe ?
Le successeur en ordre infixe (minimum du sous-arbre droit) est utilisé plutôt que le maximum du sous-arbre gauche, car les deux choix sont valides : chacun préserve la propriété du BST. Le prédécesseur en ordre infixe (maximum du sous-arbre gauche) fonctionne également. Certaines implémentations alternent entre les deux pour maintenir l’équilibre de l’arbre. Lors d’un entretien, la version avec le successeur en ordre infixe est la plus souvent attendue ; mentionnez que le prédécesseur fonctionne tout aussi bien.
# Both approaches are valid for two-child deletion:
# Option A: Replace with in-order SUCCESSOR (min of right subtree)
# - Successor goes to current position
# - Delete successor from right subtree
# Option B: Replace with in-order PREDECESSOR (max of left subtree)
# - Predecessor goes to current position
# - Delete predecessor from left subtree
def find_max(node):
while node.right:
node = node.right
return node
# Using predecessor:
def delete_node_pred(root, key):
if not root:
return None
if key < root.val:
root.left = delete_node_pred(root.left, key)
elif key > root.val:
root.right = delete_node_pred(root.right, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left
pred = find_max(root.left)
root.val = pred.val
root.left = delete_node_pred(root.left, pred.val)
return root
print('Both successor and predecessor deletion are correct')Supprimer tous les nœuds ayant une valeur donnée
Une variante vous demande de supprimer tous les nœuds dont les valeurs appartiennent à un intervalle ou satisfont une condition. Pour un BST, cette opération est efficace : appelez récursivement le sous-arbre approprié en fonction des comparaisons et appliquez la suppression partout où la condition est satisfaite. La structure récursive de la suppression dans un BST s’étend naturellement à ces situations sans nécessiter une seconde phase de parcours.
# Delete all nodes with values outside [low, high]
def trim_bst(root, low, high):
if not root:
return None
if root.val < low:
# Entire left subtree is also < low, skip to right
return trim_bst(root.right, low, high)
if root.val > high:
# Entire right subtree is also > high, skip to left
return trim_bst(root.left, low, high)
# Current node is within range
root.left = trim_bst(root.left, low, high)
root.right = trim_bst(root.right, low, high)
return root
root = TreeNode(3)
root.left = TreeNode(0)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
root.left.right.left = TreeNode(1)
root = trim_bst(root, 1, 3)
print(root.val, root.left.val) # 3 2Modèle d’itérateur de BST
L’itérateur BST (LeetCode n° 173) renvoie les éléments dans l’ordre trié, un à la fois, avec un temps moyen de O(1) et un espace de O(h). Implémentez-le avec une pile qui simule le parcours infixe itératif : lors de la construction, empilez tous les nœuds gauches depuis la racine. Lors de next(), dépilez le sommet, puis empilez tous les nœuds gauches du sous-arbre droit. Il s’agit d’un déroulement contrôlé de l’algorithme infixe itératif.
class BSTIterator:
def __init__(self, root):
self.stack = []
self._push_left(root)
def _push_left(self, node):
while node:
self.stack.append(node)
node = node.left
def next(self):
node = self.stack.pop()
if node.right:
self._push_left(node.right)
return node.val
def has_next(self):
return bool(self.stack)
root = TreeNode(7)
root.left = TreeNode(3)
root.right = TreeNode(15)
root.right.left = TreeNode(9)
it = BSTIterator(root)
while it.has_next():
print(it.next(), end=' ') # 3 7 9 15Analyse de la complexité de la suppression d’un nœud
La suppression dans un BST s’exécute en O(h), où h représente la hauteur de l’arbre. Pour un BST équilibré, cela donne O(log n). Pour un arbre dégénéré, la complexité se dégrade en O(n). La recherche du successeur en ordre infixe ajoute au plus un parcours supplémentaire en O(h) du sous-arbre droit, ce qui ne modifie pas la complexité globale. La complexité spatiale est de O(h) pour la pile d’appels dans l’implémentation récursive.
# Complexity summary for BST operations:
# Operation | Balanced | Skewed
# ----------|-----------|-------
# Search | O(log n) | O(n)
# Insert | O(log n) | O(n)
# Delete | O(log n) | O(n)
# Min/Max | O(log n) | O(n)
# In-order | O(n) | O(n) (visits all nodes)
# The key: BST guarantees these complexities only when balanced.
# Python standard library has no balanced BST.
# Use sortedcontainers.SortedList for O(log n) ops in practice.
print('All BST core ops are O(h): O(log n) balanced, O(n) skewed')Deux sommes dans un BST
Deux sommes IV dans un BST demande si deux nœuds quelconques ont une somme égale à une cible. Une approche utilise un ensemble : le parcours infixe collecte les valeurs tout en vérifiant si target - current existe déjà dans l’ensemble. Une approche plus élégante utilise simultanément un itérateur BST vers l’avant et un itérateur BST vers l’arrière, comme deux pointeurs ; cela évite tout espace supplémentaire au-delà de O(h) pour la pile de chaque itérateur.
def find_target_bst(root, k):
seen = set()
def inorder(node):
if not node:
return False
if inorder(node.left):
return True
if k - node.val in seen:
return True
seen.add(node.val)
return inorder(node.right)
return inorder(root)
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.right.right = TreeNode(7)
print(find_target_bst(root, 9)) # True (2+7)
print(find_target_bst(root, 28)) # FalseConvertir un BST en arbre de somme des valeurs supérieures
L’arbre de somme des valeurs supérieures (LeetCode n° 538) remplace la valeur de chaque nœud par la somme de toutes les valeurs supérieures ou égales à la sienne dans le BST. L’idée essentielle consiste à effectuer un parcours infixe inversé (droite → racine → gauche) afin de visiter les nœuds dans l’ordre décroissant et d’accumuler une somme courante. Cette opération s’exécute en O(n) et utilise O(h) d’espace.
def bst_to_gst(root):
acc = [0] # running accumulated sum
def reverse_inorder(node):
if not node:
return
reverse_inorder(node.right) # visit larger values first
acc[0] += node.val
node.val = acc[0] # replace with cumulative sum
reverse_inorder(node.left)
reverse_inorder(root)
return root
root = TreeNode(4)
root.left = TreeNode(1)
root.right = TreeNode(6)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
bst_to_gst(root)
print(root.val) # 4+5+6+7 = 22
print(root.right.val) # 5+6+7 = 18Vérification rapide
Évaluez votre compréhension des concepts de structures de données & algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : les trois cas de suppression dans un BST (feuille, un enfant, deux enfants), la technique du successeur en ordre infixe pour supprimer un nœud à deux enfants, ainsi que des modèles récursifs clairs tels que l’itérateur BST et l’arbre de somme des valeurs supérieures. Ensuite, nous vérifierons la validité des BST et exploiterons les propriétés du parcours infixe.
Questions Fréquemment Posées
La leçon « Suppression dans un BST : trois cas » est-elle gratuite ?
Oui — le texte complet de « Suppression dans un BST : trois cas » 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 « Suppression dans un BST : trois cas » ?
Gérez la suppression d’une feuille, d’un nœud avec un seul enfant et d’un nœud avec deux enfants à l’aide du successeur infixe, en implémentant l’algorithme depuis zéro. 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 2 sur 4.
Combien de temps prend la leçon « Suppression dans un BST : trois cas » ?
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é