Miglior BST autobilanciante per l'inserimento rapido di un gran numero di nodi

Question

Sono riuscito a trovare dettagli su diversi autobilanciamenti BSTs attraverso diverse fonti, ma non ho trovato alcuna buona descrizione che descriva in dettaglio quale sia la migliore da utilizzare in diverse situazioni (o se davvero non ha importanza).

voglio un BST questo è ottimale per archiviare oltre dieci milioni di nodi.L'ordine di inserimento dei nodi è sostanzialmente casuale e non avrò mai bisogno di eliminare nodi, quindi il tempo di inserimento è l'unica cosa che dovrebbe essere ottimizzata.

Intendo usarlo per memorizzare gli stati del gioco visitato in precedenza in un puzzle game, in modo da poter verificare rapidamente se è già stata riscontrata una configurazione precedente.

Answer 1

Rosso nero è migliore di AVL per applicazioni con inserimenti pesanti.Se prevedi uno sguardo relativamente uniforme, allora il rosso-nero è la strada da percorrere.Se prevedi una ricerca relativamente sbilanciata in cui è più probabile che gli elementi visualizzati più di recente vengano visualizzati di nuovo, puoi utilizzare alberi divaricati.

Answer 2

Perché usare a BST affatto?Dalla tua descrizione un dizionario funzionerà altrettanto bene, se non meglio.

L'unico motivo per utilizzare a BST lo sarebbe se volessi elencare il contenuto del contenitore in ordine chiave.Certamente non sembra che tu voglia farlo, nel qual caso scegli la tabella hash. O(1) inserimento e ricerca, nessuna preoccupazione per la cancellazione, cosa c'è di meglio?

Answer 3

I due si autobilanciano BSTQuelli con cui ho più familiarità sono rosso-nero e AVL, quindi non posso dire con certezza se altre soluzioni siano migliori, ma, se ricordo bene, il rosso-nero ha un inserimento più veloce e un recupero più lento rispetto a AVL.

Quindi, se l'inserimento ha una priorità più alta rispetto al recupero, il rosso-nero potrebbe essere una soluzione migliore.

Answer 4

[le tabelle hash hanno] O(1) inserimento e ricerca

Penso che questo sia sbagliato.

Prima di tutto, se limiti lo spazio delle chiavi a essere finito, puoi memorizzare gli elementi in un array ed eseguire una scansione lineare O (1).Oppure potresti ordinare in modo casuale l'array e quindi eseguire una scansione lineare nel tempo previsto O (1).Quando le cose sono finite, le cose sono facilmente O(1).

Quindi diciamo che la tua tabella hash memorizzerà qualsiasi stringa di bit arbitraria;non ha molta importanza, purché esista un insieme infinito di chiavi, ognuna delle quali è finita.Quindi devi leggere tutti i bit di qualsiasi query e input di inserimento, altrimenti inserisco y0 in un hash vuoto e interrogo su y1, dove y0 e y1 differiscono in una singola posizione di bit che non guardi.

Ma diciamo che la lunghezza delle chiavi non è un parametro.Se l'inserimento e la ricerca richiedono O(1), in particolare l'hashing richiede O(1), il che significa che si guarda solo una quantità finita di output dalla funzione hash (da cui è probabile che Essere solo un output finito, garantito).

Ciò significa che con un numero finito di bucket, deve esserci un insieme infinito di stringhe che hanno tutte lo stesso valore hash.Supponiamo di inserire molto, ad es.ω(1), di questi, e inizia a interrogare.Ciò significa che la tua tabella hash deve ricorrere a qualche altro meccanismo di inserimento/ricerca O(1) per rispondere alle mie domande.Quale e perché non usarlo direttamente?