Il TDA Tree - UNISAcaprera.dia.unisa.it/LASD/SLIDE/09Alberi.pdf · – Java, C++, PHP, Perl ......

Il TDA Tree

Prof. Carlo Blundo Laboratorio di Algoritmi e Strutture Dati 2

Alberi In informatica, un albero è un modello astratto di una struttura dati gerarchica– Struttura dati non lineare– Si pensi al file system di un sistema

operativoLe relazioni in un albero sono gerarchiche nel senso che alcuni oggetti sono “sopra” degli altri altri sono “sotto”


Esempio/

home rootetc

security squidbc blundo

TSW LASD FdI


Alberi

La terminologia utilizzata per far riferimento a relazioni tra gli elementi di un albero derivano dall’albero genealogico– La relazione più semplice è quella di

genitore-figlio– Altri termini utilizzati sono: antenato,

discendente, fratello, …


Definizione di albero

Un albero T è un insieme di nodi con una relazione genitore-figlio con le seguenti proprietà– T può essere vuoto– T ha un nodo speciale r detto radice di T– Ogni nodo v di T diverso da r ha un nodo

genitore u


Applicazionialberi genealogicigerarchie di ereditarietà– Java, C++, PHP, Perl

classificazioni di specie animaliorganizzazione del territorio– continente, nazione, regione, provincia ecc

(alcuni) organigrammifile systemdomini Internet


Terminologia – 1

Radice– Nodo senza genitore (A)

Nodo interno– Nodo con almeno un figlio (A, B, C, F)

Nodo esterno (detto anche foglia)– Nodo senza figli (E, I, J, K, G, H, D)

Antenati di un nodo– Genitore o antenato del genitore (di J: F, B, A),

A

B DC

G HE F

I J K


Terminologia – 2

Discendenti di un nodo– Figlio o discendente del figlio (di B: E, F, I, J, K)

Sottoalbero– Albero che consiste di un nodo e dei suoi

discendenti

A

B DC

G HE F

I J K


Terminologia – 3

Profondità di un nodo – Numero di antenati del nodo, la radice ha

profondità 0 (F: 2)Altezza di un albero– Massima profondità di un qualsiasi nodo (3)

A

B DC

G HE F

I J K


Il TDA TreeL’albero memorizza gli elementi in posizioniCome per le posizioni di List, esse sono definite relativamente alle posizioni vicineLe posizioni in un albero sono i suoi nodiLe posizioni in un albero soddisfano la relazione genitore-figlio


Il TDA PositionUsiamo lo stesso TDA (ed interfaccia) impiegata per List

public interface Position {// Restituisce l’elemento memorizzato // nella posizione

public Object element();}

La sua implementazione cambierà a seconda dell’albero che andremo a rappresentare


Metodi supportati dal TDA Tree – 1

Metodi di Accesso:– Position root()

• Restituisce la radice dell’albero, errore se l’albero è vuoto

– Position parent(v)• Restituisce il genitore del nodo v; errore se p è

la radice dell’albero– PositionIterator children(v)

• Restituisce un iteratore ai figli del nodo v


Metodi supportati dal TDA Tree – 2Metodi di interrogazione:– boolean isInternal(v)

• Verifica se v è un nodo interno– boolean isExternal(v)

• Verifica se v è un nodo esterno– boolean isRoot(v)

• Verifica se v è la radice– boolean isEmpty()

• Verifica se l’albero è vuoto


Ulteriori metodi di TreePossiamo aggiungere i seguenti metodi anche se non sono necessariamente legati al TDA– void swapElements(p, q)– Object replaceElement(p, o)– ObjectIterator elements()– PostionIterator positions()– int size()


Gerarchia di interfacceInvece che scrivere tutti i metodi in un’unica interfaccia possiamo dividerli in varie interfacce che possiamo in seguito riciclare per implementazioni di altri TDA– Usiamo una gerarchia simile a quella

mostrata alla fine della lezione su Sequence

Aggiungete le eccezioni ovunque lo riteniate necessario


InspectableContainersize – isEmpty – elements

InspectablePositionalContainerpositions

InspectableTreeroot – parent – children

isIntenal – isExternal – isRoot

Tree

PositionalContainerreplaceElement swapElement

Gerarchia


Interfacce Java – Codice sul sitopublic interface InspectableContainer {}public interface InspectablePositionalContainer extends

InspectableContainer {}public interface InspectableTree extends

InspectablePositionalContainer {}public interface PositionalContainer extends

InspectablePositionalContainer {}public interface Tree extends

InspectableTree, PositionalContainer {}


Struttura dati per rappresentare posizioni in Tree

Possiamo rappresentare il TDA Position tramite un nodo che contiene– un riferimento ad un elemento – un riferimento al nodo genitore– un riferimento ad un contenitore che

memorizza riferimenti ai nodi figliGraficamente ….


B

DA

C E

F

∅

B

∅ ∅

A D F

∅

C

∅

ERiferimento al genitore

Riferimento all’elemento

Riferimento al contenitore

Riferimento al nodo


Classe TreeNode – 1public class TreeNode implements Position {

private Object element;private TreeNode parent;private NodeList children;

public TreeNode() {element = null; parent = null; children = null; }

public TreeNode(Object e, TreeNode p, NodeList c) {element = e; parent = p; children = c; }


Classe TreeNode – 2public Object element() { return element; }

public void setElement(Object e) { element = e; }

public TreeNode getParent() { return parent; }

public void setParent(TreeNode p) { parent = p; }

public NodeList getChildren() { return children; }//potremmo far restituire un iteratore ai figli

public void setChildren(NodeList l) { children = l; }

}


EserciziImplementare l’interfaccia Tree(scrivere il codice della classe LinkedTree ) usando l’implementazione TreeNode per Position– Indicare le eccezioni da lanciare

Modificare il metodo getChildren di TreeNode in modo da fargli restituire un iteratore ai figli del nodo


Bozza di LinkedTree

public class LinkedTree implements Tree {

protected NodeTree root;

protected int numElem;

//numero di elementi nell’albero

. . . }


EserciziTestare l’implementazione di LinkedTreescrivendo un programma TestLinkedTreeche utilizzi tutti i metodi dell’interfaccia Tree

Aggiungere a LinkedTree il metodo depth(v) che restituisce la profondità del nodo v

Aggiungere a LinkedTree il metodo height() che restituisce l’altezza dell’albero


Esercizio

L’arità (arity) di un albero è il numero massimo di figli di un nodo dell’alberoAggiungere a LinkedTree il metodo arity() che restituisce l’arità dell’albero (nell’esempio, arity() restituisce 3)

A

B DC

G HE F

I J K


LeftChild – RightSibling

Altra struttura dati per rappresentare Tree

Struttura del nodo simile a quella che utilizzeremo per rappresentare un albero binario (ogni nodo ha al più due figli)


LeftChild – RightSiblingElemento

Riferimento al primo figlioRiferimento al prossimo fratello

B C D

E F G

A

B C D

E F G

A

Nella rappresentazione Java aggiungiamo anche un riferimento al nodo genitore


Classe LCRSNode – 1public class LCRSNode implements Position{

private Object element;private LCRSNode leftC, rightS, parent;

public LCRSNode() {}public LCRSNode(Object e, LCRSNode p, LCRSNode l,

LCRSNode r) {setElement(e); setParent(p); setLeft(l); setRight(r); }

public Object element() { return element; }public void setElement(Object o) { element = o; }


Classe LCRSNode – 2public LCRSNode getLeft() { return leftC; }

public void setLeft(LCRSNode l) { leftC = l; }

public LCRSNode getRight() { return rightS; }

public void setRight(LCRSNode r) { rightS = r; }

public LCRSNode getParent() { return parent; }

public void setParent(LCRSNode p) { parent = p; }}


Esercizi

Implementare l’interfaccia Tree (scrivere il codice della classe LCRSTree ) usando l’implementazione LCRSNode per PositionTestare l’implementazione di LCRSTreescrivendo un programma TestLCRSTree che utilizzi tutti i metodi dell’interfaccia TreeValutare le differenze della complessitàcomputazionale dei metodi implementati in LinkedTree e LCRSTree

Il TDA Tree - UNISAcaprera.dia.unisa.it/LASD/SLIDE/09Alberi.pdf · – Java, C++, PHP, Perl ......

Documents

Transcript of Il TDA Tree - UNISAcaprera.dia.unisa.it/LASD/SLIDE/09Alberi.pdf · – Java, C++, PHP, Perl ......