All’interno di questo articolo andremo ad analizzare l’implementazione in linguaggio F# di alcune delle strutture dati più comuni ed utilizzate nella programmazione, gli alberi binari e gli alberi binari di ricerca.

Per la comprensione dei concetti contenuti in questo articolo sono necessarie alcune conoscenze di base in materia di strutture dati e di sintassi del linguaggio F#, per questo motivo consiglio la lettura dei seguenti articoli:

In seguito verranno comunque ripresi i concetti elementari.

Alberi e Alberi Binari

Un grafo non orientato G è una coppia G = (V, E) , dove V è un insieme (finito), i cui elementi sono detti nodi (o vertici) ed E è un sottoinsieme di V^2 , i cui elementi sono detti lati (o archi). Un grafo non orientato e senza cicli è detto foresta, se poi è anche connesso allora quest’ultimo viene detto albero.

Un albero binario è un albero radicato in cui ogni nodo interno ha al più due figli, ogni figlio viene distinto e identificato come figlio destro o figlio sinistro. L’altezza di un albero binario bilanciato, ovvero il percorso massimo tra la sua radice e la sua foglia è uguale a log_{2}(k) , dove k rappresenta il numero delle foglie contenute all’interno dell’albero.

algo_str16

L’altezza di un albero binario non bilanciato può invece oscillare tra il valore minimo di log_{2}(k) , fino al valore massimo di k-1 , che occorre quando l’albero è totalmente sbilanciato. Un albero è totalmente sbilanciato quando è rappresentato da un vettore.

log_{2}k \le h \le k-1

All’interno del capitolo dedicato alle Liste Polimorfe della guida Introduttiva al Linguaggio F#, abbiamo introdotto le tecniche utili alla realizzazione di un albero binario in modo ricorsivo. Ricordiamo ad esempio il codice presentato:

type 'a binTree =
    |Null                                   // Albero vuoto
    |Node of 'a * 'a binTree * 'a binTree;; // Nodo contenente tre riferimenti:
                                            // - valore nodo corrente
                                            // - nodo sinistro
                                            // - nodo destro

La definizione del tipo binTree (albero binario) è ovviamente ricorsiva, infatti all’interno della dichiarazione del tipo binTree occorre una chiamata al costruttore del tipo binTree.

Utilizzando la precedente definizione saremo in grado di generare un albero binario vuoto di tipo ‘a, oppure un albero più complesso di tipo indicato e costituito da uno a due nodi. Nell’esempio successivo vediamo prima la creazione di un albero binario vuoto e successivamente la definizione di albero binario di interi, non bilanciato e costituito da quattro livelli.

let tree1 = Null : 'a binTree;;
// val tree1 : 'a binTree

let tree2 = Null : int binTree;;
// val tree2 : int binTree = Null

(* oppure *)
let tree3 = Node(1, Node(2, Null, Node(4, Null, Null)), Node(3, Null, Null));;
// val tree3 : int binTree =
//  Node(1, Node(2, Null, Node(4, Null, Null)), Node(3, Null, Null))

// Struttura dell'albero generato:
//   1                                    1
//   /\                                 /   \
//  2  3    oppure (impropriamente)    2     3
//   \                                / \    /\
//    4                                  4

Una delle più importanti operazioni definibili sugli alberi binari è l’operazione di ricerca, incaricata di verificare la presenza di un certo valore fra tutti i nodi dell’albero. Possiamo immagine tale operazione come ad una funzione booleana predisposta a restituire il valore TRUE se il valore passato come argomento è presente all’interno di un nodo dell’albero, o FALSE in caso contrario.

let t2 = Node (2, Null, Node (4 , Null, Null));;
let t7 = Node (7, Null, Node (10, Null, Node (13 , Null, Null)));;
let t8 = Node (8, Node (11, Null, Null), Null);;
let t5 = Node (5, t7, t8);;
let t9 = Node (9, Null, Node (12, Null, Null));
let t6 = Node (6, t9, Null);;
let t3 = Node (3, t5, t6);;
let t1 = Node (1, t2, t3);;

let rec search (elm, tr) = match tr with
                           |Null           -> false
                           |Node (x, y, z) -> if x=elm then true else false || search (elm, y) || search (elm, z);;
// val search : elm:'a * tr:'a binTree -> bool when 'a : equality

search(2,t1);;
// val it : bool = true

search(3,t1);;
// val it : bool = true

search(4,t1);;
// val it : bool = true

search(5,t1);;
// val it : bool = true

search(100,t1);;
// val it : bool = false

Possiamo inoltre decidere di conteggiare tutti i nodi contenuti all’interno dell’albero:

let rec count tree = match tree with
                     |Null                  -> (0, 0)
                     |Node(elm, Null, Null) -> (1, 1)
                     |Node(elm, sx, dx)     -> (1 + fst (count sx) + fst (count dx), snd (count sx) + snd (count dx));;
// val count : tree:'a binTree -> int * int

let n1 = count t2;;
// val n1 : int * int = (2, 1)

let n2 = count t7;;
// val n1 : int * int = (3, 1)

let n3 = count t6;;
// val n1 : int * int = (3, 1)

let n4 = count t1;;
// val n1 : int * int = (13, 4)