alberi in java

[terence_81]

Salve,

dove posso trovare informazioni dettagliate su come costruire un albero generico in java (non binario) e poi applicare un algoritmo di ricerca?
Grazie

[Dr_House]

Bhé penso che una ricerca su googe possa bastare per trovare qualche informazione sugli alberi..

Poi che siano binari o meno conta poco, il procedimento è quello, una classe Node che contiene i puntatori ai nodi successivi e campi informazione

Nella classe principale per creare l'albero ti serve:

un costruttore che crei la radice dell'albero

per l'inserimento ci sono varie politiche ma si tratta di riempire l'albero dando il figlio sinistro ed il figlio destro etc...

comunque cercando su google
http://www.google.it/search?hl=it&q=...n+Google&meta=

[PGI-Bis]

Un albero generico, nel senso del grafo connesso aciclico, è molto più semplice di quanto si veda in giro. Più che altro perchè in giro si vedono gli alberi che servono a qualcosa .

E' una collezione di oggetti con tre proprietà: un valore, un genitore, dei figli. Una volta che hai creato un oggetto con queste caratteristiche hai anche il tuo albero. Se aggiungi al nodo la capacità di assumere nuovi figli hai anche la possibilità di costruire dinamicamente il tuo albero. Ad esempio:

class Nodo {
	private Object valore;
	private Nodo genitore;
	private List<Nodo> figli = new LinkedList<Nodo>();

	public Nodo(Nodo genitore, Object valore) {
		this.genitore = genitore;
		this.valore = valore;
	}

	public Object valore() {
		return valore;
	}

	public void aggiungiFiglio(Nodo figlio) {
		figli.add(figlio);
	}

	public Collection<Nodo> figli() {
		return figli;
	}
}

Nodo è l'elemento di un albero generico. Nodo e albero sono quindi due cose diverse. Essendo l'albero un grafo connesso se hai in mano il nodo radice (in verità un nodo qualsiasi) puoi navigare lungo tutto l'albero. In questo senso, la rappresentazione di un albero è solitamente l'insieme di funzioni che agiscono su un nodo radice. Supponiamo che questo insieme di funzioni che agiscono su una radice siano l'inserimento e l'attraversamento. Attraversare l'albero significa passare di nodo in nodo finchè non arrivi al punto di poter dire: ho visto tutti i nodi, da cui "visitare" il nodo. Un tipo semplicissimo di attraversamento è detto "in ampiezza". Parti dalla radice R. Visiti ogni figlio di R. Per ogni figlio di R, visiti i suoi figli. Poi visiti i figli dei figli. E i figli dei figli dei figli... finchè arrivi in fondo. E' più facile a farsi che a dirsi. Supponendo che "radice" sia un Nodo (nel senso della classe di prima), l'attraversamento in ampiezza dell'albero di cui "radice" è radice sarebbe:

public void attraversaInAmpiezza(Nodo radice) {
    ArrayList<Nodo> nodi = new ArrayList<Nodo>();
    nodi.add(radice);
    for(int i = 0; i < nodi.size(); i++) {
        Nodo nodo = nodi.get(i);
        System.out.println(nodo.valore());
        nodi.addAll(nodo.figli());
    }
}

Qui il "System.out.println(nodo.valore())" sta per "visita il nodo".

La ricerca di un nodo nell'albero (trova il nodo N il cui valore è V) è una degenerazione dell'attraversamento. Data la radice "radice" ed il valore "valore", trovare il nodo N il cui valore è "valore" significa percorrere tutto l'albero finchè non trovi un nodo che corrisponda al requisito. Ad esempio:

public Nodo trovaNodo(Nodo radice, Object valore) {
    ArrayList<Nodo> nodi = new ArrayList<Nodo>();
    nodi.add(radice);
    for(int i = 0; i < nodi.size(); i++) {
        Nodo nodo = nodi.get(i);
        if(nodo.valore().equals(valore)) {
            return nodo;
        }
        nodi.addAll(nodo.figli());
    }
    return null;
}

E' come prima solo che stavolta ci si ferma (return) quando si trova il nodo il cui valore corrisponde a quello cercato.

L'inserimento di un valore nell'albero è un'operazione relativa al valore di un nodo che diventerà il genitore dell'inserito. Così l'inserimento è un procedimento in due fasi:

Dato il valore V da inserire nell'albero di radice R rispetto al valore V':
1. trova il nodo N' che contiene V'
2. inserisci in N' un nuovo nodo N il cui valore è V.

Dato il metodo di ricerca precedente, la traduzione potrebbe essere:

public void inserisci(Object nuovoValore, Object valoreGenitore) {
    Nodo genitore = trovaNodo(valoreGenitore);
    if(genitore != null) {
        Nodo figlio = new Nodo(genitore, nuovoValore);
        genitore.aggiungiFiglio(figlio);
    }
}

Comunque un albero del genere non è esattamente un maestro di utilità.

[terence_81]

Grazie mille della spiegazione! Ne approfitto per sottoporre un altro quesito:

Prendi in esame il gioco del quindici (il gioco in cui si devono mettere in ordine i numeri dall'1 al 15 avendo un solo posto libero per muovere le varie caselle) e mettiamo che io debba portare la casella 1 al suo posto. Il mio pbiettivo è trovare il percorso che mi porti la casella 1 al suo posto con il minor numero di spostamente di celle possibili. Quindi costruisco un grafo che mi permetta di esplicitare tutti i percorsi che la casella 1 può percorrere per raggiungere la sua esatta posizione. Nel mio caso la strategia usata permette alla casella 1 di spostarsi solo in quelle posizioni che la avvicinano alla sua posizione esatta, ovvero nelle celle che minimizzano la distanza di Manhattan e quindi non avrò cicli e percorsi che si ripetono, ovvero il mio grafo non avrà archi che tornano indietro. Sotto queste condizioni io ho che i nodi mi rappresentano le celle in cui posso spostare la casella 1, mentre i pesi degli archi indicano quanti spostamenti di caselle in totale devo fare per spostare la mia casella 1 da una cella ad un'altra adiacente (in questo caso ho che il peso di ogni arco può essere 3 o 5). Quindi il mio grafo sarà in realtà un albero che avrà nodi uguali, cioè diversi nodi che indicano la stessa cella, perchè il peso dell'arco che va da un nodo ad un altro può avere due valori diversi (3 o 5) a seconda di dove si trova la casella vuota per gli spostamenti e quindi a seconda di dove si trovava la casella 1 prima di giungere al primo dei due nodi in quesione.
Questo algoritmo va bene se il mio obiettivo è portare la casella 1 al suo posto con il minor numero di spostamenti di celle totali e quindi nel minor tempo possibile? E una volta costruito l'albero posso usare un algortimo greedy per cercare la soluzione migliore? Perchè sperimentalmente ho visto che praticamente "l'algoritmo ottimo" è quello per cui la casella 1 si sposti sempre diagonalmente (quindi con 3 spostamenti di celle ogni volta) ed eventualemente se incontra il lato sinistro o superiore del quadrante inzia a spostarsi verticalmente o orizzontalmente ogni volta con un numero di 5 spostamente di caselle.

Spero di esser stato chiaro

[PGI-Bis]

Volevo dirti di sì ma, colpito da rimorso preventivo, sono andato a scartabellare un paio di volumi su algoritmi e strutture dati.

Dopo il quotidiano bagno d'umiltà, la risposta ufficiale è: non lo so

Se dicessi sì dovrei anche essere in grado di dartene la matematica dimostrazione e ho appena capito (in verità mi sono ricordato di essermi scordato) che non sono in grado di farlo .

[terence_81]

Ti ringrazio per l'impegno