Eliminazione da un BST: tre casi
Gestisca l'eliminazione di una foglia, di un nodo con un solo figlio e di un nodo con due figli usando il successore in-order e implementando l'algoritmo da zero
Eliminazione da un BST: tre casi è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Perché l’eliminazione nei BST è complessa
L’eliminazione in un BST è la più complessa delle tre operazioni fondamentali, perché la rimozione di un nodo deve preservare la proprietà del BST nell’intero albero. Esistono tre casi distinti a seconda dei figli del nodo: nessun figlio, cioè una foglia; un figlio; oppure due figli. Ogni caso richiede una strategia diversa. Questo problema è molto apprezzato nei colloqui perché verifica la capacità di manipolare i puntatori, di ragionare sui casi limite e di comprendere il concetto di successore in-order.
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')Caso 1: eliminazione di un nodo foglia
Un nodo foglia non ha figli. L’eliminazione è semplice: si restituisca None dalla chiamata ricorsiva, facendo sì che il genitore imposti a null il proprio puntatore, sinistro o destro. Questo è il caso base che tutte le implementazioni dell’eliminazione nei BST devono gestire per primo. Si verifichi che funzioni anche nel caso speciale in cui l’albero abbia un solo nodo, ovvero quando la radice è una foglia.
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 intactCaso 2: nodo con un solo figlio
Quando un nodo ha esattamente un figlio, sostituisca il nodo con quel figlio. Restituisca il figlio non nullo dalla chiamata ricorsiva, in modo che il puntatore del padre venga aggiornato e salti il nodo eliminato. Funziona senza problemi sia quando l'unico figlio è a sinistra sia quando è a destra: è sufficiente restituire quello esistente.
# 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')Caso 3: nodo con due figli
Quando un nodo ha due figli, non è sufficiente rimuoverlo. Occorre invece trovare il successore in-order del nodo (il valore più piccolo nel sottoalbero destro), copiarne il valore nel nodo corrente e poi eliminare il successore in-order dal sottoalbero destro. Il successore ha al massimo un figlio (non ha un figlio sinistro), quindi la sua eliminazione rientra nel Caso 1 o nel Caso 2, che sappiamo già come gestire.
# 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')Implementazione completa dell'eliminazione in un BST
La procedura ricorsiva completa per l'eliminazione combina tutti e tre i casi. Trovi il nodo da eliminare confrontando i valori, quindi gestisca il caso appropriato. Il modello in cui si restituisce la radice, eventualmente modificata, a ogni livello e la si riassegna a root.left o root.right gestisce elegantemente tutti gli aggiornamenti dei puntatori senza dover tenere traccia esplicita del padre. La complessità temporale è 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)Perché il successore in-order?
Si usa il successore in-order (il minimo del sottoalbero destro) invece del massimo del sottoalbero sinistro perché entrambe sono scelte valide: usare l'una o l'altra preserva la proprietà del BST. Funziona anche il predecessore in-order (il massimo del sottoalbero sinistro). Alcune implementazioni alternano le due opzioni per mantenere l'albero bilanciato. Nei colloqui, è più comune aspettarsi la versione con il successore in-order; specifichi che anche il predecessore funziona altrettanto bene.
# 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')Eliminazione di tutti i nodi con un valore
Una variante richiede di eliminare tutti i nodi con valori compresi in un intervallo o che soddisfano una condizione. In un BST, questa operazione è efficiente: ricorra nel sottoalbero appropriato in base ai confronti, applicando l'eliminazione ogni volta che la condizione è soddisfatta. La struttura ricorsiva dell'eliminazione in un BST si estende naturalmente a questi scenari senza richiedere un passaggio di attraversamento separato.
# 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 2Pattern dell'iteratore BST
L'iteratore BST (LeetCode #173) restituisce gli elementi in ordine crescente, uno alla volta, con tempo medio O(1) e spazio O(h). Lo implementi con uno stack che simula l'attraversamento iterativo in-order: durante la costruzione, inserisca nello stack tutti i nodi sinistri partendo dalla radice. In next(), estragga l'elemento in cima e inserisca nello stack tutti i nodi sinistri del sottoalbero destro. Si tratta di un'espansione controllata dell'algoritmo iterativo di attraversamento in-order.
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 15Analisi della complessità dell'eliminazione di un nodo
L'eliminazione in un BST ha complessità temporale O(h), dove h è l'altezza dell'albero. In un BST bilanciato, la complessità è O(log n). In un albero sbilanciato, peggiora fino a O(n). Trovare il successore in-order aggiunge al massimo un ulteriore attraversamento di O(h) del sottoalbero destro, senza modificare la complessità complessiva. La complessità spaziale è O(h) per lo stack delle chiamate nell'implementazione ricorsiva.
# 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 un BST
Two Sum IV in un BST richiede di verificare se la somma di due nodi è uguale a un valore obiettivo. Un approccio usa un insieme: l'attraversamento in-order raccoglie i valori e, al contempo, verifica se target - current è già presente nell'insieme. Un approccio più elegante usa simultaneamente un iteratore BST in avanti e uno all'indietro, come due puntatori: in questo modo si evita spazio aggiuntivo oltre a O(h) per lo stack di ciascun iteratore.
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)) # FalseConversione di un BST in un Greater Sum Tree
Il greater sum tree (LeetCode #538) sostituisce il valore di ogni nodo con la somma di tutti i valori maggiori o uguali a esso nel BST. L'intuizione fondamentale è eseguire un attraversamento in-order inverso (destra → radice → sinistra) per visitare i nodi in ordine decrescente e accumulare una somma progressiva. La complessità è O(n) in tempo e O(h) in spazio.
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 = 18Verifica rapida
Metta alla prova la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato: i tre casi di eliminazione nei BST (foglia, un figlio, due figli), la tecnica del successore in-order per l'eliminazione di un nodo con due figli e schemi ricorsivi chiari come l'iteratore BST e la conversione da BST a greater sum tree. Il prossimo argomento riguarda la validazione della correttezza dei BST e l'uso delle proprietà dell'attraversamento in-order.
Domande Frequenti
La lezione «Eliminazione da un BST: tre casi» è gratuita?
Sì — il testo completo di «Eliminazione da un BST: tre casi» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Eliminazione da un BST: tre casi»?
Gestisca l'eliminazione di una foglia, di un nodo con un solo figlio e di un nodo con due figli usando il successore in-order e implementando l'algoritmo da zero Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Eliminazione da un BST: tre casi»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Inserimento e ricerca in un BST
- Eliminazione da un BST: tre casi
- Convalidare un BST e le proprietà in-order
- K-esimo più piccolo, somma degli intervalli e da BST ad array ordinato