Esercizi di programmazione in Pascal->Albero binario di ricerca

Albero binario di ricerca

In questo piccolo tutorial verrà spiegato l'implementazione del classico albero binario di ricerca.
Un albero binario di ricerca è una struttura dati organizzata come un albero, dove ad ogni nodo c'è una chiave e tre campi chiamati rispettivamente padre, sinistra e destra che contengono rispettivamente il puntatore al nodo padre, il puntatore al nodo destro ed il puntatore al nodo sinistro. Se un campo non punta ad un'altro nodo allora contiene il valore NIL. Solo il nodo radice ha in campo padre a NIL, mentre il nodo foglia ha i due campi sinistra e destra rispettivamente a NIL. I momi di questi campi sono derivati dal modo in cui l'albero può essere disegnato.
La proprietà di un albero binario di ricerca è che la chiave del nodo sinistro è più piccola della chiave del nodo padre, e la chiave del nodo destro è più grande.

Le operazioni che verranno implementate sono: inserimento, ordinamento, ricerca, calcolo del valore massimo, calcolo del valore minimo, ricerca del successore, ricerca del predecessore ed eliminazione.
Vediamo la definizione del nodo dell'albero.
L'inserimento di un nodo in un albero avviene eseguendo una scansione in base al valore della chiave.
La scansione considera la proprietà che a sinistra ci sono i valori più piccoli e a destra ci sono i valori più grandi. La scansione termina quando si incontra un nodo foglia o eventualmente un nodo interno con il campo figlio a NIL (a destra o a sinistra in base alla scansione che si sta eseguendo).
Vediamo il codice:
L'operazione di ordinamento, per come sono disposti i nodi è piuttosto semplice in quanto consiste in una semplice scansione del'albero da sinistra verso destra.
Vediamo il codice:
La ricerca del nodo mediante una data chiave consiste nella scansione dell'albero in base la proprietà che a sinistra ci sono i valori più piccoli e a destra ci sono i valori più grandi.
Vediamo il codice:
La ricerca del valore massimo consiste nella semplice scansione dell'albero verso destra in quanto i nodi a destra contengono i valori più grandi. Il valore massimo si trova nella foglia.
Vediamo il codice:
La ricerca del valore minimo è analoga alla ricerca del valore massimo e consiste nella semplice scansione dell'albero verso sinistra. Il valore minimo si trova nella foglia.
Vediamo il codice:
Il successore di un nodo x è il nodo dell'albero con la chiave più piccola ma più grande della chiave di x.
Partendo dal nodo x, se esiste un sottoalbero a destra allora il nodo più a sinistra di quel sottoalbero è il successore; ovviamente il nodo più a sinistra di un sottoalbero corrisponde al nodo con la chiave più piccola. Se il campo a destra è a NIL allora occorre risalire l'albero verso l'alto (se il padre non è NIL) e cercare il nodo antenato più vicino a x che ha un figlio sinistro ancora antenato di x.
Vediamo il codice:
Il predecessore di un nodo x è il nodo dell'albero con la chiave più grande ma più piccola della chiave di x.
Partendo dal nodo x, se esiste un sottoalbero a sinistra allora il nodo più a destra di quel sottoalbero è il predecessore; ovviamente il nodo più a destra di un sottoalbero corrisponde al nodo con la chiave più grande. Se il campo a sinistra è a NIL allora occorre risalire l'albero verso l'alto (se il padre non è NIL) e cercare il nodo antenato più vicino a x che ha un figlio destro ancora antenato di x.
Vediamo il codice:
L'eliminazione di un nodo z senza figli è molto semplice, si elimina il nodo, e si imposta al padre nel campo destra o sinistra (in base a quale puntava a z) il valore NIL. Se z ha un figlio allora si elimina il nodo ed il campo (destra o sinistra) del padre deve puntare al figlio di z. Nel caso in cui z ha due figli allora occorre scambiare il valore di z con il valore del suo successore y, quindi si elimina il nodo y. Si noti che y come successore di z è il nodo più a sinistra del sottoalbero a destra di z, quindi y ha al massimo un figlio a destra. In quel caso il campo (destra o sinistra) del padre di y deve puntare al figlio di y.
Il codice di seguito viene sintetizzato in questo modo: nella variabile y viene inserito il nodo da eliminare che può essere z se ha al massimo un figlio, oppure il suo successore. In entrambi i casi il nodo contenuto in y ha al massimo un figlio. Nella variabile x andiamo ad inserire il figlio di y se c'è l'ha oppure NIL. Se x contiene un nodo allora impostiamo nel campo padre il padre di y. Se il campo padre del nodo y è NIL allora il nodo y è la radice dell'albero quindi impostiamo la variabile t (contenente la radice dell'albero) uguale a x. Se il campo padre del nodo y non è NIL, allora il campo (destra o sinistra) del padre del nodo y deve puntare al nodo x. Infine si può distruggere il nodo y.
Vediamo il codice:

Ora che abbiamo implementato tutte le operazioni sull'albero binario di ricerca, possiamo implementare le operazioni che consentono ad un utente di eseguirle.

La procedura seguente serve semplicemente per creare una pausa al termine di ogni operazione.
Vediamo il codice:
Per l'inserimento, viene richiesto all'utente il valore da inserire, quindi viene richiamata la procedura di inserimento del nodo.
Vediamo il codice:
Per l'ordinamento, viene richiamata la procedura di ordinamento dell'albero se l'albero contiene almeno un nodo.
Vediamo il codice:
Per la ricerca, viene richiesto all'utente il valore da trovare, quindi se l'albero contiene almeno un nodo viene richiamata la procedura di ricerca nell'albero.
Vediamo il codice:
Per la ricerca del massimo, viene richiamata la procedura di ricerca del massimo dell'albero se l'albero contiene almeno un nodo.
Vediamo il codice:
Per la ricerca del minimo, viene richiamata la procedura di ricerca del minimo dell'albero se l'albero contiene almeno un nodo.
Vediamo il codice:
Per la determinazione del successore, viene richiesto all'utente un valore, quindi se l'albero contiene almeno un nodo viene chiamata la funzione per cercare il nodo y contenente il valore dato dall'utente. Poi viene richiamata la funzione per calcolare il successore di un nodo. Se il valore dato dall'utente non è la chiave più grande dell'albero allora viene visualizzata la chiave del suo successore.
Vediamo il codice:
Per la determinazione del precedessore, viene richiesto all'utente un valore, quindi se l'albero contiene almeno un nodo viene chiamata la funzione per cercare il nodo y contenente il valore dato dall'utente. Poi viene richiamata la funzione per calcolare il precedessore di un nodo. Se il valore dato dall'utente non è la chiave più picola dell'albero allora viene visualizzata la chiave del suo precedessore.
Vediamo il codice:
Per l'eliminazione, viene richiesto all'utente il valore del nodo da eliminare, quindi se l'albero contiene almeno un nodo viene chiamata la funzione per cercare il nodo y contenente il valore dato dall'utente. Poi viene richiamata la funzione per eliminare il nodo.
Vediamo il codice:
Il corpo del programma è caratterizato da un menu dove l'utente può scegliere le operazioni da eseguire. Vediamo di seguito il codice.

Compilato con Free Pascal 2.2.4 (compatibile con Vista)
Scarica sorgente ed eseguibile (27 Kb)