Inserimento e ricerca in un BST
Implementi inserimento e ricerca ricorsivi e iterativi, tracci il percorso nell'albero per chiavi diverse e analizzi la complessità nel caso peggiore degli alberi non bilanciati
Inserimento e ricerca in un BST è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 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 Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Definizione della proprietà dei BST
Un Binary Search Tree soddisfa un unico vincolo: per ogni nodo, tutti i valori nel suo sottoalbero sinistro sono strettamente minori del valore del nodo e tutti i valori nel suo sottoalbero destro sono strettamente maggiori. Questa proprietà di ordinamento, mantenuta nell’intero sottoalbero e non solo nei figli immediati, consente di eseguire ricerca, inserimento ed eliminazione in O(log n) negli alberi bilanciati e distingue un BST da un albero binario generico.
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')Ricerca ricorsiva in un BST
La ricerca in un BST funziona come la ricerca binaria: si confronta il valore obiettivo con quello del nodo corrente e si esegue la ricorsione nel sottoalbero appropriato. Se il valore obiettivo è uguale a quello corrente, si restituisce il nodo. Se è minore, si procede a sinistra; se è maggiore, a destra. Si restituisca null quando si raggiunge un nodo vuoto. La complessità temporale è O(h): O(log n) per gli alberi bilanciati e O(n) per quelli degeneri.
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 foundRicerca iterativa in un BST
La ricerca iterativa evita l’overhead dello stack delle chiamate ed è preferibile nel codice di produzione. Si usi un puntatore curr che percorre l’albero seguendo il ramo sinistro o destro in base ai confronti. Si tratta di un semplice ciclo while con tre casi: null (non trovato), corrispondenza (trovato) oppure modifica della direzione. Anche la ricerca iterativa ha complessità O(h), ma usa O(1) spazio invece di O(h) come la versione ricorsiva.
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)) # NoneInserimento ricorsivo in un BST
L’inserimento in un BST trova la posizione corretta seguendo le stesse decisioni sinistra/destra della ricerca, poi collega un nuovo nodo alla prima posizione null raggiunta. L’approccio ricorsivo restituisce la radice, eventualmente nuova, di ciascun sottoalbero: se il nodo corrente è null, si restituisce un nuovo TreeNode; altrimenti si aggiorna root.left o root.right con il risultato della chiamata ricorsiva. Questo schema è chiaro e comune nelle soluzioni dei colloqui tecnici.
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) # 5Inserimento iterativo in un BST
L’inserimento iterativo usa un puntatore parent per tenere traccia dell’ultimo nodo non nullo prima di raggiungere il punto di inserimento. Si percorre l’albero come nella ricerca, tenendo traccia del genitore e dell’ultima direzione seguita. Quando si raggiunge null, si collega il nuovo nodo al lato appropriato del genitore. Si gestisca sempre separatamente il caso limite dell’albero vuoto, in cui root è null.
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 nel caso peggiore: alberi degeneri
Se si inserisce una sequenza ordinata in un BST, si ottiene un albero degenere che si riduce a una lista collegata. Ricerca, inserimento ed eliminazione diventano tutte operazioni O(n). Per questo esistono i BST bilanciati, come gli alberi AVL e gli alberi Red-Black. Nei colloqui, quando viene chiesta la complessità di un BST, si menzioni sempre questo caso peggiore: dire «O(log n) in media, O(n) nel caso peggiore per gli alberi non bilanciati» dimostra una comprensione approfondita.
# 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)Ricerca del minimo e del massimo
In un BST, il valore minimo si trova sempre nel nodo più a sinistra: si continua a procedere a sinistra fino a raggiungere null. Il valore massimo si trova invece nel nodo più a destra. Queste operazioni O(h) vengono usate spesso come funzioni di supporto nell’eliminazione da un BST, per trovare il successore in-order, e nelle query sugli intervalli. Conoscere bene queste funzioni fa risparmiare tempo nei colloqui.
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) # 9Successore e predecessore in-order
Il successore in-order di un nodo è il nodo con il valore maggiore più piccolo del suo. Se il nodo ha un sottoalbero destro, il successore è find_min(node.right). Se non ha un sottoalbero destro, il successore è l’antenato più basso per il quale il nodo dato si trova nel sottoalbero sinistro. Comprendere questo concetto è fondamentale per i problemi di eliminazione nei BST e di iteratori 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) # 1Analisi della complessità della ricerca nei BST
Le prestazioni di un BST dipendono interamente dall’altezza dell’albero. Per un BST bilanciato con n nodi, l’altezza è O(log n), quindi ricerca, inserimento ed eliminazione hanno complessità O(log n). Per un BST degenere, l’altezza è O(n), quindi tutte le operazioni hanno complessità O(n). Python non dispone di un BST bilanciato integrato, a differenza di Java con TreeMap; è quindi necessario implementare autonomamente un albero AVL o Red-Black, usare sortedcontainers.SortedList oppure affidarsi a un heap nei casi d’uso delle code con 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')Casi limite dell’inserimento in un BST
Si verifichi sempre che l’inserimento gestisca: l’albero vuoto, restituendo il nuovo nodo come radice; i valori duplicati, definendo se ignorarli, inserirli a sinistra o inserirli a destra e mantenendo coerente la scelta; e i valori molto grandi o molto piccoli. Nei colloqui, si dichiari l’ipotesi sui duplicati prima di scrivere il codice. La convenzione più comune nei problemi di LeetCode è che tutti i valori siano distinti, salvo diversa indicazione.
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 da un array ordinato
La costruzione di un BST bilanciato in altezza a partire da un array ordinato (LeetCode #108) usa il divide et impera: l’elemento centrale diventa la radice, la metà sinistra diventa il sottoalbero sinistro e la metà destra diventa il sottoalbero destro. In questo modo si garantisce un albero bilanciato con altezza O(log n). La complessità temporale è O(n), perché ogni elemento viene elaborato una sola volta.
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) # 9Verifica rapida
Verifichi la comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep affrontati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato: la proprietà dei BST (sottoalbero sinistro strettamente minore, sottoalbero destro strettamente maggiore), la ricerca e l’inserimento sia in modo ricorsivo sia iterativo con complessità O(h) e gli alberi degeneri nel caso peggiore, in cui l’altezza è uguale a n. Ora affronteremo l’eliminazione nei BST e i suoi tre casi.
Domande Frequenti
La lezione «Inserimento e ricerca in un BST» è gratuita?
Sì — il testo completo di «Inserimento e ricerca in un BST» è 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 Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Inserimento e ricerca in un BST»?
Implementi inserimento e ricerca ricorsivi e iterativi, tracci il percorso nell'albero per chiavi diverse e analizzi la complessità nel caso peggiore degli alberi non bilanciati Eserciti Coding 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 Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding 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 1 di 4.
Quanto tempo richiede la lezione «Inserimento e ricerca in un BST»?
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 Coding Interview Prep?
Sì. Ogni lezione Coding 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