Newsgroup: it.scienza.informatica
Titolo: alberi con numero illimitato di figli

Salve, tempo fa mi ero trovato a dover implementare una struttura dati ad
albero in cui ogni nodo doveva poter avere un numero qualsiasi di figli, non
decidibile a priori e aumentabile a piacere a run-time. Poi ho abbandonato.
Voi come fareste? Mi farebbe piacere avere uno scambio di idee, se è
permesso su questo newsgroup stile "Orwell", con tanto di Grande Fratello.
Michele.

Voi come fareste? Mi farebbe piacere avere uno scambio di idee, se č


 Voi come fareste?
Un B-Tree non lo permette?
--
Stefano Pettini
domi...@tiscalinet.it
web.tiscalinet.it/dominion
ICQ#: 38328322

Dipende da cosa ci vuoi fare con un tale albero...
il numero di nodi, il tipo di operazioni, la loro frequenza e le
prestazioni che si desiderano determinano le
possibili implementazioni di una struttura dati.
 
Una soluzione banale sarebbe utilizzare una
struttura nodo con una lista linkata di puntatori ai figli...
Paolo
-----------------------------------------------------------------
  Paolo Marotta
  Computer Science, University of Pisa
  home:   
http://www.cli.di.unipi.it/~marotta
-----------------------------------------------------------------

Basta usare questa stuttura:
struttura nodo
{ info: stringa o quel che ti pare
  primofiglio: puntatore a nodo
  primofratello: puntatore a nodo
}
Ciao Federico

decidibile a priori e aumentabile a piacere a run-time.
Che ci vuole? Se hai una struttura "nodo", l'informazione sui figli e' una
lista di puntatori a nodi contenuta nella struttura. Poi puoi implementare
la lista come ti pare (puntatori, array che si estende se vai out of bounds,
containers della STL se usi il C++ eccetera).
                                          Ciao
                                          Antonio
Antonio Frangioni                      Research Associate  |  I have gained ...
Dip. di Informatica - Corso Italia 40 - 56125 Pisa, Italy  |  the colour of the
Ph +039-50-887216                
www.di.unipi.it/~frangio
  |  corn.   [Exupery]

 Michele.
Implementerei i puntatori ai figli con una lista.
Se il linguaggio che usi ammette gli array dinamici puoi usare anche quelli.
P.S:
Ma perchč spesso non riesco a piazzare le mie risposte nel thread?
Alessandro Monti

 Michele.
Sei stato un po' troppo generico... che preparazione hai ? Che linguaggi
conosci ?
Credo che tu non abbia ancora molta esperienza di programmazione (quella
seria).
Allora, ti consiglio di procurarti un manuale di C anche soltanto per
imparare i principi di base della programmazione e del linguaggio C.
Generalmente, per costruire un albero si utilizza il concetto di allocazione
dinamica della memoria. In pratica, è un meccanismo che ti permette di
creare delle variabili in fase di run-time. Ogni volta che avrai bisogno di
aggiungere un nuovo nodo, allocherai dinamicamente una nuova variabile che
conterrà le informazioni del nodo, e la collegherai opportunamente con dei
puntatori all'interno dell'albero.
Le funzioni C utilizzate per allocare dinamicamente dello spazio in memoria
sono alloc, malloc, ecc. Per poter scrivere una procedura come quella che
serve a te bisogna avere ben chiaro anche il concetto di variabili di tipo
puntatore, ovvero variabili che contengono al loro interno un indirizzo di
memoria.
Se preferisci il Pascal, può fare quanto ti ho detto fin ora in modo
analogo.
Studia, studia, studia, sei solo agli inizi...
Se vuoi fare sul serio, studia bene adesso, sarà un investimento per il
futuro.
Ciao,
Riccardo

 dinamica della memoria. In pratica, è un meccanismo che ti permette di
Questa lettera mi ha fatto notare che quasi tutte le risposte precedenti
erano molto brevi, supponendo che il problema fosse banale, ma, salvo
smentite, se uno chiede come fare a costruire alberi con numero di figli
qualsiasi, io suppongo che sia in grado di costruire alberi con almeno 2
figli, e magari con un numero qualsiasi (pur se fissato a compile-time).
Credo anche che, sapendo come si costruisce un albero, sappia cos'e'
l'allocazione dinamica.
Immagino anche che il concetto di lista non sia nuovo.
Magari ha anche un manuale di C. (o di Pascal, o java, o altro)
:)
Alessandro Monti
P.S.
Spero non sia considerato un flame, non è questa la mia intenzione.

 wrote in message
AQqA3.60317$6C.1...@typhoon.libero.it...


Lo sai cha avevo pensato la stessa soluzione quella volta? Ogni nodo però
aveva anche un puntatore al padre, in modo da poter risalire all'inizio
della catena dei fratelli. Però la difficoltà era accrescere l'albero,
perché se io salvavo i vari record i n un file sequenzialmente, per ogni
nodo aggiunto dovevo sempre riaccedere ai record precedenti, con un sacco di
tempo perso a far ruotare il disco (infatti avevo migliaia di record, e
organizzarli tutti in un array in memoria poteva portare a un out of
memory). Siccome però mi sembra la soluzione migliore, volevo chiederti se
per caso hai mai provato a implementarlo e se sì come...
Ciao
Michele

Volevo precisare un paio di cose:
1) io programmo in delphi 1, ma non sono sceso nello specifico perché qui si
parla di informatica teorica e avevo paura di essere censurato.
2) ho abbastanza pratica di programmazione, anche di allocazione dinamica,
però mettere una lista dinamica in ogni record avrebbe lo svantaggio di
generare ogni record di una dimensione diversa, ma ciò non è possibile dato
che poi i record vanno organizzati in un file, e mettere un array di
puntatori di dimensione fissa molto elevata porterebbe a file enormi e pur
sempre a un limite nel numero di figli.

 sempre a un limite nel numero di figli.
Vediamo se questa volta ho capito qual è veramente il tuo problema...
Hai utilizzato una struttura simile a quella descritta sotto per creare un
albero con un numero illimitato di figli.
Il tuo problema non è "costruire l'albero in fase di run-time", ma piuttosto
"memorizzare l'albero creato in un file".
Giusto ?
    struttura Nodo
        sInfo: informazione del nodo corrente
        pPadre: puntatore al nodo padre
        pFiglio: puntatore al primo figlio
        pFratello: puntatore al prossimo nodo nella lista dei fratelli
    fine struttura
Allora ecco cosa puoi fare, a patto di rinunciare all'efficienza in fase di
Lettura/Scrittura dell'albero nel file.
Per creare i nodi dell'albero utilizza la seguente struttura, ignorando per
il momento il campo nKey:
    Struttura Nodo
        nKey: Chiave numerica del nodo corrente
        sInf: Informazione del nodo corrente
        pPadre: Puntatore al padre
        pFiglio: Puntatore al primo figlio
        pFratello: Puntatore al prossimo nodo nella lista dei fratelli
    Fine struttura
A questo punto esegui tutti i tuoi passi per costruire l'albero in memoria
centrale, utilizzando i soliti meccanismi di allocazione dinamica.
Crea anche la seguente struttura, in cui al posto dei vari puntatori hai
delle chiavi numeriche di cui ti parlerò in seguito:
    Struttura RecNodo
        nKey: Chiave numerica del nodo corrente
        sInf: Informazione del nodo corrente
        kPadre: Chiave del padre
        kFiglio: Chiave del primo figlio
        kFratello: Chiave del fratello (il successivo nella lista dei
fratelli)
    Fine struttura
Dovrai scrivere anche alcune procedure aggiuntive:
    AssignKeys:    (Assegna delle chiavi numeriche ai nodi dell'albero
partendo dalla radice ed arrivando alle foglie)
        K <- 1 (Non usare K <- 0 perché il valore 0 ti servirà più
avanti...)
        Visita l'albero con una procedura che lo attraversa per livelli, dal
livello 0 (radice) al livello n (foglie):
            Per ogni nodo attraversato
                Nodo.nKey <- K
                K <- K+1
            Fine
    SaveTree:    (Salva l'albero su disco, in un formato opportuno)
        Visita l'albero con una procedura che lo attraversa per livelli, dal
livello 0 (radice) al livello n (foglie):
            Per ogni nodo attraversato
                RecNodo.nKey <- Nodo.nKey
                RecNodo.sInf <- Nodo.sInf
                RecNodo.kPadre <- (Nodo.pPadre).nKey
                RecNodo.kFiglio <- (Nodo.pFiglio).nKey
                RecNodo.kFratello <- (Nodo.pFratello).nKey
                Write(RecNodo)
            Fine
        (Se pPadre/pFiglio/pFratello sono NULL allora utilizza la chiave 0
per nPadre/nFiglio/nFratello)
Una volta che l'albero è stato creato e che bisogna salvarlo su disco,
chiama nell'ordine le due procedure:
    AssignKeys
    SaveTree
Per caricare dal disco alla memoria centrale, dovrai scrivere una procedura
simmetrica a SaveTree e che grazie ai valori delle chiavi ti permetterà di
trasformare i RecNodo in Nodo e di effettuare i giusti collegamenti tra i
vari nodi che avrai caricato in memoria.
La mia è solo un'idea, adattala opportunamente al tuo problema.
Non avendo verificato il funzionamento dell'algoritmo, ti consiglio di
analizzarlo a fondo prima di usarlo eventualmente.
Spero di esserti stato di aiuto,
Riccardo

 ha scritto nel messaggio ...


Grazie a tutti quelli che mi hanno dato dei chiarimenti!
Michele

Ancora in proposito del su(bj)ddetto problema, mi
viene in mente: un esempio di albero con numero
variabile e potenzialmente infinito di figli per 
ogni nodo e' il filesystem di un sistema operativo.
Perche' non provi a salvare ogni nodo non terminale
come una directory e ogni nodo terminale come un file?
Eventuale informazione di ogni nodo non terminale la
puoi salvare in un file speciale, e il problema della
frammentazione resterebbe al s.o.
Se poi hai l'esigenza di tenere tutto in un file, potresti
simulare un semplice filesystem su un file, con tanto di fat
e lista_libera. (ovvero la fat e' la struttura dell'albero,
che riferisce indici di "blocco" nel resto del file - sarebbe
opportuno utilizzare files ad accesso casuale - e l'informazione
e' appunto suddivisa in blocchi. I blocchi liberi nel file li tieni 
in una lista e quando cancelli un nodo restituisci i blocchi ottenuti
alla lista medesima. Poi avrai il problema della frammentazione,
ma puoi deframmentare il file nei momenti di scarso utilizzo della
applicazione, almeno credo)
Fammi sapere
 
===============================================
Vincenzo Ciancia
Studente del Quarto anno  ( AH AH AH AH AH ...)
Corso di laurea in Informatica
Universita' di Pisa
-----------------------------------------------
Linux e' un regalo
Windows e' solo un pacco
===============================================