Albero binario di ricerca

Istruzioni

Inserisci e cerca numeri in un albero binario.

Quando dobbiamo rappresentare dati ordinati, un array non è una buona struttura dati.

Prendiamo l'array [1, 3, 4, 5] e aggiungiamoci 2, così diventa [1, 3, 4, 5, 2]. Adesso dobbiamo ordinare di nuovo l'intero array! Possiamo migliorare la situazione rendendoci conto che ci basta fare spazio per il nuovo elemento [1, nil, 3, 4, 5] e poi inserirlo nello spazio che abbiamo creato. Ma questo ci obbliga comunque a spostare molti elementi di una posizione.

Gli alberi binari di ricerca, invece, riescono a lavorare su dati ordinati in modo molto più efficiente.

Un albero binario di ricerca è formato da una serie di nodi collegati tra loro. Ogni nodo contiene un dato (ad esempio il numero 3), una variabile chiamata left e una variabile chiamata right. Le variabili left e right puntano a nil o ad altri nodi. Dato che questi altri nodi hanno a loro volta altri nodi sotto di sé, diciamo che le variabili left e right puntano a dei sottoalberi. Tutti i dati nel sottoalbero sinistro sono minori o uguali al dato del nodo corrente, e tutti i dati nel sottoalbero destro sono maggiori del dato del nodo corrente.

Ad esempio, se avessimo un nodo contenente il dato 4 e aggiungessimo il dato 2, il nostro albero apparirebbe così:

  4
 /
2

Se poi aggiungessimo 6, apparirebbe così:

  4
 / \
2   6

Se poi aggiungessimo 3, apparirebbe così

   4
 /   \
2     6
 \
  3

E se poi aggiungessimo 1, 5 e 7, apparirebbe così

      4
    /   \
   /     \
  2       6
 / \     / \
1   3   5   7

Suggerimenti

Per completare questo esercizio devi creare il tipo di dato BST, con le istanze Eq e Show, e implementare le funzioni:

• bstLeft
• bstRight
• bstValue
• empty
• fromList
• insert
• singleton
• toList

Troverai già una dichiarazione di dati fittizia e le firme dei tipi, ma starà a te definire le funzioni e creare un tipo di dato, un newtype o un sinonimo di tipo significativo.