In questi giorni, per un esame di algoritmi distribuiti ho avuto la necessità di lavorare con un particolare albero nario. Genericamente un albero nario è un albero in cui ogni nodo presenta al massino n figli. Un albero binario è un caso particolare di albero nario dove n=2; in figura viene mostrato un albero 3ario.
Vediamo come realizzare un semplice albero nario che permetta di specificare il fattore di ramificazione e che permetta di inserire nodi all'interno dell' albero in modo tale che l'albero venga riempito livello per livello (prima ci creare un nuovo livello si porta a saturazione il livello corrente). Prima di passare alla definizione dell' albero voglio ricordare come un albero nario possa contenere un numero massimo di nodi per una certa altezza h pari a:
MaxNumNodi = N^(h+1)-1/N-1
In riferimento alla figura sopra esposta possiamo osservare che con N=3 ed h=2 otteniamo un numero massimo di nodi pari a 13. Passiamo adesso alla definizione del nostro albero. Per prima cosa definiamo due classi: una container che rappresenta l'albero ed esponde le funzionalità ed una che rappresenta i nodi all'interno di un albero.
1: public class NAryTree<T> where T:IComparable<T>
2: {
3: public NAryNode<T> root { get; set; }
4: public int branchFactor { get; set; }
5:
6: public NAryTree(T rootValue, int BranchFactor)
7: {
8: branchFactor = BranchFactor;
9: root = new NAryNode<T>(rootValue, branchFactor);
10: }
11: .
12: .
13: .
14: }
Come possiamo vedere la classe generica NAryTree tiene traccia della radice dell'albero e del fattore di ramificazione (numero di figli o arità). La constraint sul tipo generico in realtà nn viene utilizzata in quanto non si ha ordinamento parziale tra gli elementi ma serve come base per un eventuale albero nario di ricerca. Passiamo adesso alla classe NAryNode:
1: public class NAryNode<T> where T:IComparable<T>
2: {
3: public T value { get; set; }
4: public int childnum { get; set; }
5: public NAryNode<T>[] childs { get; set; }
6:
7: public NAryNode(T Value, int branchFactor)
8: {
9: value = Value;
10: childnum = branchFactor;
11: childs = new NAryNode<T>[branchFactor];
12: }
13: }
Anche la definizione di questa classe risulta abbastanza semplice.... abbiamo una property che memorizza il valore del nodo, un array di nodi figlio ed ancora una proprietà che mi informa sul numero di nodi figlio (proprietà ridondante avendo memorizzato questa info per la classe NaryTree ). Vediamo adesso come inserire per livelli i nodi all'interno dell' albero...
1: public void Insert(T value)
2: {
3: NAryNode<T> firstFreeNode = FindFirstFreeNode(root);
4: firstFreeNode.childs[CountImmediateChildren(firstFreeNode)] = new NAryNode<T>(value, branchFactor);
5: }
6:
7: private int CountImmediateChildren(NAryNode<T> node)
8: {
9: int count = 0;
10: for (int i = 0; i < node.childnum; i++)
11: {
12: if (node.childs[i] != default(NAryNode<T>))
13: count++;
14: }
15: return count;
16: }
17:
18: private NAryNode<T> FindFirstFreeNode(NAryNode<T> root)
19: {
20: //BREADTH FIRST WAY!!!!
21: Queue<NAryNode<T>> row = new Queue<NAryNode<T>>();
22: row.Enqueue(root);
23: while (row.Count > 0)
24: {
25: NAryNode<T> currentNode = row.Dequeue();
26: if (CountImmediateChildren(currentNode) < root.childs.Length)
27: {
28: return currentNode;
29: }
30: for (int index = 0; index < CountImmediateChildren(currentNode); index++)
31: {
32: row.Enqueue(currentNode.childs[index]);
33: }
34: }
35: return default(NAryNode<T>);
36: }
Per eseguire l'inserimento ho usato una tecnica molto brute force che nn fa altro che reperire il primo nodo che ha ancora spazio libero tra i propri figli ed eseguire su di esso l' inserimento.... una tecnica più efficiente consiste nel tenere all'interno della classe NaryTree un riferimento all' ultimo nodo inserito in modo tale che ad ogni inserimento non venga fatta una scansione dell' intero albero per trovare il nodo su cui fare l'inserimento. Unica cosa degna di nota è l'ottimizzazione in termini di allocazione dello stack di sistema eseguita all'interno della funzione FindFirstFreeNode grazie all'uso di una coda dove per ogni livello vengono accodati i vari nodi. A questo punto allego la solution dove potete trovare l'intero codice comprensivo di test ed una piccola demo winform che utilizza la libreria GLEE. Se ritenete opportuno avere un'implementazione seria di albero nario lasciate un feedback che magari verrà presa in considerazione come feature da aggiungere all'interno di DSA