[JAVA] Implementazione Alberi generici

[Mulder90]

Ciao a tutti!!! Sto scrivendo il progettino di "Algoritmi e strutture dati" e naturalmente i dubbi non mancano :D
Il progetto consiste nell'implementazione di un albero generico. Deve essere rappresentato tramite due strutture sequenziali: una memorizza i nodi dell'albero e un'altra invece memorizza i padri dei nodi.
Se il nodo occupa la posizione i-esima nella prima struttura, il padre deve occupare la posizione i-esima della seconda struttura.
Ad esempio: NODI = {a,c,h,b,x,g}, PADRI = {null, a,a,c,h,a}. a è la radice e non ha padre quindi nella seconda struttura il valore è null, c è figlio di a, ecc....
Devo assumere che l'inserimento avvenga in fondo alla struttura, i nodi siano tutti diversi e con informazione dello stesso tipo.
Dopo aver implementato la struttura dovrò implementare vari metodi per svariate operazioni.
Intanto posto il codice che ho scritto fin'ora e poi vi dico i miei dubbi ;)
P.S: sia chiaro che non voglio la soluzione!!!

Nodo.java:

import java.util.LinkedList;

public class NodoVP<T> {

private T info;
private NodoVP<T> padre;
private LinkedList<NodoVP<T>> figli;

public NodoVP(T data) {
info = data;
padre = null;
figli = new LinkedList<NodoVP<T>>();
}

public T getInfo() {
return info;
}

public void setInfo(T data) {
info = data;
}

public NodoVP<T> getPadre() {
return padre;
}

public void setPadre(NodoVP<T> u) {
padre = u;
}

public LinkedList<NodoVP<T>> getFigli() {
return figli;
}

public void setFiglio(NodoVP<T> x) {
figli.addLast(x);
}

}

Albero.java:

import java.util.ArrayList;
import java.util.Iterator;

public class AlberoVP<T> {

private ArrayList<NodoVP<T>> nodiAlbero;
private ArrayList<NodoVP<T>> padriNodi;
private int numNodi;
private NodoVP<T> radice;

public AlberoVP() {
radice = null;
numNodi = 0;
nodiAlbero = new ArrayList<NodoVP<T>>();
padriNodi = new ArrayList<NodoVP<T>>();
}

public NodoVP<T> setRadice(T data) throws Exception {
if (radice != null)
throw new Exception("Radice già presente");
else {
radice = new NodoVP<T>(data);
numNodi++;
getNodiAlbero().add(radice);
getPadriNodi().add(null);
return radice;
}
}

public NodoVP<T> inserisciNodo(T data, T valorePadre) {
int position = trovaNodo(valorePadre);
NodoVP<T> nodo = new NodoVP<T>(data);
nodo.setPadre(getNodiAlbero().get(position));
getNodiAlbero().get(position).setFiglio(nodo);
numNodi++;
getNodiAlbero().add(nodo);
getPadriNodi().add(nodo.getPadre());
return nodo;

}

private int trovaNodo(T valorePadre) {
int position = 0;
int i = 0;
while (i < getNodiAlbero().size()) {
if (getNodiAlbero().get(i).getInfo() == valorePadre) {
position = i;
return position;
} else
i++;
}
if (i == getNodiAlbero().size()) {
System.out.println("Il padre non esiste");
return -1;
}
return position;
}

public ArrayList<NodoVP<T>> getNodiAlbero() {
return nodiAlbero;
}

public ArrayList<NodoVP<T>> getPadriNodi() {
return padriNodi;
}

public NodoVP<T> getRadice() {
return radice;
}

public int getNumNodi() {
return numNodi;
}

public void stampaNodiAlbero() {
System.out.print("Nodi dell'albero: ");
Iterator<NodoVP<T>> it = nodiAlbero.iterator();
while (it.hasNext())
System.out.print(it.next().getInfo() + " ");
}

public void stampaPadriNodi() {
System.out.print("Padri dei nodi: ");
for (NodoVP<T> i : padriNodi) {
if (i != null)
System.out.print(i.getInfo() + " ");
else
System.out.print("null ");
}
}

public T getDataOfNodo(NodoVP<T> n) {
return n.getInfo();
}

public void setDataOfNodo(NodoVP<T> n, T data) {
n.setInfo(data);
}

}

Nel main costruisco un albero in questa maniera:

AlberoVP<Integer> albero = new AlberoVP<Integer>();

Setto la radice e inserisco i nodi in questa maniera:


albero.setRadice(19);
albero.inserisciNodo(12, 19);
albero.inserisciNodo(16, 19);
albero.inserisciNodo(23, 12);
albero.inserisciNodo(52, 16);
albero.inserisciNodo(2,16);
albero.inserisciNodo(31, 2);


Passiamo alle domande che mi "turbano":
1)La struttura di base è solida?
Questo dubbio mi viene poichè per inserire un nodo come figlio di un altro viene richiesto di sapere l'informazione e il nodo padre.
Invece l'unico modo in cui sono riuscito a fare l'inserimento di un figlio è stato quello di passare al metodo inserisciNodo l'informazione e il valore del nodo padre.
In questo modo posso inserire un nodo in questa maniera:
albero.inserisciNodo(12, 19);
dove 12 è l'informazione e 19 il valore del padre.
2) Per fare l'inserimento devo fare ogni volta una ricerca della posizione del padre nella struttura sequenziale(nel mio caso ArrayList). Tutto questo ha un costo particolarmente alto? Come potrei migliorare?

Per ora basta visto che ho fatto un post di 1 km!!! :D
Ringrazio anticipatamente quelli che avranno la voglia di leggere tutto!!!

P.S: il codice è scritto di fretta...se ci sono "orrori" mi scuso in anticipo...naturalmente non è la versione finale!

[rasty1991]

Ciao, scusa ma non so rispondere alle tue domande ma forse te puoi chiarire qualche mio dubbio...cercavo infatti qualcuno che mi spiegasse cosa vuol dire, facendo ad esempio riferimento al tuo codice, public class NodoVP<T>, questa <T> che sta a significare ? come la usi?
Cosa vuol dire: private LinkedList<NodoVP<T>> figli; ??
Mi potresti poi spiegare cosa vuol dire esattamente e cosa fa :
public void setFiglio(NodoVP<T> x) {
figli.addLast(x); //cos'è addLast?
}


Scusa se rispondo con un altra domanda ma....:D

[PGI-Bis]

x Mulder90

Circa la solidità bisognerebbe prima definire il concetto puntualmente. In generale potremmo dire che è "solido" tutto ciò che non è possibile "mandare a ramengo".

Nel codice ci sono un paio di rischi che nascono dalla pubblicazione delle liste di nodi, padri e figli. A naso direi che quei rischi non si concretizzano (ad esempio posso dire albero.getPadriNodi().clear() ma, per com'è fatto il codice, non mi sembra che questa alterazione causi una corruzione del funzionamento dell'albero perchè la lista dei padri è praticamente irrilevante).

Sospetto anche che siano un po' di duplicazioni nel senso che, dal codice, mi risulta possibile che la lista di padri contenga più volte uno stesso nodo oltre ad un "null" che non dovrebbe essere necessario.

Per quanto riguarda il dubbio sull'inserimento, il requisito "inserisci un valore x dato il nodo padre p" funziona esattamente come il tuo "inserisciNodo" solo che al posto di valorePadre è dato direttamente il nodo.

public NodoVP<T> inserisciNodo(T data, NodoVP<T> padre) {
NodoVP<T> figlio = new NodoVP<T>(data);
padre.setFiglio(figlio);
figlio.setPadre(padre);
nodiAlbero.add(figlio);
padriNodi.add(padre);//duplicazione se padriNodi.contains(padre)
return figlio;
}

L'inserimento rispetto al valore del padre è però più sicuro perchè la versione su riportata opera sotto la precondizione implicita che "padre" sia un nodo generato da AlberoVP, cosa che la struttura del programma non garantisce.

Dal punto di vista dell'algoritmo è chiaro che l'inserimento che hai già sia un O(n). Per come sono fatte le strutture dati coinvolte, l'inserimento dato il nodo padre sarebbe un O(1). Con un gigantesco MA.

L'O(N) che hai, salvo il problema della duplicazione, verifica che l'inserimento sia valido - cioè operi rispetto ad un nodo esistente. L'O(1) proposto non fa questa verifica: dunque si tratta di funzioni con effetti diversi. Capita che per ottenere le stesse garanzie dell'inserisci valore rispetto al valore, l'inserimento del valore rispetto al nodo debba diventare anch'esso un O(N) - nel caso peggiore perché dato un padre puoi verificare l'appartenenza all'albero risalendo da quel nodo alla radice e controllando che essa sia la radice dell'albero.

Ricapitolando, io credo che le questioni che devi esaminare siano due: se sia possibile "violentare" l'albero con i metodi che hai e con i tipi di dato che quei metodi restituiscono (soprattutto con quelle liste: cosa succede se ci ficchi dei nodi che non appartengono all'albero o se li rimuovi o se aggiungi dei figli estranei all'albero alla lista dei figli di un nodo eccetera);
se sia possibile ottenere un inserimento O(1) rispetto ad un nodo padre dato con le stesse garanzie dell'inserimento O(N) rispetto al valore del padre.

x rasty1991

Di solito è meglio aprire un diverso thread per domande proprie ma capisco che essendo incerto il "nome" del dubbio sarebbe stato difficile formulare una domanda autonoma.

Quella T denota una variabile parametro di tipo... tipo.

E' parametro nello stesso senso in cui lo è una variabile che faccia parte della lista di argomenti di un metodo:

public void metodo(String parametro)

Denota cioè qualcosa rispetto a cui opererà qualcos'altro (il metodo nel caso d'esempio) e il cui valore sarà specificato nel momento in cui il qualcos'altro sarà usato (nel caso del metodo all'atto dell'invocazione di metodo).

Per convenzione le variabili di tipo "tipo di parametro" sono denotate da lettere singole maiuscole. Fuori dalla convenzione, la faccenda diventerebbe più chiara se ad esempio dicessimo:

public class NodoVP<TipoDelValoreDelCampoInfo> {
private TipoDelValoreDelCampoInfo info;

Dal punto di vista del codice avere quella <T> significa che nel momento in cui userai la classe (ma vale anche per interfacce metodi o costruttori) dovrai specificare il valore di T.

NodoVP<String> n = new NodoVP<String>();

Quando specifichi la T è come se tutto ciò che nella classe NodoVP era identificato dalla lettera T diventasse String. Vale a dire che "n" si troverà ad avere un campo info di tipo String, il suo metodo getInfo restituirà uno String, il suo metodo getPadre restituirà un NodoVP<String> e così via.

In base a questa sostituzione nominale, il campo "figli" di NodoVP<T>, specificato all'atto dell'invocazione in NodoVP<String>, diventa come se fosse dichiarato:

LinkedList<NodoVP<String>> figli;

Questa orrenda sequela di <> deriva dal fatto che LinkedList, come NodoVP è una classe generica (è definito parametrizzato o generico un tipo - classe, interfaccia, enumerativo o un metodo o un costruttore che reca una dichiarazione parametrica, cioè un <Qualcosa> in prossimità del nome).

E' generica perchè è definita:

public class LinkedList<Qualcosa> {

Al posto di Qualcosa, come detto, si può mettere il nome di un tipo (classe, interfaccia, enumerativo). Ad esempio:

LinkedList<String> lista
LinkedList<Integer> lista
LinkedList<JFrame> lista

Si può mettere il nome di un tipo che è a sua volta generico? Impropriamente, sì. Lo fai dicendo ad esempio:

LinkedList<NodoVP<String>> lista

E ottieni una LinkedList che contiene dei NodoVP che hanno per "info" delle stringhe.

In senso poprio non metti il tipo generico ma il risultato dell'espressione che trasforma un tipo generico in tipo parametrico, cioè la specificazione di parametro. Ci metti cioè String, Integer, Pippo, Giovanni, quel che vuoi. Tra quel che vuoi rientrano anche altre variabili di tipo tipo.

NodoVP dichiara di essere generico in T. Al suo interno ha un campo LinkedList che è un altro tipo generico, diciamo in A. NodoVP dice che il tipo dei valori di LinkedList è NodoVP. Siccome NodoVP è generico deve anche dirgli qual'è il tipo dei NodoVP contenuti nella LinkedList. E dice "T": cioè lo stesso tipo che è stato usato per specificarmi quando sarò usato.

E poi arriverebbe la parte complicata perchè la dichiarazione di parametro, cioè quello che puoi scrivere al posto della T quando "crei" un tipo parametrico partendo da un generico, include alcuni esoterismi geometrici che ti risparmio.

Questo segone mentale permette di usare il compilatore per eseguire una certa classe di operazioni il cui risultato è verificato dal compilatore stesso. L'operazione tipica è la verifica della compatibilità logica degli assegnamenti: se scrivo LinkedList<String> il compilatore verifica che il mio codice nella lista metta e tolga solo stringhe. Se scrivo NodoVP<Number> verificherà che il mio NodoVP operi esclusivamente rispetto a valori di tipo Number (quindi Integer, Double, Float, BigDecimal eccetera).

Impedisce cioè, comunemente, la possibilità che si verifichino certe eccezioni di tipo ClassCastException (la cui incidenza era praticamente nulla ma qualcuno la pensò veramente male).

Non è però il solo tipo di uso possibile, ce ne sono altri molto più astrusi che sono forse più interessanti ma di cui non importa nulla a nessuno salvo forse un paio di predicanti con annessa torre d'avorio.

[Mulder90]

Intanto ti ringrazio della risposta, come sempre sei gentilissimo:)
In questi giorni ho parlato con il professore e lui mi ha consigliato di passare il nodo padre e non il valore.

Alla fine ho pensato di fare proprio come hai scritto te e cioè:

public NodoVP<T> inserisciNodo(T data, NodoVP<T> padre) {
NodoVP<T> nodo = new NodoVP<T>(data);
nodo.setPadre(padre);
padre.setFiglio(nodo);
getNodiAlbero().add(nodo);
getPadriNodi().add(padre);
numNodi++;
return nodo;
}


Adesso nel main opero in questa maniera:


AlberoVP<Integer> albero = new AlberoVP<Integer>();
NodoVP<Integer> ottantadue = albero.setRadice(82);
NodoVP<Integer> quarantaquattro = albero.inserisciNodo(44, ottantadue);
NodoVP<Integer> trentatre = albero.inserisciNodo(33, ottantadue);
NodoVP<Integer> ventidue = albero.inserisciNodo(22, ottantadue);



Forse mi ero dimenticato di scriverlo ma devo supporre che tutti i nodi siano diversi tra loro.... cioè non devo gestire i casi dei duplicati.

Per quanto riguarda la validità dell'inserimento se io al metodo inserisciNodo passo come argomento un padre che non esiste mi dovrebbe segnalare immediatamente l'errore.

Esempio:

NodoVP<Integer> uno= albero.inserisciNodo(1, diecimila);


Siccome il nodo "diecimila" non esiste eclipse mi segnala subito l'errore.
Così a occhio non credo si possa fare un metodo che inserisce con un tempo costante e che verifichi anche la validità dell'inserimento...
Mi rendo conto che il tutto è un po bruttino però essendo una cosa didattica credo che possa andare, no?

[PGI-Bis]

E' possibile prendere i due piccioni con una fava giocando con le classi (in particolare coi tipi annidati puoi imporre che i nodi gestiti dai metodi dell'albero provengano esclusivamente dall'albero) ma non è richiesto dall'esercizio io non me ne preoccuperei.

L'unica cosa strana sono i padri: l'albero ha questa lista di padri ma a parte infilarci dentro nodi e stamparla non mi sembra abbia altri usi. Magari ci sarà un esercizio successivo in cui questa lista avrà un qualche scopo ma così non è di grande utilità.

[Mulder90]

E' possibile prendere i due piccioni con una fava giocando con le classi (in particolare coi tipi annidati puoi imporre che i nodi gestiti dai metodi dell'albero provengano esclusivamente dall'albero) ma non è richiesto dall'esercizio io non me ne preoccuperei.

L'unica cosa strana sono i padri: l'albero ha questa lista di padri ma a parte infilarci dentro nodi e stamparla non mi sembra abbia altri usi. Magari ci sarà un esercizio successivo in cui questa lista avrà un qualche scopo ma così non è di grande utilità.


Essendo il progettino di fine corso credo che sia stata messa per "aumentare" leggermente la difficoltà... :D

Ultimissimo dubbio. (forse più che dubbio è una p***a mentale... :D )
Ho un metodo per cambiare l'informazione di un nodo.
Cambio l'info di un nodo in questa maniera:

albero.setInfoNodo(quarantaquattro, 55);
o in quest'altra:
quarantaquattro.setInfo(55);

entrambi i metodi restituiscono void.
In questo caso ho un metodo che si chiama quarantaquattro ma contine 55....molto brutto.
Se per qualche operazione devo usare il nodo quarantaquattro mi devo ricordare che in verità contiene 55.


Ho pensato ad una soluzione di questo genere:
Faccio il metodo così:

public NodoVP<T> setInfoNodo(NodoVP<T> nodo, T data) {
nodo.setInfo(data);
return nodo;
}
e se voglio cambiare valore ad un nodo faccio così:
NodoVP<Integer> cinquantacinque = albero.setInfoNodo(quarantaquattro, 55);

L'unica cosa è che rimane il nodo con nome quarantaquattro "libero"...

[PGI-Bis]

In realtà il problema è di più ampio respiro.

In generale il funzionamento di una struttura dati è diviso in due parti, chiamiamole "interna" ed "esterna".

Esternamente non operi sui nodi ma sui valori cioè l'utente della libreria non lavora coi nodi ma lavora con gli "info".

Internamente la struttura dati usa i nodi cioè i nodi sono quella parte della struttura dati "albero" che le permette di dire che 55 è figlio di 50 che è figlio di 10.

A conti fatti il nodo è il medium tramite il quale l'albero struttura i dati che gli fornisci.

Il problema del nodo quarantaquattro che contiene l'info 55 è un problema di confusione (nel senso del mescolare) tra il modo in cui l'albero gestisce la sua organizzazione interna e i dati che deve contenere.

Per farla breve, l'albero non dovrebbe esporre i nodi ma solo i valori dei nodi. Da utente dell'albero non cambieresti l'info di un nodo ma diresti, in ipotesi:

albero.replace(55, 44)
List<Number> numeri = albero.getBranch(44);//piglia 44 e tutti i figli di 44

Da scrittore dell'albero realizzeresti questi replace e getBranch sapendo che 55 e 44 sono i valori dell'info di un Nodo.

La generica possibilità che da utente della libreria albero tu possa dire nodo.setInfo(qualcosa di diverso) causa effettivamente le stramberie che intuisci. Nel caso del tuo albero solo nominali ma pensa all'ipotesi comune secondo cui la struttura dell'albero dipende dai valori che esso contiene: se cambi il valore di un nodo pregiudichi la coerenza dell'albero.

Ricapitolando, quando dici:

quarantaquattro.setInfo(55);

c'è una stranezza e un problema. La stranezza è che il nodo quarantaquattro si chiami così perchè denota la confusione tra struttura e dato. Il nodo è sempre una cosa diversa dal suo info. Il problema nasce dalla possibilità che la mutazione del valore detenuto dal nodo corrompa la struttura dati.

Non che gli info dei nodi non devano cambiare: cambiano eccome. E' solo che il loro cambiamento è sempre controllato dall'albero a cui appartengono.

[Mulder90]

Secondo te mi conviene lasciare così come è ora?

[PGI-Bis]

Dipende dai requisiti dell'esercizio. Personalmente se fossi costretto a scriverlo non lo farei così ma è una considerazione che lascia il tempo che trova: bisogna vedere quanta libertà hai - ho visto esercizi in cui non ve n'è alcuna - quali sono le basi di partenza, quali sono i parametri di valutazione eccetera eccetera.

[Mulder90]

ultimo dubbio prima della consegna.
Il metodo per fare la visita in profondità l'ho implementato così:


public LinkedList<NodoVP<T>> visitaProfondità() {
System.out.println("Visita dell'albero in profondità: ");
LinkedList<NodoVP<T>> nodi = new LinkedList<NodoVP<T>>();
LinkedList<NodoVP<T>> pila = new LinkedList<NodoVP<T>>();
pila.addFirst(radice);
while (!pila.isEmpty()) {
NodoVP<T> u = pila.removeFirst();
System.out.print(u.getInfo() + " ");
nodi.addLast(u);
for (int i = u.getFigli().size() - 1; i >= 0; i--)
pila.addFirst((u.getFigli().get(i)));
}
return nodi;
}

Si può fare di meglio?

[PGI-Bis]

Per me va bene così.