Definizione
Un albero binario è ordinato, e viene anche chiamato albero binario di ricerca, binary search tree (BST), quando il campo chiave di ogni nodo è minore del campo chiave di ogni nodo del suo sottoalbero destro ed è maggiore del campo chiave di ogni nodo del suo sottoalbero sinistro.
Un esempio di BST
In questo caso l'ordine è quello lessicografico.
Un esempio di BST (segue)
Gli stessi dati possono essere contenuti in alberi BST di forma diversa.
Albero bilanciato
Un albero si dice bilanciato se il livello di tutte le foglie è uguale all'altezza dell'albero o a questa stessa altezza meno 1.
Albero non bilanciato
L'albero è non bilanciato in quanto ci sono foglie al livello 2 e foglie ai livelli 3, 4, 5.
Albero binario
Se un albero è bilanciato allora per fare una ricerca di una chiave in esso contenuta si esplora in un numero di passi inferiore a quello necessario per esplorare un albero non bilanciato.
Come si può osservare nell’esempio degli alberi mostrati nella figura successiva pur essendo tutti alberi BST la ricerca della chiave Riccardo viene fatta in un numero di passi decisamente diverso a seconda se l’albero è o non bilanciato.
Albero binario
Albero binario
Se un albero bilanciato ha M livelli, il numero di nodi di cui è formato può variare tra
2M e 2(M+1) -1
In un albero bilanciato il numero di passi massimo di ricerca è di O(log2 (N)) dove N è il numero di nodi.
Albero bilanciato con M livelli
Da questa immagine si ricava facilmente che il numero di nodi N di un albero bilanciato, nota l’altezza dell’albero pari a M (o M+1) è data: (vedi figura).
Albero bilanciato con M livelli (segue)
Albero bilanciato con M livelli (segue)
Per trovare, quindi, una chiave in un dato BST, se esso è bilanciato il numero massimo di passi è dato dall’altezza dell’albero M. Poichè abbiamo mostrato che 2M≤N≤2M+1-1.
Da questa espressione per ricavare N, supposto M abbastanza grande, e quindi -1 trascurabile abbiamo:
N ≅ 2M da cui M ≅ log2N
Quindi per un albero bilanciato, con N nodi, il numero di passi massimo per trovare una chiave è pari O(log2N), nel caso l’albero non fosse bilanciato il massimo numero di passi sarà pari a O(N).
Albero binario
Nella figura è illustrato il caso peggiore per il quale la ricerca può essere, nel caso peggiore fatta in O(N) passi.
Si può dimostrare che un albero di ricerca binario costruito in maniera casuale, quindi non necessariamente bilanciato, effettua in media un numero di passi per effettuare la ricerca pari a 1.36 * O(log2(N)).
Albero binario (segue)
Per avere un’idea della differenza che intercorre tra i valori O(N), log2(N) e 1.36* log(N) riportiamo nella tabella che segue i valori delle tra funzioni corrispondenti a diversi valori di N.
Albero binario (segue)
Di seguito ci rifaremo alla seguente struct per definire un nodo di un albero:
struct RTnodo
{
int key;
RTnodo *left, *right;
};
typedef RTnodo* Tnodo;
Per esplorare un albero vi sono tre diverse modalità.
Algoritmi di attraversamento di BST
INORDER. Visitare tutti i nodi di un BST di interi, attraversando:
- il sotto albero sinistro;
- la radice;
- il sotto albero destro;
PREORDER. Visitare tutti i nodi di un BST di interi, attraversando:
- la radice;
- il sotto albero sinistro;
- il sotto albero destro;
POSTORDER. Visitare tutti i nodi di un BST di interi, attraversando:
- il sotto albero sinistro;
- il sotto albero destro;
- la radice;
I codici per gli attraversamenti
I codici per gli attraversamenti
Dato l’albero di figura (foto in alto)
un esempio di output è riprodotto nella foto in basso.
Allegato: visite
Per utilizzare il codice visite è necessario costruire un file di nome TREE1 .txt in cui vanno inserite le chiavi dei singoli nodi dell’albero che si vuole costruire.
Operazioni sui BST
Poiché ogni nodo di un BST punta ad altri due nodi, ciascuno dei quali è una variabile dinamica di tipo struct avremo che una variabile di tipo RTnodo, cioè un puntatore alla radice di un BST, è a sua volta una variabile BST, e può quindi essere passata da un blocco ad un altro.
In altre parole dato un nodo di un BST, questo è radice per i suoi sottoalberi e i nodi a cui punta sono a loro volta radici di altri sottoalberi.
Pertanto possiamo adoperare ricorsivamente queste variabili.
Operazioni sui BST (segue)
Le principali operazioni che ci interessa definire sono:
- Creazione di un albero
- Inserimento di un nuovo nodo con un valore assegnato al campo dati Key e NULL ai campi Left e Right
- Cancellazione di un nodo
- Selezionare un nodo data una chiave
- Fornire informazioni sull’albero (altezza, numero nodi, livelli, figli, etc.)
