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.