LabASD - Alberi binari di ricerca

Il file bst.h contiene l’interfaccia della struttura dati Albero Binario di Ricerca (BST, binary search tree). Completare l’implementazione realizzando le funzioni indicate. È possibile definire ulteriori funzioni di supporto, se lo si ritiene necessario.

typedef struct {
    BSTNode *root;
    int size;
} BST;

dove root punta alla radice dell’albero, oppure a NULL se l’albero è vuoto, e size è il numero di nodi. Il campo size consente di conoscere il numero di nodi dell’albero in tempo \(O(1)\), senza bisogno di contarli ogni volta; occorre però mantenere aggiornato tale valore durante le operazioni di inserimento e cancellazione.

typedef int BSTKey;

typedef struct BSTNode {
    BSTKey key;
    struct BSTNode *parent, *left, *right;
} BSTNode;

dove BSTKey è il tipo dell’informazione associata ai nodi (di default è un intero), mentre parent, left e right sono puntatori al padre, al figlio sinistro e al figlio destro; nel nodo radice si avrà parent == NULL. Un esempio è mostrato nella Figura 1.

Le operazioni di inserimento e ricerca non dovrebbero presentare difficoltà; personalmente ritengo più semplice implementarle in forma ricorsiva, ma è possibile realizzarle in forma iterativa come visto a lezione. Le implementazioni ricorsive richiederanno la definizione di ulteriori funzioni a supporto.

In questa implementazione dei BST occorre mantenere la seguente proprietà di ordine:

L’operazione più complessa è la cancellazione. Esistono numerose varianti della procedura di cancellazione, ma si suggerisce di seguire quella descritta nel libro: se il nodo da cancellare ha due figli, si rimpiazza la chiave in esso contenuta con la chiave minima del sottoalbero destro. In alternativa si può anche rimpiazzare la chiave con il massimo del sottoalbero sinistro.

La funzione bst_pretty_print() (da lasciare per ultima perché è la meno importante) deve stampare il contenuto di un BST in modo “leggibile” ruotando l’output di 90 gradi.

Il programma bst-main.c legge una sequenza di comandi da un file il cui nome va specificato come unico parametro sulla riga di comando. I comandi sono descritti nella Tabella 1, dove k è una chiave intera.

Tabella 1: Comandi nel file di input
Comando	Significato
`+` k	Inserisce la chiave k, se non presente
`-` k	Cancella il nodo contenente k, se presente
`?` k	Verifica se la chiave k è presente
`s`	Stampa il numero di nodi nell’albero
`h`	Stampa l’altezza dell’albero
`p`	Stampa il contenuto dell’albero

Tabella 1: Comandi nel file di input

+ k

Inserisce la chiave k, se non presente

- k

Cancella il nodo contenente k, se presente

? k

Verifica se la chiave k è presente

s

Stampa il numero di nodi nell’albero

h

Stampa l’altezza dell’albero

p

Stampa il contenuto dell’albero

Per approfondire

Scrivere una funzione che, dato un intero \(n > 0\), inserisca le chiavi \(\{0, 1, \ldots, n - 1\}\) in un BST inizialmente vuoto in modo da ottenere un albero di altezza minima possibile.

Le procedure di inserimento e ricerca possono essere espresse in modo iterativo (come fatto nel libro di testo) oppure ricorsivo. È istruttivo provare ad implementarle in entrambi i modi.

[Difficile] Qual è l’altezza media di un BST in cui vengono inserite \(n\) chiavi casuali? È stato dimostrato che l’altezza media è \(\left(\alpha \ln n - \beta \ln \ln n + O(1)\right)\), con \(\alpha \approx 4.311\) e \(\beta \approx 1.953\). Provare a verificare sperimentalmente questo risultato, considerando diversi valori di \(n\), ad esempio \(n=1000, 2000, 3000, \ldots, 20000\). Per ogni \(n\) si generino 100 alberi, ciascuno contenente \(n\) chiavi generate casualmente, e si calcoli l’altezza media di ogni gruppo di 100 alberi. Alla fine si riporti su un grafico l’altezza media in funzione di \(n\).

Per approfondire

File