Un albero di ricerca binaria è un albero binario con un invariante di ordinamento: per ogni nodo, tutte le chiavi nel suo sottoalbero sinistro sono più piccole, e tutte le chiavi nel suo sottoalbero destro sono più grandi. Questo ti permette di cercare dimezzando il problema ad ogni passo.
8
/ \
3 10
/ \ \
1 6 14 left < node < right at every node
def search(node, key):
while node:
if key == node.val: return node
node = node.left if key < node.val else node.right # go one way
return None
def insert(node, key):
if node is None: return Node(key)
if key < node.val: node.left = insert(node.left, key)
else: node.right = insert(node.right, key)
return node
| Operazione | Bilanciato | Peggiore (degenerato) |
|---|---|---|
| search | O(log n) | O(n) |
| insert | O(log n) | O(n) |
| delete | O(log n) | O(n) |
Il caso peggiore si verifica quando le chiavi vengono inserite in ordine — l'albero degenera in una lista collegata di altezza n.
Gli BST ti danno dati ordinati e dinamici con operazioni logaritmiche — l'antenato concettuale degli indici di database e delle mappe ordinate.
Il problema della degenerazione motiva gli alberi auto-bilancianti, un argomento di follow-up cruciale nei colloqui.