UNIVERSITÀ DEGLI STUDI ROMA 3FACOLTÀ DI SCIENZE MATEMATICHE, FISICHE E NATURALI

CORSO DI LAUREA MAGISTRALE IN MATEMATICA

Tesi di Laurea Magistrale in Matematica

Analisi comparativa di strutture dati per la

rappresentazione di alberi

Candidato Relatore

Roberta Tirocchi Prof. Roberto Di Pietro

Correlatore

Prof. Alessandro Colantonio

Anno Accademico 2011/2012

2 CONCETTI BASE SUGLI ALBERI

1 IntroduzioneLa struttura ad albero, in inglese Tree, è una struttura dati non lineare che

segue un modello gerarchico. La sua caratteristica principale è che ciascun elementoha molti successori ed un unico predecessore. L’albero è molto usato nell’ambitoinformatico perchè consente di modellare aspetti della vita reale, come ad esempiol’organigramma di un’azienda, la tassonomia degli organismi animali e vegetali, legerarchie militari e la genealogia di una persona.

Nella letteratura esistono diverse strutture dati per rappresentare l’albero nelcalcolatore. Le principali distinzioni tra queste strutture si possono individuareattraverso la valutazione delle prestazioni, in termini di memoria occupata, e deltempo impiegato nell’esecuzione delle operazioni. Anche se la letteratura è moltoricca per quanto riguarda la descrizione di queste strutture dati, tuttavia è moltodifficile trovare delle analisi comparative che mostrino l’efficienza di ogni formarispetto alle altre.

La tesi si occuperà di fare un’analisi comparativa delle metodologie note inletteratura usate per rappresentare l’albero attraverso gli array e le matrici. Sarannoinoltre descritti due nuovi approcci, uno basato sull’uso di una matrice binaria, l’altrocomposto da un insieme di array di dimensione variabile. In entrambi i casi l’ideaprincipale è quella di memorizzare tutti gli antenati di ciascun elemento dell’albero.Nella tesi esamineremo pro e contro dei nuovi approcci rispetto alle metodologieclassiche. Inoltre analizzeremo il legame tra la teoria spettrale della forma matriciale,già nota in letteratura, e la teoria dei grafi ed esamineremo anche le caratteristichespettrali della nuova matrice binaria.

Nel corso del lavoro saranno comparate tra loro tutte le implementazioni dellerappresentazioni descritte, la complessità computazionale delle principali operazionisugli alberi, il tempo di esecuzione di ogni operazione ed il numero di celle usate perallocare nel calcolatore l’intero albero. Quest’analisi comparativa sarà effettuata siain maniera formale che mediante implementazione nel linguaggio di programmazioneJava di tutti gli algoritmi, eseguendo test numerici su alberi con un numero variabiledi nodi. Da quest’analisi saranno evidenziati gli aspetti positivi di ogni formadi rappresentazione e saranno messi in luce i miglioramenti che la nuova formaapporterà nella gestione degli alberi, come la riduzione del tempo di esecuzione dialcune operazioni.

2 Concetti base sugli alberiIn questo capitolo definiamo in modo rigoroso la struttura dati ad albero.

2

2 CONCETTI BASE SUGLI ALBERI

2.1 Definizioni

Nella teoria dei grafi, per grafo G intendiamo una coppia G = (V,E) dove V èun insieme non vuoto, discreto e finito, i cui elementi sono i vertici del grafo ed E èl’insieme degli spigoli del grafo ed è un sottoinsieme del prodotto cartesiano V×V[1].

Definizione 1. Un albero puó essere definito ricorsivamente come segue:

• G = ({v}, ∅) è un albero;

• se G1 e G2 sono alberi, allora G = (V,E) definito ponendo V = V (G1)∪V (G2),E = E(G1) ∪ E(G2) ∪ {(v1, v2)}, con v1 ∈ V (G1) e v2 ∈ V (G2) �

Da questa definizione ricorsiva ricaviamo che

Definizione 2. Un albero è un grafo T = (V,E) connesso ed aciclico.

Ciò vuol dire che presi due vertici distinti sono sempre connessi da uno ed unsolo cammino e che non devono esistere cicli. La connessione e l’aciclicità di unalbero T sono due proprietà legate alla cardinalità dell’insieme E(T ). Infatti se siaggiunge uno spigolo a T si perde l’aciclità, invece se si elimina uno spigolo si perdela connessione. Osserviamo inoltre preso un albero T abbiamo che se |V (T )|= n;allora |E(T )| =n−1. Questa relazione caratterizza in modo forte un albero; infattidato un grafo G = (V,E) con |E| = |V | − 1 e connesso allora è un albero. Tuttequeste proprietà sono riassunte nel seguente teorema di caratterizzazione degli alberi.

Teorema 1. Sia G = (V,E), un grafo non orientato.Le seguenti affermazioni sonoequivalenti :

1. G è un albero;

2. due vertici qualsiasi di G sono connessi da unico cammino semplice;

3. G è connesso, ma se qualunque spigolo di G venisse rimosso, allora G divente-rebbe non connesso;

4. G è connesso e |E| = |V | − 1;

5. G è aciclico e |E| = |V | − 1;

6. G è aciclico, ma se venisse aggiunto uno spigolo qualsiasi il grafo risultantenon sarebbe più aciclico.

3

3 METODI DI RAPPRESENTAZIONE CLASSICI

Dato un albero T = (V,E) è possibile selezionare un vertice r ∈ V (T ) qualsiasi ea partire da esso orientare tutti gli spigoli in modo naturale scegliendo i camminiche da r portano a tutti i vertici dell’albero. Otteniamo in questo modo un alberoorientato e radicato. Il vertice r è detto radice dell’albero, unico vertice privo dispigoli entranti ma può possedere un numero arbitrario di spigoli uscenti. Ogni nododell’albero, diverso dalla radice, possiede diversi spigoli uscenti ma un solo spigoloentrante. I vertici con solo spigoli entranti sono detti foglie. In un albero orientatoT = (V,E) se (u, v) ∈ E(T ), il vertice u si dice padre di v ed al tempo stesso v sidice figlio di u. Se due nodi hanno lo stesso padre, sono fratelli. Le foglie sono quindivertici privi di figli, invece la radice è l’unico vertice che non ha padre. Definiamoora un albero ordinato, un albero radicato i cui figli di ciascun nodo sono ordinati,cioè se un nodo ha k-figli abbiamo un primo, un secondo,. . . , un k-simo figlio. Seabbiamo un albero dove ogni nodo possiede solo due figli, definiamo questi con ilnome di figlio destro e sinistro. Un nodo non foglia è interno. Il grado di un nodox ∈ V (T ), in un albero T radicato, è il numero dei suoi figli. L’ordine è il gradomassimo di quasi tutti i nodi dell’albero. Preso un nodo x di un albero radicato Tcon radice r; un qualunque nodo y compreso nell’unico cammino da r a x è chiamatoantenato di x mentre x è detto discendente di y. La profondità di un nodo x, è lalunghezza del cammino dalla radice al nodo in questione. La profondità massima diun qualsiasi nodo dell’albero determina l’altezza dell’albero. Infine diciamo che unalbero è bilanciato se la profondità di ogni foglia coincide con l’altezza dell’alberooppure a questa stessa altezza meno uno. Per concludere questo discorso introduttivosulle proprietà della struttura dati ad albero enunciamo il seguente teorema con ilsuo corollario.

Teorema 2. Un albero completo di ordine d ed altezza h possiede dh+1−1d−1 nodi. �

Corollario 1. L’altezza di un albero completo di ordine d e avente n nodi è H =logd(nd− n+ 1)− 1. �

3 Metodi di rappresentazione classiciIn questo capitolo viene offerta una descrizione ad alto livello delle principali

strutture dati utilizzate per rappresentare alberi. Ci sono vari metodi per rappre-sentare la struttura ad albero. Nella letteratura, tale struttura viene implementatain due modi: con gli array e con le liste concatenate, ovvero oggetti (i nodi) chepuntano ad altri oggetti.

Per semplicità di esposizione ci soffermeremo a descrivere tutti i metodi noti chericorrono all’uso di uno ma anche più array e non quelli che ricorrono ai puntatori. Non

4

3 METODI DI RAPPRESENTAZIONE CLASSICI

descriveremo le liste concatenate perchè nella maggior parte dei casi la complessitàdell’esecuzione delle operazioni è la stessa, gli array sono più compatti e possiamoavere accesso diretto ai dati mediante indici. Inoltre alcune tipologie di alberi comead esempio gli heap ricorrono proprio per definizione agli array.

Gli alberi che andremo a rappresentare saranno alberi k-ari, ovvero alberi doveogni nodo possiede al più k figli.

Preso un albero T, memorizziamo il contenuto dell’etichetta di ciascun nodoall’interno di un array L ed i nodi vengono rinominati 0 ,1 ,..., n-1. In questomodo modelliamo i nodi dell’albero con dei numeri naturali così da rendere piùsemplice l’esecuzione delle operazioni sull’albero per qualsiasi tipo di dato contenutonell’etichette dei nodi.

3.1 Parent Representation (PR)

La Parent Representation(PR) è la forma di rappresentazione più semplice di unalbero. Il seguente metodo sfrutta la caratteristica della struttura dati ad albero cheevidenzia che ogni nodo ha un solo padre. La Parent Representation(PR) dell’alberoT è un array lineare A nel quale nella cella A[i] viene memorizzato il padre del nodoi, ovvero A[i] = j se il nodo j è il padre del nodo i e A[i] = −1 se il nodo i è la root.Con questa rappresentazione sarà semplice l’operazione di ricerca del padre di unnodo ma risulterà più costosa eseguire l’operazione di calcolo dei figli e molte altreoperazioni. Inoltre in questo caso non viene specificato l’ordine dei figli di un nodo.Nell’inserimento dei nodi è possibile imporre un ordine artificiale di inserimento deinodi nell’array. I nodi dell’albero possono essere letti, livello dopo livello, partendo dasinistra a destra a partire dalla radice. Assegniamo alla root la prima cella dell’arrayL (quella di posto 0), quindi avremo che A[0] = −1. È giusto notare che nel seguentemodo possiamo rappresentare qualsiasi tipo di albero non sono quello binario.

3.2 Adjacency Matrix Representation(AMR)

In teoria dei grafi, un albero è un tipo particolare di grafo, ovvero è un grafoconnesso ed aciclico. Un grafo può essere sempre rappresentato utilizzando unamatrice particolare detta matrice di adiacenza .

Definizione 3. La matrice di adiacenza è una matrice A di dimensione |V | × |V |definita in questo modo :

aij =

1 se (i , j) ∈ E(G)0 altrimenti .

5

3 METODI DI RAPPRESENTAZIONE CLASSICI

Se m è il numero di spigoli del grafo, avremmo 2m celle con il valore 1. Latrasposta di una matrice A = (aij) è definita come la matrice AT = (aTij), dove aTij =aji. Poichè in un grafo non orientato (u, v) e (v, u) rappresentano lo stesso arco, lamatrice di adiacenza di un grafo non orientato è identica alla trasposta : A = AT .In alcune applicazioni è conveniente memorizzare solo i dati che compaiono soprala diagonale principale (diagonale inclusa) della matrice di adiacenza, riducendoquindi la memoria necessaria per memorizzare il grafo quasi della metà. L’albero èun grafo quindi potremmo usare la matrice di adiacenza definita in questo modo perrappresentarlo :

aij =

1 se i è padre di j1 se i è figlio di j0 altrimenti

Quindi avremmo che ai,j = aj,i perchè se i è padre di j allora sicuramente j è figlio dii. Come nel caso del grafo non orientato A = AT quindi per convenienza possiamomemorizzare solo le celle al di sopra della diagonale e quindi definiamo la matrice diadiacenza dell’albero nel seguente modo :

aij =

1 se i è padre di j0 altrimenti

In questa rappresentazione abbiamo bisogno di memorizzare dove si trova la rootaltrimenti è difficile distinguerla dagli altri nodi. Possiamo rappresentare ogni alberok-ario con questo metodo.

3.3 List of Children Representation(LCR)

Una tecnica per la rappresentazione degli alberi molto usata in informatica prevedel’utilizzo di una famiglia di n liste L1, ...., Ln di vertici denominate liste di adiacenzadel grafo G. La rappresentazione mediante liste di adiacenza avviene nel seguentemodo: ∀ vi ∈ V (G) memorizziamo nella lista Li tutti i vertici ad esso adiacenti.Due vertici u e v si dicono adiacenti se esiste uno spigolo che li collega. Come nelparagrafo precedente sapendo che l’albero T= (V,E) è un grafo possiamo sfruttarequesto metodo per rappresentarlo. Sia T un albero, le liste sono array A di lunghezzan. Come per le altre forme questa può essere usata per ogni tipo di albero non soloquello binario, nel caso di alberi k-ari avremo k array. In ciascuna cella A[i] sonocontenuti i figli del nodo i. Alla root assegniamo sempre la prima posizione e perinserire gli altri nodi usiamo sempre un ordine convenzionale partendo dall’alto eproseguendo verso il basso. Nel caso dell’albero binario avremo solo due array L[i]e R[i] , nelle quali entrate memorizziamo rispettivamente il figlio sinistro e il figliodestro del nodo i. Per questo motivo, nel caso nell’albero binario, oltre al metodo

6

3 METODI DI RAPPRESENTAZIONE CLASSICI

d’inserimento con gli input standard (nodo e padre del nodo) implementeremo ancheun altro metodo per inserire i nodi , per input avremo un ulteriore informazioneovvero se il nodo in questione è un figlio sinistro o destro del padre. Chiamiamoquesta forma di rappresentazione List of Children Representation(LCR) .

3.4 Binary Tree Representation(BTR)

Binary Tree Representation(BTR) è una rappresentazione posizionale perchè laposizione del nodo nell’array corrisponde alla sua posizione nell’albero. Assegniamola cella 0 alla root, il nodo nella cella 1 è il figlio sinistro della radice e quello nellacella 2 è il figlio destro, e così via, proseguendo da sinistra a destra lungo ogni livellodell’albero. Aggiungere un nodo in una posizione nell’albero vuol dire collocareil nodo nella corrispettiva cella dell’array, se un nodo nell’albero non esiste nellasua cella viene memorizzato il valore −1. Sia T un albero binario, i figli ed ilpadre di un nodo possono essere trovati applicando semplici operazioni aritmeticheagli indici di locazione del nodo nell’ array. Sia index l’indice del nodo, il figliosinistro si troverà nella cella 2index + 1 mentre il figlio destro invece nella cella2index+2 ed infine il padre si trova nella posizione index−1

2 . Quando cancelliamoun nodo dall’albero avremo uno spreco di memoria perchè nell’array si creerannodei buchi ovvero rimarranno vuote quelle celle precedentemente occupate dai nodieliminati. Questa rappresentazione non è solo usata per gli alberi binari ma potràessere sfruttata per rappresentare qualsiasi tipo di albero k-ario.

3.5 Left Child - Right Sibling Representation (LCRSR)

Dato un albero k-ario esiste un algoritmo per trasformarlo in albero binario,questo procedimento non è reversibile senza l’ aggiunta di ulteriori informazioni. Senon eseguiamo l’ultimo passo dell’algoritmo abbiamo la rappresentazione di qualsiasialbero k-ario. Sia T un albero, prendiamo due array Left e Right di lunghezza parial numero n di nodi dell’albero. Memorizziamo all’interno della cella Left [i] il figliosinistro del nodo i, mentre nella cella Right[i] memorizziamo il fratello destro delnodo i. Specifichiamo che con il termine figlio sinistro del nodo i, intendiamo ilprimo nodo che abbiamo con padre il nodo i. L’ultimo passo dell’algoritmo consistenel prendere un nuovo albero T’ con gli stessi array Left e Right però cambierà ilsignificato del contenuto di questi array. Infatti Left[i] e Right[i] rappresentano il figliosinistro e destro del nodo i. Nel nostro caso non siamo interessati alla trasformazionema solo alla rappresentazione dell’albero quindi ci fermeremo al passo precedente,ove in Left[i] abbiamo il figlio più sinistro del nodo i mentre in Right[i] il fratellodestro di i. Se abbiamo un albero non completo segnaliamo la mancanza di un nodo

7

4 NUOVO METODO DI RAPPRESENTAZIONE BASATA SU MATRICIBINARIE

memorizzando -1 nell’entrata corrispettiva. Alla radice come in LCR assegniamosempre la prima cella dei due array quindi in Left[0] è contenuto il figlio più sinistrodella root e Right[0] = -1. Questa forma di rappresentazione si chiama Left Child -Right Sibling Representation (LCRSR).

4 Nuovo metodo di rappresentazione basata sumatrici binarie

Presentiamo ora la nuova forma di rappresentazione, nella sua forma estesa e nellasua forma contratta. Descriviamo queste due rappresentazioni della struttura datiad albero, la prima che ricorre all’uso di una matrice binaria, la seconda è sempreuna matrice ma costituita di array di dimensioni variabili.

4.1 Rappresentazione nella forma estesa

Dato un albero T con n nodi, i quali vengono memorizzati in un array L e lidenominiamo 0,1,. . . ,n-1 come per le classi note in letteratura. Rappresentiamol’albero attraverso una matrice binaria A di dimensione n× n. La matrice A vieneriempita seguendo il criterio che segue: A[i][j] = 1 se j è un antenato del nodo ied A[i][i] = 1, cioè ogni nodo è antenato di se stesso. Questa forma matriciale dirappresentazione dell’albero ricalca un legame specifico tra i nodi, essere antenati,per questo rende efficiente l’esecuzione di alcune operazioni. Come vedremo in avantiquesto metodo porta dei benefici in diverse operazioni, per il fatto che siamo in gradodi trovare in tempi costanti tutti gli antenati di ogni nodo dell’albero senza doveriterare il metodo di ricerca del padre. Lo svantaggio è chiaramente rappresentato dauna maggiore occupazione di memoria rispetto alla memorizzazione del solo antenatodiretto (cioè il padre), ma come vedremo in seguito è possibile ridurre moltissimotale overhead di memoria con tecniche di compressione dei dati. Per ogni nododell’albero la i-esima riga contiene gli antenati del nodo i. Tale metodo segue, comenel caso di PR, un criterio d’inserimento dei nodi nell’albero. La matrice binariache otteniamo da tale rappresentazione è una matrice sparsa. Questa matrice sidistingue dalla matrice di adiacenza descritta nel paragrafo precedente, perchè inquesta sono riportati tutti gli antenati del nodo ed il nodo stesso, mentre nellamatrice di adiacenza riportiamo solamente il padre diretto di ogni nodo.

4.2 Rappresentazione nella forma compressa

Per non avere una matrice sparsa, possiamo definire una versione compressadel metodo. C è un array n - dimensionale. Ogni cella è un array di dimensione

8

4 NUOVO METODO DI RAPPRESENTAZIONE BASATA SU MATRICIBINARIE

variabile, all’interno di ogni cella C[i] memorizziamo il nodo i ed il valore di tutti isuoi antenati. Utilizziamo, data la dimensione variabile di ogni cella dell’array C,un altro array N. Ogni cella N [i] contiene il numero di elementi dell’array C[i], talevalore è pari al numero di antenati del nodo i. In questo caso risulterà semplicissimoricercare gli antenati di un nodo dato.

Definiamo quanto detto in maniera rigorosa.C[i]= {j : A[i][j] = 1} ed con N [i]=|{j : A[i][j] = 1}|.Questa matrice vista per colonne ricorda le liste di adiacenza, ma a differenza di

questa vengono memorizzate in ogni riga gli antenati di ogni nodo ed il nodo stesso,mentre all’interno delle liste di adiacenza in ogni colonna troviamo i figli di ogninodo.

4.3 Legame tra la nuova matrice binaria e la matrice diadiacenza

Sia T un albero radicato, rappresentato nella memoria del calcolatore mediantela matrice di adiacenza A definita nel seguente modo:

aij =

1 se i è padre di j0 altrimenti

Conosciuta h, l’altezza dell’albero, dalla matrice di adiacenza A possiamo ottenere lamatrice binaria della nuova forma di rappresentazione mediante i seguenti passi:

• Calcoliamo la trasposta della matrice di adiacenza AT = A′.

• Sommiamo ad essa la matrice identità In quindi (A′ + In)

• Calcoliamo (A′ + In)h ed otteniamo la nuova forma di rappresentazione dell’al-bero mediante matrice binaria.

Osservazione 1. Il prodotto e la somma tra le matrici segue in questo caso le regoledell’algebra booleana. Sia A ∈ Mm,n(K) e B ∈ Mn,p(K) il loro prodotto righeper colonne è la matrice AB ∈ Mmp(K) il cui elemento di posto (i, k) è il prodottodella i-esima riga di A per k-esima colonna di B.

In formule si haAB = (A(i)B(k)) = ai1b1k + · · ·+ ainbnk.Il prodotto è il prodotto logico (AND) che restituisce 1 se tutti gli operandi valgono

1, mentre restituisce 0 in tutti gli altri casi.Invece la somma è la somma logica (OR) che restituisce 1 se almeno uno degli

elementi è 1 altrimenti vale 0.

9

5 IMPLEMENTAZIONE DELLE PRINCIPALI OPERAZIONI TIPICHE DEGLIALBERI

4.4 Pro e Contro dell’uso della nuova di rappresentazionedegli alberi

Nell’analizzare questa forma di rappresentazione rispetto alle altre note inletteratura evidenzieremo vantaggi ma anche svantaggi.

Rispetto agli altri metodi sarà semplice e veloce ricercare gli antenati di unnodo rispetto alle lunghe iterazioni ai cui ricorrono le altre metodologie. Questariduzione del tempo di calcolo degli antenati influenzerà in positivo i tempi diricerca del cammino minimo di un nodo, di calcolo della profondità di un nodo ecalcolo dell’altezza dell’albero. Questa sua particolarità ci permetterà di usare questarappresentazione ad esempio nella gestione dell’organigramma di un’azienda basatasui ruoli. Grazie al modo in cui vengono memorizzati i nodi rispetto alle altre formedi rappresentazione saremo in grado di risalire in breve tempo al ruolo root di ogniutente attraverso una semplice lettura.

Avremo però degli svantaggi per quanto riguarda la memoria occupata, dato cheessendo entrambe delle matrici occupano sicuramente più celle degli array ma anchedella stessa matrice di adiacenza (dato che come abbiamo detto memorizziamo tuttigli antenati ed il nodo stesso, non solo il padre). Si possono sfruttare tecniche dicompressione degli insieme come ad esempio Concise: Compressed ’n’ ComposableInteger Set [11].Concise è un algoritmo di compressione di matrici di bit. La com-pressione avviene senza compromettere le prestazioni delle operazioni bit per bit.Concise è in grado di rappresentare 32 interi in una cella di memoria solamente se gliinteri sono consecutivi (i, i+ 1, i+ 2, . . . , i+ 31). [11] . Nel caso degli alberi quindi segli antenati fossero tutti interi consecutivi sarebbe possibile applicare la compressionedei dati con Concise e quindi l’occupazione di memoria della matrice binaria nellaforma estesa diviene pari all’occupazione di memoria della matrice di adiacenza.

I vantaggi e gli svantaggi di questa nuova metodologia saranno esaminate neidettagli nei capitoli successi della tesi, attraverso l’analisi degli algoritmi, lo studiodella complessità computazionale e dell’occupazione di memoria

5 Implementazione delle principali operazioni ti-piche degli alberi

Per ogni struttura dati proposta nella tesi verranno analizzate in dettaglio leseguenti operazioni sugli alberi ed implementate in java:

• aumento dell’arietà, cioè aumento del numero massimo di figli per ogni nodo.

10

5 IMPLEMENTAZIONE DELLE PRINCIPALI OPERAZIONI TIPICHE DEGLIALBERI

• inserimento di un nodo in una data posizione, cioè inserimento all’interno dellastruttura dati del nodo in una determinata posizione.

• ricerca del padre di un dato nodo, cioè ricerca del padre diretto di un nodo.

• ricerca dei figli diretti di un dato nodo, cioè ricerca dei figli diretti di un nodo.

• ricerca dei fratelli di un dato nodo, cioè ricerca di tutti i nodi che hanno lostesso padre del nodo dato.

• rimozione di un nodo in una data posizione, cioè eliminazione di un nodo dallasua posizione all’interno della struttura dati.

• spostamento di un nodo da una posizione ad un’altra, cioè cambiamento dellaposizione del nodo all’interno della struttura dati.

• ricerca del cammino più breve tra due nodi dati e calcolo della sua lunghezza,cioè ricerca del cammino di lunghezza minima che connette due nodi dell’albero.

• calcolo antenati di un dato nodo.

• calcolo discendenti di un dato nodo.

• calcolo profondità di dato nodo.

• calcolo altezza dell’albero.

• calcolo radice dell’albero.

• verificare se un dato nodo è una foglia.

• verificare se dati due nodi, uno è figlio diretto dell’altro.

• verificare se dati due nodi, uno è padre dell’altro.

• verificare se dati due nodi, uno è discendente dell’altro.

• verificare se dato un nodo, è padre diretto di almeno un nodo contenuto in uninsieme generico di nodi.

• verificare se dato un nodo, è padre diretto di tutti i nodi contenuti in un insiemegenerico di nodi.

11

6 ANALISI MEMORIA E COMPLESSITÀ COMPUTAZIONALE

6 Analisi memoria e complessità computazionale

6.1 Vantaggi e Svantaggi in termini di complessità compu-tazionale della nuova forma di rappresentazione:

Attraverso la nozione O grande, con cui si definisce l’insieme delle funzioni lacui crescita asintotica non è maggiore, a meno di fattori moltiplicativi costanti, aquella di una determinata funzione f(n). Descriviamo ora una scala per magnitudinecrescente, con c indichiamo una costante arbitraria .

Notazione Nome0(1) costante0((log) logaritmicaO(n) lineareO(n2) quadraticaO(nc) polinomialeO(n!) fattoriale

Tabella 1: Ordini di funzioni comuni

Riassumiamo nelle seguenti la complessità computazionali calcolate in preceden-denza.

Memory Father Children SiblingsPR n O(1) O(n) O(n)BTR O(kn) O(1) O(1) O(1)AMR (n−1)n

2 O(n) O(n) O(n2)LCR kn O(kn) O(1) O(kn)LCRRSR kn O(nk) O(1) O(1)NEW (n+1)n

2 O(n) O(n2) O(n2)NEWC (n−1)n

2 O(1) O(n) O(n2)

Tabella 2: Tabella riassuntiva 1

12

7 RISULTATI SPERIMENTALI

Insert Remove Shortest Path MovePR O(1) O(n2) O( h) O(1)BTR O(1) O(n) O(n) O(n)AMR O(1) O (n2) O(n2) O(1)LCR O(k) O(n2) O(kn2) O(kn)LCRRSR O(k) O(n2) O(kn2) O(kn)NEW O(n) O (n2) O(h) O(n3)NEWC O(n) O(n2) O(h) O(n2)

Tabella 3: Tabella riassuntiva 2

Con il termine h, indichiamo l’altezza dell’albero. Da questa tabelle possiamonotare come la nuova forma di rappresentazione nella forma estesa (NEW) e com-pressa(NEWC) per quanto riguarda le operazione in tabella 2 non vanno peggio dialtri metodi. Infatti la forma compresse nel calcolo del padre di un nodo ha unacomplessità bassa pari a quella di PR. Invece nelle altre operazioni non risultanoessere efficienti ma neanche hanno tempi più alti delle altre classi. Mentre dallatabella 3 NEW e NEWC vediamo che in alcune operazioni come ShortestPath vadanomeglio di altre. Infatti tale operazione che ha complessità O(h) poichè al più abbiamoh antenati, ma nel caso peggiore h=n.

7 Risultati sperimentaliPer verificare i risultati teorici precedentemente esposti effettuiamo ora test

numerici per vedere l’andamento medio dei tempi di esecuzione di alcune operazioni.Eseguiamo i test su un albero binario con nodi random ed un albero binario bilanciato.

• Remove: Eseguiamo anche in questo caso i test su entrambi i tipi di alberi.Prendiamo in questo caso molti alberi con un numero sempre diverso di nodie calcoliamo il tempo medio di eliminazione da ogni albero dello stesso nodo.Nel caso del metodo remove, come abbiamo visto dobbiamo sempre calcolarci idiscendenti e poi eliminare il nodo in questione con a seguito ogni discendente.Siccome il calcolo dei discendenti nella nuova forma si riduce a semplice letturadi una colonna ciò si ripercuote nell’esecuzione della remove poichè usando lanuova forma di rappresentazione nella forma estesa si svolge con un tempomedio più basso rispetto alle altre forme.

13

7 RISULTATI SPERIMENTALI

Figura 1: Tempo medio remove albero nodi random

Figura 2: Tempo medio remove alberi nodi random grafico 3D

14

7 RISULTATI SPERIMENTALI

Figura 3: Tempo medio remove alberi bilanciati

Figura 4: Tempo medio remove alberi bilanciati 3D

• ParentOf : Anche in questo caso conduciamo il test su alberi con nodi randomed alberi bilanciati. Ogni test ricerchiamo su uno stesso albero il padre di ogninodo dell’albero a partire dalla radice fino alle foglie. Calcoliamo il tempo medioper svolgere tale ricerca. In entrambe le tipologie di alberi possiamo notarecome PR e BTR risultano essere le forme note più convenienti per condurretale ricerca invece come la forma matriciale della nuova rappresentazione nellaversione contratta risulta essere migliore di AMR.

15

7 RISULTATI SPERIMENTALI

Figura 5: Tempo medio parentOf albero nodi random

Figura 6: Tempo medio parentOf alberi nodi random grafico 3D

16

7 RISULTATI SPERIMENTALI

Figura 7: Tempo medio parentOf alberi bilanciati

Figura 8: Tempo medio parentOf alberi bilanciati 3D

• allParentOf : In questo caso per testare i tempi d’esecuzione dell’algoritmo dicalcolo degli antenati di un nodo usiamo sempre uno stesso albero e cerchiamogli antenati di ogni nodo a partire dalla radice fino alle foglie. Calcoliamoil tempo medio per condurre tale operazione. Possiamo vedere come nellosvolgimento di quest’operazione è conveniente usare un array sfruttando la formarappresentazione PR e BTR ma grazie alle due nuove forme di rappresentazionediviene utile anche l’uso della matrice. Infatti entrambi le forme risultano essereefficienti per ricercare gli antenati di un nodo.

17

7 RISULTATI SPERIMENTALI

Figura 9: Tempo medio AllParentOf albero nodi random

Figura 10: Tempo medio AllParentOf alberi nodi random grafico 3D

18

7 RISULTATI SPERIMENTALI

Figura 11: Tempo medio AllParentOfOf alberi bilanciati

Figura 12: Tempo medio AllParentOfOf alberi bilanciati 3D

• Height : In questo caso testo su più alberi e calcolo il tempo medio per il calcolodell’altezza di ogni albero. Il calcolo dell’altezza dell’albero viene influenzatodal calcolo degli antenati e dalla ricerca della foglia. Dalla combinazione diquesti due fattori negli alberi con nodi random la nuova forma nella versioneestesa risulta essere efficiente.

19

7 RISULTATI SPERIMENTALI

Figura 13: Tempo medio Height alberi nodi random

Figura 14: Tempo medio Height alberi nodi random grafico 3D

20

8 ANALISI DELLE RAPPRESENTAZIONI DEGLI ALBERI BASATI SUMATRICE

Figura 15: Tempo medio Height alberi bilanciati

Figura 16: Tempo medio Height alberi bilanciati 3D

8 Analisi delle rappresentazioni degli alberi basatisu matrice

Dopo aver descritto tutte le forme di rappresentazione degli alberi, tramite arraye matrici ed introdotte le nuove forme di rappresentazione matriciali degli alberi, inquesto capitolo studieremo ulteriore proprietà della matrice ed il legame che c’è traessa ed i grafi. Lo studio verrà effettuato sulla matrice di adiacenza, unica forma di

21

8 ANALISI DELLE RAPPRESENTAZIONI DEGLI ALBERI BASATI SUMATRICE

rappresentazione matriciale presente nella letteratura. Possiamo usare lo spettro diuna matrice(autovalori di una matrice) per avere informazioni su un determinatotipo di grafo. In questo modo creiamo una relazione tra gli autovalori di una matricee le proprietà di un grafo. Lo studio della relazione tra questi due oggetti si chiamaTeoria Spettrale dei grafi[10].

8.1 La matrice di adiacenza di un grafo

Come abbiamo già detto nella presentazione delle varie metodologie di presenta-zione dell’albero abbiamo che :

Definizione 4. La matrice di adiacenza è una matrice A di dimensione |V | × |V |definita in questo modo :

aij =

1 se (i , j)∈ E(G)0 altrimenti .

Definiamo lo spettro del grafo G, assumendo spec(G) = spec(A) ed estendiamo a Gla terminologia usata per la matrice A (autovalori,autovettori, polinomio caratteristicoecc...).Vediamo ora come dallo studio spettrale della matrice siamo in grado di coglierele caratteristiche di un grafo. Nel caso di alberi e grafi non orientati la matrice èsimmetrica e reale e tutti gli autovalori sono reali e mg(λi) = ma(λi) per ogniautovalore di A.

Proposizione 1. Sia G un grafo con n vertici, sia A la sua matrice di adiacenza esia pG(λ):= pA(λ) il polinomio caratteristico di G. Se il grafo G ha t ≥ 1 componenticonnesse G1. . . Gt allora pG = pG1 . . . pGt . Pertanto lo spettro di G è l’unione deglispettri delle sue componenti, e la molteplicità di ciascun autovalore di G è la sommadelle sue molteplicità come autovalore delle componenti Gi

8.2 La matrice di adiacenza e i cammini tra i vertici

Proposizione 2. Sia G=(V,E) un grafo e sia A la sua matrice di adiacenza. Alloraper ogni x,y ∈ V e per ogni s ≥ 1 : (As)xy = numero di cammini tra x e y di lunghezzas.

Osservazione 2. Sia G = (V,E) un grafo ed A la sua matrice di adiacenza. Dallaproposizione precedente segue che per ogni x ∈ V : (A2)xx = dG(x). e quindi la tracciadi A2 è tr(A2) := ∑

x∈V (A)2xx = ∑

x∈V dG(x) = 2|E|.

Proposizione 3. Sia M ∈ C n×n. La traccia ed il determinate di M sono rispettiva-mente la somma e il prodotto dei suoi autovalori : tr(M) := ∑

mij =∑λi∈Spec(M) λi

det(M) := ∏λi∈Spec(M) λi

22

9 CONCLUSIONI

Lemma 1. Siano M ∈ C n×n e Spec(M) = λ1, . . . , λn. Allora Spec(M s) = λs1,. . .,λsn con (s= 1,2,3,. . . )

Proposizione 4. Sia G = (V,E) un grafo con n vertici, sia A la matrice di adiacenzae sia Spec(G) = {λ1,. . . ,λn} i suoi autovalori. Allora :

1. ∑λi =

∑x∈V (A)xx= tr(A) = 0;

2. ∑λ2i = ∑

x∈V (A)2xx= tr(A2) = numero delle passeggiate chiuse di G lunghezza

2 = ∑x∈V dG(x) = 2|E|

3. ∑λ3i = ∑

x∈V (A)3xx= tr(A3) = numero delle passeggiate chiuse di G lunghezza

3 = 6 volte il numero dei triangoli del grafo

4. Conclusione : tr(As)= numero delle passeggiate chiuse di G lunghezza s =∑λsi = numero delle passeggiate chiuse di G di lunghezza s

8.3 La matrice binaria della nuova forma

La nuova matrice viene definita nel seguente modo :

Aij =

1 se j è antenato i oppure i=j0 altrimenti

Osservazione 3. Da tale definizione deriva che la traccia della nostra matrice èpari sempre ad n ove con n intendiamo il numero di nodi dell’albero.

Rispetto alla matrice di adiacenza per come è definita dipendendo dagli antenatidi un nodo, è conveniente principalmente per la rappresentazione di un albero. Perrappresentare un grafo qualsiasi con questa metodologia dovremmo prima trasformarloin albero. Calcolando gli autovalori di tale matrice (attraverso l’ analisi numericae anche con il calcolo delle radici del polinomio caratteristico) possiamo dire chein questo caso ∑

λi =∑x∈V (A)xx= tr(A) = n =|V |. Attraverso lo studio degli

autovalori della matrice binaria nella nuova forma si potrebbero trovare particolaricaratteristiche di un albero.

9 ConclusioniL’ albero è una struttura dati non lineare, che segue un modello gerarchico. La

sua struttura non sequenziale permette di stabilire dei rapporti di parentela tra inodi, per cui è possibile definire un nodo padre, un nodo figlio ed un nodo fratelloper questo viene impiegato in molti campi dell’informatica. Attraverso la struttura

23

9 CONCLUSIONI

dati ad albero siamo in grado di modellare aspetti della vita reale, come ad esempiol’organigramma di un’azienda, la tassonomia degli organismi animali e vegetali, legerarchie militari e la genealogia di una persona.

La letteratura è molto ricca per quanto riguarda la descrizione di queste strutturedati che rappresentano l’albero nella memoria del calcolatore, tuttavia è molto difficiletrovare delle analisi comparative che mostrino l’efficienza di ogni forma rispetto allealtre.

Nel corso della tesi sono state presentate le metodologie che utilizzano uno o piùarray. Tutte le forme di rappresentazione note in letteratura sono state presentatenel secondo capitolo della tesi, nel quale abbiamo visto che ogni metodologia ricalcaun legame di parentela specifico che si sviluppa tra i nodi dell’albero.

Nel terzo capitolo è stata presentata la nuova metodologia di rappresentazionenella forma estesa e compressa. Questo nuovo metodo rispecchia il legame tra duenodi di essere antenati. Sono entrambe due matrici, nella forma estesa è binariae quadrata mentre in quella compressa è una matrice dove le righe sono array didimensioni variabili. In ogni riga sono contenuti gli antenati del nodo associato atale riga ed il nodo stesso.

Questa forma usa le matrici e quindi nel sesto capitolo della tesi abbiamo evi-denziato l’importanza dell’uso della matrice nella rappresentazione di grafi grazieal legame che nasce tra le proprietà algebriche della matrice e la teoria dei grafi.Infatti attraverso lo studio dello spettro della matrice di adiacenza siamo in grado diconoscere diverse caratteristiche di un grafo, uno studio spettrale è stato condottoanche sulla matrice della nuova rappresentazione nella forma estesa.

Siamo passati alla comparazione delle varie forme di rappresentazione, abbiamodescritto ed implementato in Java gli algoritmi di esecuzione nelle principiali ope-razioni, abbiamo calcolato l’occupazione di memoria all’interno del calcolatore edinfine la complessità computazionale di ogni operazione per ogni forma.

Nel quinto capitolo sono stati condotti test numerici da quali è possibile dedurrecome la nuova forma di rappresentazione nella forma estesa e compressa ha portato deimiglioramenti sull’esecuzione di alcune operazioni e dove ogni struttura dati risultaessere valida nell’esecuzione di un operazione. La nuova forma risulta essere efficientenel calcolo degli antenati, nel calcolo dell’altezza dell’albero, nel calcolo del camminominimo tra due nodi , nella semplice ricerca del padre del nodo e nella rimozione diun nodo. Tali miglioramenti specialmente apportati in queste operazione rendonoutilizzabile l’albero mediante questa nuova forma di rappresentazione nella gestionedell’organigramma di un’azienda, di siti web o anche della rete di comunicazione tragli enti di una stessa azienda.

Come sviluppi futuri si potrebbero analizzare con maggior dettaglio i vantaggi

24

RIFERIMENTI BIBLIOGRAFICI

che un metodo di compressione dei dati apporta nell’uso di questa forma.

Riferimenti bibliografici[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduzione agli

algoritmi, seconda edizione, McGraw - Hill,1999.

[2] John R. Hubbard, Schaum’s Outline of Data Structures with Java, McGraw -Hill, 2000

[3] Robert Lafore, Data Structures e Algorithms in Java, Sams ,1998.

[4] Alfred V.Aho,John E. Hopcroft, and Jeffrey Ullman. Data Structures e Algori-thms .Addison-Wesley Longman Publishing Co. , Inc.,Boston , MA, USA, 1stedition, 1983.

[5] J.A. Bondy and U.S.R. Murty.Graph Theory. Springer Publishing Company,Incorporated, 1st edition, 2008

[6] P.S. Deshpande and O.G. Kakde. C e Data Structures (Eletrical and ComputerEngineering Series). Charles River Media, Inc, Rockland, MA,USA,2004.

[7] Alan Gibbons, Algorithmic graph theory, Cambridge University Press, 19948

[8] Richard J. Trudeau, Introduction to Graph Theory, Dover Publiactions Ins.,New York,1993.

[9] L.W. Beineke, R.J. Wilson, Topics in algebraic graph theory. Edited by L.W.Beineke and R.J. Wilson. Cambridge University Press, 2004.

[10] N. Biggs ,Algebraic graph theory. Second edition. Cambridge UniversityPress,1993.

[11] Alessandro Colantonio and Roberto Di Pietro, CONCISE: COmpressed ’N’Composable Integer SEt, Information Processing Letters, Elsevier, 2010, 110 ,16,644–650.

25