Radice
L’unico nodo senza padre; è il punto d’ingresso della struttura.
Algoritmi · Strutture dati
Alberi binari di ricerca e rotazioni
Un albero binario di ricerca mantiene le chiavi in un ordine che guida ogni decisione: più piccolo a sinistra, più grande a destra. La sua efficienza dipende dalla forma dell’albero, non soltanto dal numero di nodi.
La proprietà che rende possibile la ricerca
Sottoalbero sinistrochiavi minori
vnodo corrente
Sottoalbero destrochiavi maggiori
Per ogni nodo v: chiavi(sinistra(v)) < v < chiavi(destra(v))
La condizione deve valere per interi sottoalberi, non soltanto per i due figli immediati. Per semplicità il laboratorio non accetta duplicati; in un’implementazione reale va scelta e documentata una politica coerente.
Conseguenza fondamentale: la visita in-order di un BST produce tutte le chiavi in ordine crescente.
Anatomia e vocabolario
Foglia
Un nodo senza figli. Un nodo può anche avere un solo figlio.
Profondità
Numero di archi dalla radice al nodo. La radice ha profondità 0.
Altezza
Numero di livelli sul cammino più lungo. Qui un albero vuoto ha altezza 0 e una foglia altezza 1.
Laboratorio: modifica l’albero
I nodi sono selezionabili. Le rotazioni agiscono sul nodo selezionato; ricerca, inserimento ed eliminazione mostrano il cammino seguito dai confronti.
- Nodi
- 0
- Altezza
- 0
- Confronti
- 0
- Forma
- —
In-order
Pre-order
Post-order
selezionato
cammino visitato
nodo promosso o modificato
Ricerca, inserimento ed eliminazione
Ricerca
Confronta la chiave con il nodo: termina se è uguale, vai a sinistra se è minore, a destra se è maggiore.
Inserimento
Segue lo stesso cammino della ricerca e collega una nuova foglia al primo puntatore vuoto.
Eliminazione
Una foglia si rimuove; un nodo con un figlio si sostituisce con quel figlio; con due figli si usa il successore in-order.
Il caso delicato è l’eliminazione con due figli. Il successore è il minimo del sottoalbero destro: non ha figlio sinistro, quindi la sua rimozione ricade in uno dei casi semplici.
Rotazioni: cambiare la forma senza cambiare l’ordine
Una rotazione è una modifica locale in tempo Θ(1). Conserva tutte le relazioni di ordinamento e quindi lascia invariata la visita in-order.
Rotazione sinistra attorno a x
x y
/ \ / \
A y → x C
/ \ / \
B C A B
Richiede un figlio destro y. y viene promosso; il sottoalbero B passa da sinistra di y a destra di x.
Rotazione destra attorno a y
y x
/ \ / \
x C → A y
/ \ / \
A B B C
È l’operazione inversa. Richiede un figlio sinistro x e trasferisce B da destra di x a sinistra di y.
Una rotazione non sceglie da sola dove bilanciare. AVL e red-black tree aggiungono invarianti e regole che stabiliscono quando e quali rotazioni eseguire.
La complessità dipende dall’altezza
| Operazione | Costo | Albero bilanciato | Caso peggiore |
|---|---|---|---|
| Ricerca | Θ(h) | Θ(log n) | Θ(n) |
| Inserimento | Θ(h) | Θ(log n) | Θ(n) |
| Eliminazione | Θ(h) | Θ(log n) | Θ(n) |
| Minimo / massimo | Θ(h) | Θ(log n) | Θ(n) |
| Una rotazione | Θ(1) | Θ(1) | Θ(1) |
| Visita completa | Θ(n) | Θ(n) | Θ(n) |
Bilanciato
h = Θ(log n)Ogni confronto elimina circa metà dei candidati.
Degenerato
h = Θ(n)Valori inseriti già ordinati possono creare una lista collegata mascherata da albero.
Tre visite in profondità
In-order · LNR
Sinistra, nodo, destra. In un BST restituisce le chiavi ordinate.
Pre-order · NLR
Nodo, sinistra, destra. Utile per serializzare o ricostruire la forma.
Post-order · LRN
Sinistra, destra, nodo. Utile quando i figli vanno elaborati prima del padre.
Errori comuni
- Verificare soltanto che figlio sinistro < padre < figlio destro: il vincolo riguarda tutti i discendenti.
- Dimenticare di aggiornare il padre o la radice durante una rotazione, perdendo un intero sottoalbero.
- Scambiare le chiavi durante una rotazione: le chiavi non cambiano, cambiano soltanto i collegamenti.
- Affermare che ogni BST ha operazioni Θ(log n): vale soltanto quando l’altezza è logaritmica.
- Non stabilire una politica per i duplicati, rendendo ambigua la proprietà di ordinamento.