Alberi binari di ricerca

Un albero binario di ricerca bilanciato di 1023 chiavi ne trova una qualsiasi in al massimo 10 confronti; costruito da dati ordinati, le stesse chiavi possono richiederne 1023.

La ricerca binaria, costruita nella forma

La ricerca binaria su un array ordinato trova una chiave in circa log₂ n controlli, ma inserire in un array ordinato sposta valori. Una tabella hash inserisce in fretta, ma dimentica l'ordine: non sa dirti facilmente la chiave più piccola o la chiave che viene dopo 40. Un albero binario di ricerca (ABR, in inglese BST) punta a entrambe le cose. È fatto di nodi, come una lista concatenata, ma ogni nodo ha due puntatori, left e right. Il nodo in cima è la radice; un nodo senza figli è una foglia.

Una sola regola lo rende un albero di ricerca: per ogni nodo, tutte le chiavi del sottoalbero sinistro sono più piccole e tutte le chiavi del sottoalbero destro sono più grandi. Per cercare una chiave parti dalla radice e confronta. Uguale significa trovata. Più piccola significa vai a sinistra, più grande significa vai a destra. Ogni confronto scarta un intero sottoalbero, proprio come la ricerca binaria scarta metà della lista. Cercare 60 nell'albero 50, 30, 70, 20, 40, 60, 80 confronta con 50, poi 70, poi 60: 3 confronti.

L'inserimento segue lo stesso percorso. Vai a sinistra o a destra finché il puntatore che ti serve è vuoto, e appendi lì il nuovo nodo. Inserire 45 confronta con 50 (vai a sinistra), 30 (vai a destra) e 40 (vai a destra), e 40 non ha un figlio destro, quindi 45 diventa il suo figlio destro. Eliminare un nodo che non è una foglia richiede un'idea in più: gli appunti del MIT scambiano il suo elemento con la chiave successiva o precedente nell'ordine ed eliminano da lì. La regola di conteggio nel laboratorio è un confronto per ogni nodo del percorso.

L'altezza è tutto

Quanti confronti può richiedere una ricerca? Al massimo uno per livello, quindi il costo dipende dall'altezza dell'albero, il numero di archi del percorso più lungo dalla radice fino a una foglia. Gli appunti del MIT lo dicono così: le operazioni sull'albero richiedono tempo O(h). L'albero 50, 30, 70, 20, 40, 60, 80 ha altezza 2, quindi nessuna ricerca richiede più di 3 confronti. Un albero perfettamente bilanciato con 1023 nodi ha altezza 9 e richiede al massimo 10 confronti.

Ma la forma dipende dall'ordine di inserimento. Inserisci 10, 20, 30, 40, 50, 60, 70 in ordine crescente: ogni chiave è più grande di tutte le precedenti, quindi ogni nuovo nodo va a destra dell'ultimo. L'albero diventa una catena di altezza 6, e cercare 70 richiede 7 confronti: una lista concatenata con puntatori in più. Con 1023 chiavi ordinate la ricerca peggiore richiede 1023 confronti invece di 10.

Gli alberi bilanciati risolvono il problema rimodellandosi dopo ogni inserimento o eliminazione. Il primo schema fu l'albero AVL, di Georgy Adelson-Velsky ed Evgenii Landis nel 1962, trattato nella lezione 7 del MIT. In ogni nodo mantiene le altezze dei due sottoalberi entro 1 l'una dall'altra, e ripara ogni squilibrio con piccole mosse locali chiamate rotazioni. Così l'altezza resta O(log n), e ricerca, inserimento ed eliminazione restano O(log n) in qualunque ordine arrivino le chiavi.

Le chiavi in ordine, gratis

Un ABR non dice soltanto se una chiave c'è. Visita il sottoalbero sinistro, poi il nodo, poi il sottoalbero destro, in modo ricorsivo, e le chiavi escono in ordine crescente. Questa visita simmetrica (il MIT la chiama traversal order) è il modo in cui un ABR risponde a «chiave più piccola», «chiave più grande» e «chiave successiva a 40», le operazioni d'ordine dell'interfaccia Set del MIT che una tabella hash non sa fare in fretta.