BST-Löschen: drei Fälle
Behandeln Sie das Löschen eines Blatts, eines Knotens mit einem Kind und eines Knotens mit zwei Kindern mithilfe des In-Order-Nachfolgers und implementieren Sie den Algorithmus von Grund auf.
BST-Löschen: drei Fälle ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Warum das Löschen aus einem BST knifflig ist
Das Löschen aus einem BST ist die komplexeste der drei grundlegenden Operationen, weil beim Entfernen eines Knotens die BST-Eigenschaft im gesamten Baum erhalten bleiben muss. Abhängig von den Kindern des Knotens gibt es drei verschiedene Fälle: Er hat keine Kinder (Blatt), ein Kind oder zwei Kinder. Für jeden Fall ist eine andere Strategie erforderlich. Interviewer stellen dieses Problem gern, weil es die Manipulation von Zeigern, das Denken in Sonderfällen und das Verständnis des Inorder-Nachfolgers prüft.
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')Fall 1: Einen Blattknoten löschen
Ein Blattknoten hat keine Kinder. Das Löschen ist einfach: Geben Sie aus dem rekursiven Aufruf None zurück, sodass der Elternknoten seinen Zeiger (links oder rechts) auf null setzt. Dies ist der Basisfall, den jede Implementierung zum Löschen aus einem BST zuerst behandeln muss. Überprüfen Sie, dass dies auch für den Sonderfall funktioniert, in dem der Baum nur einen Knoten enthält (die Wurzel ist ein Blatt).
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 intactFall 2: Knoten mit einem Kind
Wenn ein Knoten genau ein Kind hat, ersetzen Sie den Knoten durch dieses Kind. Geben Sie das Nicht-Null-Kind aus dem rekursiven Aufruf zurück, damit der Zeiger des übergeordneten Knotens aktualisiert wird und den gelöschten Knoten überspringt. Das funktioniert unabhängig davon, ob sich das einzelne Kind links oder rechts befindet – geben Sie einfach das jeweils vorhandene zurück.
# 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')Fall 3: Knoten mit zwei Kindern
Wenn ein Knoten zwei Kinder hat, können wir ihn nicht einfach entfernen. Ermitteln Sie stattdessen den Inorder-Nachfolger des Knotens (den kleinsten Wert im rechten Teilbaum), kopieren Sie dessen Wert in den aktuellen Knoten und löschen Sie anschließend den Inorder-Nachfolger aus dem rechten Teilbaum. Der Nachfolger hat höchstens ein Kind (kein linkes Kind), daher fällt sein Löschen unter Fall 1 oder Fall 2 – und damit unter Fälle, die wir bereits behandeln können.
# 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')Vollständige Implementierung zum Löschen in einem BST
Die vollständige rekursive Löschfunktion führt alle drei Fälle zusammen. Ermitteln Sie den zu löschenden Knoten durch Vergleichen der Werte und behandeln Sie anschließend den passenden Fall. Das Muster, auf jeder Ebene die (möglicherweise geänderte) Wurzel zurückzugeben und sie wieder root.left oder root.right zuzuweisen, behandelt alle Zeigeraktualisierungen elegant, ohne die übergeordneten Knoten explizit nachverfolgen zu müssen. Die Zeitkomplexität beträgt 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)Warum der Inorder-Nachfolger?
Der Inorder-Nachfolger (das Minimum des rechten Teilbaums) wird anstelle des Maximums des linken Teilbaums verwendet, weil beide Möglichkeiten gültig sind – beide erhalten die BST-Eigenschaft. Auch der Inorder-Vorgänger (das Maximum des linken Teilbaums) funktioniert. Manche Implementierungen wechseln zwischen beiden Möglichkeiten, um den Baum im Gleichgewicht zu halten. In Vorstellungsgesprächen wird häufiger die Variante mit dem Inorder-Nachfolger erwartet; erwähnen Sie daher, dass der Vorgänger ebenso gut funktioniert.
# 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')Alle Knoten mit einem bestimmten Wert löschen
Bei einer Variante sollen Sie alle Knoten löschen, deren Werte innerhalb eines Bereichs liegen oder eine bestimmte Bedingung erfüllen. Bei einem BST ist das effizient möglich: Durchlaufen Sie anhand der Vergleiche den passenden Teilbaum rekursiv und wenden Sie die Löschoperation überall dort an, wo die Bedingung erfüllt ist. Die rekursive Struktur des BST-Löschens lässt sich ganz natürlich auf diese Szenarien erweitern, ohne einen separaten Traversierungslauf zu benötigen.
# 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 2BST-Iterator-Muster
Der BST-Iterator (LeetCode #173) gibt die Elemente einzeln in sortierter Reihenfolge zurück, mit einer durchschnittlichen Zeit von O(1) pro Element und einem Speicherbedarf von O(h). Implementieren Sie ihn mit einem Stack, der die iterative Inorder-Traversierung simuliert: Legen Sie bei der Konstruktion alle linken Knoten ausgehend von der Wurzel auf den Stack. Entfernen Sie bei next() das oberste Element und legen Sie anschließend alle linken Knoten des rechten Teilbaums auf den Stack. Dadurch wird der iterative Inorder-Algorithmus kontrolliert schrittweise ausgeführt.
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 15Löschen eines Knotens: Komplexitätsanalyse
Das Löschen in einem BST benötigt O(h) Zeit, wobei h die Höhe des Baums ist. Bei einem balancierten BST beträgt die Komplexität O(log n). Bei einem entarteten Baum verschlechtert sie sich auf O(n). Das Finden des Inorder-Nachfolgers fügt höchstens eine zusätzliche O(h)-Durchquerung des rechten Teilbaums hinzu, was die Gesamtkomplexität nicht verändert. Die Speicherkomplexität beträgt O(h) für den Aufruf-Stack in der rekursiven Implementierung.
# 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')Two Sum in einem BST
Two Sum IV in einem BST fragt, ob die Summe der Werte zweier beliebiger Knoten einem Zielwert entspricht. Ein Ansatz verwendet eine Menge: Die Inorder-Traversierung sammelt Werte und prüft dabei, ob target - current bereits in der Menge enthalten ist. Ein eleganterer Ansatz verwendet gleichzeitig einen BST-Iterator vorwärts und einen BST-Iterator rückwärts (ähnlich wie zwei Zeiger) – dadurch wird zusätzlicher Speicher über O(h) für den Stack jedes Iterators hinaus vermieden.
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)) # FalseBST in einen Greater-Sum-Tree umwandeln
Der Greater-Sum-Tree (LeetCode #538) ersetzt den Wert jedes Knotens durch die Summe aller Werte, die im BST größer oder gleich diesem Wert sind. Die entscheidende Erkenntnis: Führen Sie eine umgekehrte Inorder-Traversierung (rechts → Wurzel → links) durch, um die Knoten in absteigender Reihenfolge zu besuchen und eine laufende Summe zu bilden. Dies benötigt O(n) Zeit und O(h) Speicher.
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 = 18Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie Folgendes gelernt: die drei Fälle beim Löschen in einem BST (Blatt, ein Kind, zwei Kinder), die Technik mit dem Inorder-Nachfolger zum Löschen eines Knotens mit zwei Kindern sowie saubere rekursive Muster wie den BST-Iterator und den Greater-Sum-Tree. Als Nächstes überprüfen wir die Korrektheit von BSTs und nutzen Inorder-Eigenschaften.
Häufig gestellte Fragen
Ist die Lektion „BST-Löschen: drei Fälle“ kostenlos?
Ja — der vollständige Text von „BST-Löschen: drei Fälle“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „BST-Löschen: drei Fälle“?
Behandeln Sie das Löschen eines Blatts, eines Knotens mit einem Kind und eines Knotens mit zwei Kindern mithilfe des In-Order-Nachfolgers und implementieren Sie den Algorithmus von Grund auf. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „BST-Löschen: drei Fälle“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- BST-Einfügen und -Suchen
- BST-Löschen: drei Fälle
- BST und In-Order-Eigenschaften validieren
- K-kleinstes Element, Bereichssumme und BST zu sortiertem Array