[C++] Tabella hash o albero binario di ricerca?

[Esphelex]

Salve a tutti!
Mi è stato assegnato un progetto di algoritmi e strutture dati,
in cui si richiede di implementare un motore di ricerca semplificato:
ho una collezione di file di testo e, una volta acquisite le parole (non case sensitive e solo alfanumeriche), devo organizzarle in modo da poter fare delle ricerche.
Si richiede di poter fare:
una ricerca di una parola, che restituisce l'elenco non ordinato dei file in cui compare tale parola.
una ricerca di una parola, che restituisce l'elenco ordinato (si contano le occorrenze della parola).
una ricerca di più parole (non frasi, quindi sarebbe una ricerca multipla di parole) non ordinate e ordinate.

Naturalmente il programma sarà valutato sulla velocità di esecuzione delle ricerce (e non dell'acquisizione) e, magari, anche dello spazio utilizzato.

Volevo soltanto un consiglio: cioè se utilizzare una tabella hash (complessità quasi costante, se non ci sono troppe collisioni) o albero binario (complessità logaritmica).
Io avevo pensato una cosa del genere:
Acquisisco le parole e mi creo un lista di oggetti: ogni oggetto di tale lista ha un vettore per il numero dei file, e ogni cella tiene tracce del numero di occorrenze di tale parola e del file preso in considerazione.
Guardo la lunghezza della lista e mi creo una tabella hash di oggetti come la lista del 20% più grande.
Eseguo la funzione hash sulle parole della lista e le inserisco in tabella la parola e nel vettore le altre informazioni su occorenze e file. Magari potrei ordinarle con dei puntatori così da risolvere la ricerca ordinata di singola parola.
Per la ricerca di più parole ordinate, si devono sommare le varie occorrenze e poi eseguire un algoritmo di ordinamento (tipo quicksort).
Oppure con gli alberi di binari, più o meno la stessa cosa.

Cosa ne pensate??? Help help help

[GliderKite]

Se dovessi scegliere tra una tabella di hash e un albero binario di ricerca, se fossi in te implementerei, per questo caso, un buon BST basato su alberi 2-3-4 magari attraverso l'implementazione di un red-black.

[Esphelex]

Ma la ricerca è logaritmica, quali sarebbero i vantaggi in termini di tempo?

[GliderKite]

Originariamente inviato da Esphelex
Ma la ricerca è logaritmica, quali sarebbero i vantaggi in termini di tempo?

Non capisco se la tua è una domanda o meno, in ogni caso la ricerca in un red-black di N nodi richiede sempre meno di 2 ln(N) + 2 confronti.

Quali sarebbero i vantaggi rispetto ad una tabella di hash?
Be innanzitutto dovresti spiegarti meglio perchè di hash table ve ne sono diverse. Tu che tipo volevi usare? Concatenazioni separate, scansione lineare, hashing doppio?

In ogni caso i vantaggi di un red-black per come la vedo io sarebbero:
- maggior facilità di implementazione e quindi di debug (se si esclude la concatenazione separata)
- Minor spreco di spazio (costo da non sottovalutare)
- Si evita la gestione delle collisioni (non esiste la funzione di hash perfetta, comunque nel tuo caso se si tratta di chiavi stringa ti consiglio l'utilizzo della funzione di hash universale a coefficienti pseudocasuali), che se non è ben fatta porta solo a grandi casini, soprattutto se le chiavi iniziano ad essere dell'ordine di 10^6
- La funzione di hash, soprattutto nel caso di chiavi stringa utilizza parecchie risorse (persino quella che ti ho indicato io potrebbe essere eccessivamente lenta per applicazioni che si basano sulla performance)
- Una ricerca in un albero di tipo 2-3-4 top-down non visita più di ln(N) + 1 nodi, quindi estremamente rapida (lo svantaggio è il costo che si paga in più nell'inserimento per la scomposizione durante lo scorrimento dei nodi di tipo 4-nodi, ma se non sbaglio questo non ha importanza per te).

In conclusione la ricerca dicotomica che offre il red-black è estremamente vantaggiosa sotto diversi punti di vista.