[C++] Progetto con strutture ad alberi per memorizzare parole in RAM

[darknessone]

Problema urgentissimo,
devo consegnare un progetto all' università fra circa 8 giorni.
Solo adesso il prof ha suggerito una nuova struttura dati! Maledetto!

Dobbiamo memorizzare circa 500.000 parole in RAM.
Potete ben vedere tutti che questo ha un enorme costo in memoria.
Per risparmiare memoria, ci ha consigliato una struttura descritta in questo documento...
E' una struttura ad alberi! Purtroppo non riesco a capirla e quindi non riesco ad implementarla!
Perfavore, qualche anima pia mi spieghi come funziona e mi occuperò io di implementarla!
Grazie a tutti!!!!

Link del documento che spiega la struttura (in inglese):
http://www.cs.princeton.edu/~rs/strings/paper.pdf

[LeleFT]

Di urgentissimo c'è solo che tu legga il regolamento.


Ciao.

[darknessone]

Scusa, suppongo che mi avete ripreso per la parole Urgentissimo... Scusate, ero troppo preso dalla fretta, riscusatemi!
Come faccio a rimodificarlo (il titolo)?
Se ci sono altri problemi ditelo, io ho visto solo questo nel regolamento.

Mi scuso di nuovo con tutta la community. Grazie.

[LeleFT]

Il titolo l'ho già corretto io... il titoletto sul tuo primo post rimane per i posteri.


Ciao.

[doraemon83]

Ho dato uno sguardo soltanto superficiale a quel documento ma mi pare di aver capito che tratta degli alberi binari di ricerca, il che mi fa pensare che il tuo prof, piu che ottimizzare l'uso della memoria abbia suggerito un metodo per migliorare le ricerche nell'elenco di parole.

Un albero binario è una struttura definita ricorsivamente.

1. Ha un nodo radice;
2. ha un sottoalbero sinistro (che è a sua volta un albero binario);
2. ha un sottoalbero destro (che è a sua volta un albero binario);

Un albero binario di ricerca è un particolare albero binario che rispetta una caratteristica fondamentale :

La chiave di ogni nodo è maggiore o uguale a tutte le chiavi che si trovano nel sottoalbero sinistro, e minore di tutte le chiavi che si trovano nel sottoalbero destro.

Con questa assunzione le ricerche all'interno dell'albero diventano molto efficienti perché ogni confronto dimezza il numero di valori in cui ricercare, riducendosi quindi a una ricerca binaria.

spero di averti chiarito qualche cosa.

ciao ciao

[darknessone]

grazie della risposta, ma lui ci aveva suggerito questo documento solo per ottimizzare l' uso della memoria RAM facendola scendere sotto i 160 MB (attuali).
Quindi se qualcun'altro vuole suggerirmi altro sono qui ad ascoltarlo.

PS: noi abbiamo gia' usato la struttura ad alberi.. ma la nostra non e' ottimizzata quanto quella suggerita nel PDF che ho postato...