Best selvbalanserende BST for rask innføring av et stort antall noder

stemmer
8

Jeg har vært i stand til å finne informasjon om flere selvbalanserende BSTs gjennom flere kilder, men jeg har ikke funnet noen gode beskrivelser detaljering hvilken som er best å bruke i ulike situasjoner (eller hvis det spiller ingen rolle).

Jeg vil ha en BSTsom er optimal for lagring i overkant av ti millioner noder. Rekkefølgen av innsetting av nodene er i utgangspunktet tilfeldig, og jeg vil aldri trenger å slette noder, så innsetting tid er det eneste som må være optimalisert.

Jeg har tenkt å bruke den til å lagre tidligere besøkte spill stater i et puslespill, slik at jeg raskt kan sjekke om det allerede er oppstått en tidligere konfigurasjon.

Publisert på 05/08/2008 klokken 15:40
kilden bruker
På andre språk...                            


4 svar

stemmer
3

Hvorfor bruke en BSTi det hele tatt? Fra din beskrivelse en ordbok vil fungere like bra, om ikke bedre.

Den eneste grunnen til å bruke en BSTville være hvis du ønsket å liste ut innholdet i beholderen i nøkkelrekkefølge. Det absolutt ikke høres ut som du ønsker å gjøre det, i så fall gå for hash table. O(1)innsetting og søk, ingen bekymringer om sletting, hva kan bli bedre?

Svarte 29/08/2008 kl. 00:10
kilden bruker

stemmer
3

Rød-svart er bedre enn AVL for innsetting-tunge applikasjoner. Hvis du forutse relativt ensartet look-up, deretter rød-svart er veien å gå. Hvis du forutse en relativt ubalansert look-up der mer nylig viste elementer er mer sannsynlig å bli sett igjen, ønsker du å bruke sprikende trær .

Svarte 05/08/2008 kl. 15:59
kilden bruker

stemmer
0

De to selvbalanserende BSTs jeg er mest kjent med er rød-svart og AVL, så jeg kan ikke si med sikkerhet om noen andre løsninger er bedre, men som jeg husker, har rød-svart raskere innsetting og tregere gjenfinning forhold til AVL.

Så hvis innlegging er en høyere prioritet enn gjenfinning, kan rød-svart være en bedre løsning.

Svarte 05/08/2008 kl. 15:50
kilden bruker

stemmer
-2

[Nøkkeltabeller ha] O (1) innsetting og søk

Jeg tror dette er galt.

Først av alt, hvis du begrense KEYSPACE å være begrenset, kan du lagre elementene i en matrise og gjøre en O (1) lineær skanning. Eller du kan shufflesort matrisen og deretter gjøre en lineær skanning i O (1) forventet tid. Når ting er begrenset, er ting enkelt O (1).

Så la oss si din hash table vil lagre vilkårlig litt streng; det gjør ikke saken mye, så lenge det finnes en uendelig sett med nøkler, som hver er endelig. Da må du lese alle biter av alle spørringer og innsetting innspill, annet jeg setter y0 i et tomt hasj og spørring på Y1, hvor y0 og y1 skiller seg på en enkelt bit posisjon som du ikke ser på.

Men la oss si at nøkkellengder er ikke en parameter. Hvis innsetting og søke ta O (1), særlig hashing tar O (1) tid, noe som betyr at du bare ser på en begrenset mengde av produksjonen fra hash-funksjon (der det er sannsynlig å være bare en begrenset effekt, gitt ).

Dette betyr at med endelig mange bøtter, må det være en uendelig sett med strenger som alle har samme hash-verdi. Anta at jeg setter mye, dvs ω (1), av dem, og begynne å spørre. Dette betyr at hash tabellen har å falle tilbake på en annen O (1) innsetting / søk mekanisme for å svare på mine spørsmål. Som en, og hvorfor ikke bare bruke den direkte?

Svarte 01/02/2009 kl. 12:49
kilden bruker

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more