slacky.eu

Sempre per esercizio, devo realizzare una struttura dati che consenta l'inserimento (e la cancellazione) di giocatori di basket con le relative statistiche di gioco;
ora non so se la struttura più adeguata sia un RB-albero (che da quel che ho capito è la struttura con cui è tipicamente implementato map della STL) o un' Hash table.
Per quel che ne so una tabella con una buona funzione di hash consente inserimenti ed estrazioni con tempo costante, ma (visto che anche gli alberi vengono spesso sfruttati) qualcuno sa dirmi quali vantaggi può offrire un RB-albero (visto che le operazioni su di esso hanno costo log(n))?
Grazie mille.

Come al solito dipende. Nell'albero tutte le operazioni hanno costo specifico log(n), mentre nella tabella hash questo non si può dire. Se la tabella è piccola, la funzione hash per quanto sagace creerà comunque dei duplicati, ovvero due entry che hanno lo stesso valore hash, a questo punto devi crearti una lista concatenate in cui sistemerai gli elementi doppi. Ma allora potrebbe anche darsi che l'operazione di ricerca diventi più costosa di una ricerca in un albero.

Potresti implementare una tabella hash che, quando si crea un duplicato viene inserito in un albero, in questo modo la funzione di ricerca sarebbe log(n) solo nel caso in cui la funzione hash inserisce tutti i valori nello stesso albero, altrimenti, nel caso normale, è log(x) dove x è un numero, minore di n , che rappresenta il totale degli elementi che hanno stesso valore hash.
Non so se mi sono spiegato bene, è come se avessi un array ogni cella del quale punta ad un albero, il compito di individuare in quale cella inserire l'elemento spetta alla funzione hash.

Ricordati inoltre che se vuoi stampare gli elementi in maniera ordinata, la funzione hash non è adatta. Se ad esempio vuoi stampare tutti i giocatori ordinati per cognome, con l'albero puoi usare il cognome come elemento di inserimento e quindi poi ti basta una scansione dell'albero per avere gli elementi già ordinati. Con la funzione hash devi scandire tutta la tabella e poi effettuare delle ricerche per determinare il primo, il secondo....

In questo caso potresti usare un array "associativo" di 25 celle, ognuna delle quali rappresenta una lettera dell'alfabeto (sono 25 vero?), potresti mettere tutti i giocatori il cui cognome inizia con la 'a' nella prima cella, quelli con la 'b' nella seconda e così via. Al solito ogni cella punta ad un albero in modo da avere una ricerca veloce. In questo modo per stampare tutti i giocatori ordinati per cognome basta scandire uno alla volta tutti i 25 alberi, con lo stesso costo che avresti scandendo un solo albero con tutti i giocatori. Qui quello che ci guadagni è nella ricerca, che al solito diventerebbe log(x) dove x è il numero di elementi inseriti in questo particolare albero.

Comunque tutto dipende da quello che vuoi farci ,
Spina

In realtà credo che per 25 elementi basti una tabella con indirizzamento diretto (non sono dimensioni esagerate) con tempo di ricerca costante, però visto che è un esercizio su strutture dati in generale l'idea di una tabella con indirizzamento anzichè con chaining classico (con la lista) con l'inserimento dei giocatori che collidono in un albero, mi sembra ottima.
Ti ringrazio per il chiarimento sulla questione hash / rb, non avevo pensato all'ordinamento, perchè alla fine se non lavori su grossi input e ti basta una tabella non eccessivamente grande l'hash è la soluzione più semplice credo...
grazie ancora Spina,
Nico

... mi ero scordato di chiudere il post, comunque alla fine ho optato per una struttura ibrida (come consigliato da Spina) costituita da una tabella hash con collisioni risolte con rb alberi.

Oramai è tardi
ma secondo me te la potevi cavare anche con una skip list, decisamente più facile da implementare di un RBtree.

qui è presente una lezione tenuta al mit sulle skip list

ZeD ha scritto:Oramai è tardi
ma secondo me te la potevi cavare anche con una skip list, decisamente più facile da implementare di un RBtree.

qui è presente una lezione tenuta al mit sulle skip list

...Sono d'accordo con te, e probabilmente non sarebbe neanche l' unica implementazione migliore di quella che alla fine ho scelto, ma essendo un esercizio inerente alle strutture dati viste a lezione, la SkipList era esclusa ed altre soluzioni più semplici ed altrettanto efficienti non mi sono venute in mente.