Ultimo aggiornamento: 2021-04-19
Implementare un albero binario di ricerca (BST, binary search tree) non bilanciato.
Il file bst.h contiene la specifica dell'interfaccia del BST. Si chiede di realizzare le funzioni indicate. È possibile definire ulteriori funzioni che si ritengano necessarie.
Un nodo di un BST è definito dalla struttura:
typedef int BSTKey;
typedef struct BSTNode {
struct BSTNode *parent, *left, *right;
BSTKey key;
} BSTNode;dove BSTKey è il tipo dell'informazione mantenuta in ciascun nodo (di default, un valore intero), mentre parent, left e right sono rispettivamente puntatori al padre, al figlio sinistro e al figlio destro. Nel caso della radice si avrà parent == NULL. Un esempio è mostrato nella Figura 1.
La specifica delle funzioni è indicata nel file bst.h. La funzione bst_pretty_print() (che suggerisco di lasciare per ultima, dato che è la meno importante) stampa un BST in modo un po' più leggibile, ruotando di 90 gradi quanto viene stampato.
Ad esempio, la funzione bst_pretty_print() potrebbe produrre l'output seguente:
55
12
9
5
-3che rappresenta l'albero:
12
/ \
5 55
/ \
-3 9Il programma bst-main.c legge da standard input una sequenza di comandi, uno per ogni riga, che manipolano un BST inizialmente vuoto. I comandi sono descritti nella tabella seguente, dove k è una chiave intera.
| Comando | Significato |
|---|---|
+ k |
Inserisci la chiave k |
- k |
Cancella il nodo contenente k, se presente |
? k |
Verifica se la chiave k è presente |
s |
Stampa il numero di nodi (size) nell'albero |
h |
Stampa l'altezza dell'albero |
p |
Stampa il contenuto dell'albero |
Un esempio di file di input è bst.in.
Per compilare:
gcc -std=c90 -Wall -Wpedantic bst.c bst-main.c -o bst-mainPer eseguire:
./bst-main < bst.inoppure
./bst-main bst.inSi assuma che BSTKey sia il tipo int.
Scrivere una funzione che inserisca gli interi \(\{0, 1, \ldots, n - 1\}\) in un BST inizialmente vuoto in modo da ottenere un albero di altezza minima; se lo si ritiene utile, si può assumere che \(n\) sia una qualche potenza di due.
È possibile mantenere in ciascun nodo l'informazione sull'altezza del sottoalbero radicato in quel nodo. Questo consentirebbe di realizzare la funzione bst_height() in tempo \(O(1)\), a patto di riuscire a mantenere efficientemente l'altezza di ciascun nodo anche dopo inserimenti e cancellazioni. Modificare le funzioni bst_insert() e bst_delete() perché aggiornino le altezze contenute in tutti i nodi che si trovano lungo il cammino che va dal nodo inserito/cancellato fino alla radice dell'albero.
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.
Qual è l'altezza media di un BST in cui vengono inserite \(n\) chiavi casuali uniformemente distribuite in un qualche intervallo di valori? Si provi a determinarla sperimentalmente, ripetendo l'inserimento di \(n\) valori casuali e calcolando la media delle altezze ottenute. È 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\).