BST-delete: tre tilfælde
Håndter sletning af blade, sletning af noder med ét barn og sletning af noder med to børn ved hjælp af in-order successor, og implementer algoritmen fra bunden.
BST-delete: tre tilfælde er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvorfor sletning i BST er vanskelig
Sletning i BST er den mest komplekse af de tre kerneoperationer, fordi fjernelse af en node skal bevare BST-egenskaben for hele træet. Der er tre forskellige tilfælde afhængigt af nodens børn: Den har ingen børn (blad), ét barn eller to børn. Hvert tilfælde kræver en anden strategi. Interviewere elsker dette problem, fordi det afprøver håndtering af pegefelter, evnen til at tænke på specialtilfælde og kendskab til begrebet in-order-efterfølger.
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')Tilfælde 1: Sletning af et blad
En bladnode har ingen børn. Sletning er enkel: returnér None fra det rekursive kald, hvilket får forælderen til at sætte sit pegefelt (venstre eller højre) til null. Dette er basistilfældet, som alle implementeringer af sletning i BST først skal håndtere. Kontrollér, at dette fungerer i specialtilfældet, hvor træet kun har én node (roden er et blad).
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 intactTilfælde 2: Knude med ét barn
Når en knude har præcis ét barn, erstatter du knuden med barnet. Returnér det barn, der ikke er null, fra det rekursive kald, så forælderens reference opdateres og springer den slettede knude over. Det fungerer problemfrit, uanset om det eneste barn er til venstre eller højre — returnér blot det af dem, der findes.
# 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')Tilfælde 3: Knude med to børn
Når en knude har to børn, kan du ikke bare fjerne den. Find i stedet knudens inorder-efterfølger (den mindste værdi i det højre undertræ), kopiér dens værdi til den aktuelle knude, og slet derefter inorder-efterfølgeren fra det højre undertræ. Efterfølgeren har højst ét barn (intet venstre barn), så sletningen falder ind under tilfælde 1 eller tilfælde 2 — som du allerede ved, hvordan du håndterer.
# 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')Komplet implementering af sletning i BST
Den komplette rekursive sletning kombinerer alle tre tilfælde. Find den knude, der skal slettes, ved at sammenligne værdier, og håndtér derefter det relevante tilfælde. Mønstret, hvor du returnerer den (muligvis ændrede) rod på hvert niveau og tildeler den tilbage til root.left eller root.right, håndterer elegant alle referenceopdateringer uden eksplicit at holde styr på forælderen. Tidskompleksiteten er 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)Hvorfor inorder-efterfølgeren?
Inorder-efterfølgeren (minimumsværdien i det højre undertræ) bruges i stedet for maksimumsværdien i det venstre undertræ, fordi begge valg er gyldige — begge bevarer BST-egenskaben. Inorder-forgængeren (maksimumsværdien i det venstre undertræ) fungerer også. Nogle implementeringer skifter mellem dem for at holde træet balanceret. Til interviews forventes versionen med inorder-efterfølgeren oftere; nævn, at forgængeren fungerer lige så godt.
# 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')Sletning af alle knuder med en værdi
En variant beder dig slette alle knuder med værdier inden for et interval eller alle knuder, der matcher en betingelse. For en BST er dette effektivt: rekursér ind i det relevante undertræ baseret på sammenligninger, og udfør sletteoperationen overalt, hvor betingelsen matcher. Den rekursive struktur i BST-sletning udvides naturligt til disse scenarier uden at kræve et separat gennemløb.
# 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-iteratorens mønster
BST-iteratoren (LeetCode #173) returnerer elementer i sorteret rækkefølge ét ad gangen med O(1) gennemsnitlig tid og O(h) plads. Implementér den med en stak, der simulerer det iterative inorder-gennemløb: ved konstruktionen lægger du alle venstre knuder fra roden på stakken. Ved next() tager du den øverste knude af stakken og lægger alle venstre knuder fra det højre undertræ på stakken. Dette er en kontrolleret udfoldning af den iterative inorder-algoritme.
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 15Sletning af knude: Analyse af kompleksitet
Sletning i en BST kører i O(h) tid, hvor h er træets højde. For en balanceret BST er dette O(log n). For et skævt træ forværres det til O(n). At finde inorder-efterfølgeren tilføjer højst ét ekstra O(h)-gennemløb af det højre undertræ, hvilket ikke ændrer den samlede kompleksitet. Pladskompleksiteten er O(h) for kaldestakken i den rekursive implementering.
# 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')To sum i en BST
Two Sum IV i en BST spørger, om to knuder tilsammen giver en bestemt målværdi. Én tilgang bruger en mængde: Et inorder-gennemløb samler værdier, mens det kontrollerer, om target - current allerede findes i mængden. En mere elegant tilgang bruger samtidig en BST-iterator fremad og en BST-iterator baglæns (som to pegere) — det undgår ekstra plads ud over O(h) for hver iterators stak.
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)) # FalseKonvertér BST til sumtræ med større værdier
Sumtræet med større værdier (LeetCode #538) erstatter hver knudes værdi med summen af alle værdier, der er større end eller lig med den, i BST'en. Den vigtige indsigt er at udføre et omvendt inorder-gennemløb (højre → rod → venstre), så knuderne besøges i faldende rækkefølge, mens du akkumulerer en løbende sum. Det kører i O(n) tid og bruger O(h) plads.
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 = 18Hurtig kontrol
Afprøv din forståelse af begreberne fra Data Structures & Algorithms — Coding Interview Prep i denne lektion.
Opsummering af lektionen
I denne lektion lærte du om: tre tilfælde ved sletning fra en BST (blad, ét barn, to børn), teknikken med inorder-efterfølgeren ved sletning af en knude med to børn samt rene rekursive mønstre som BST-iteratoren og BST-til-sumtræet med større værdier. Næste trin er at validere, om en BST er korrekt, og udnytte inorder-egenskaber.
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “BST-delete: tre tilfælde” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “BST-delete: tre tilfælde”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “BST-delete: tre tilfælde”?
Håndter sletning af blade, sletning af noder med ét barn og sletning af noder med to børn ved hjælp af in-order successor, og implementer algoritmen fra bunden. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.
Hvor lang tid tager lektionen “BST-delete: tre tilfælde”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- BST-insert og -søgning
- BST-delete: tre tilfælde
- Validering af BST og in-order-egenskaber
- K-te mindste, intervalsummmer og BST til sorteret array