Beste self-balansering BST vir 'n vinnige inplanting van 'n groot aantal nodes

Question

Ek het in staat was om inligting oor 'n paar self-balansering BSTs vind deur middel van verskeie bronne, maar ek het nie gevind nie enige goeie beskrywings wat aandui watter een is die beste om te gebruik in verskillende situasies (of as dit regtig nie saak nie) .

Ek wil 'n BST wat optimaal is vir die berging van meer as tien miljoen nodes. Die einde van invoeging van die nodes is basies ewekansige, en ek sal nooit nodig het om knope te verwyder, so voeg tyd is die enigste ding wat nodig sou wees om geoptimaliseer.

Ek is van plan om dit te gebruik om voorheen besoek spel state op te slaan in 'n spel, sodat ek vinnig kan kyk of 'n vorige opset reeds teëgekom het.

Answer 1

Rooi-swart is beter as AVL vir invoeging-swaar aansoeke. As jy relatief eenvormige voorkoms-up voorsien, dan Rooi-swart is die pad om te gaan. As jy 'n relatief ongebalanseerde look-up waar meer onlangs gesien elemente is meer geneig om weer gesien word voorsien, wat jy wil gebruik helling bome .

Answer 2

Hoekom gebruik 'n BST glad? Van jou beskrywing sal 'n woordeboek net so goed werk, indien nie beter.

Die enigste redes vir die gebruik van 'n BST sou wees as jy wou 'n lys van die inhoud van die houer in sleutel orde. Dit is beslis nie klink soos wat jy wil om dit te doen, in welke geval gaan vir die hash tafel. O(1) inplanting en soek, geen bekommernisse oor te skrap, wat kan beter wees?

Answer 3

Die twee self-balansering BSTs Ek is die meeste vertroud is met rooi-swart en AVL, so ek kan nie met sekerheid sê of enige ander oplossings is beter, maar as ek reg onthou, rooi-swart het vinniger te voeg en stadiger herwinning in vergelyking met AVL.

As inplanting is 'n hoër prioriteit as herwinning, rooi-swart kan 'n beter oplossing wees.

Answer 4

  

[hash tabelle] O (1) in te voeg en soek

Ek dink dit is verkeerd.

In die eerste plek, as jy die keyspace beperk eindige te wees, jy kan die elemente in 'n skikking te stoor en doen 'n O (1) lineêre scan. Of jy kan die skikking shufflesort en dan doen 'n lineêre scan in O (1) verwag tyd. Wanneer dinge eindig, dinge is maklik O (1).

So kom ons sê jou hash tafel sal enige arbitrêre bietjie string slaan; Dit verg nie veel saak nie, solank daar 'n oneindige stel sleutels, wat elkeen is beperk. Dan moet jy al die stukkies van enige navraag en voeg insette te lees, anders het ek y0 voeg in 'n leë hash en navraag oor y1, waar y0 en y1 verskil aan 'n enkele stukkie posisie wat jy nie kyk na.

Maar kom ons sê die sleutel lengtes is nie 'n parameter. As jou te voeg en soek neem O (1), in die besonder hashing neem O (1) tyd, wat beteken dat jy net kyk na 'n eindige hoeveelheid uitset van die hash funksie (waaruit daar is geneig om te wees net 'n beperkte uitset, verleen).

Dit beteken dat met eindig baie emmers, daar moet 'n oneindige stel snare wat almal dieselfde hash waarde wees. Dink ek 'n baie voeg, dit wil sê ω (1), van die, en begin bevraagteken. Dit beteken dat jou hash tafel het om weer op 'n ander O (1) in te voeg / search meganisme val om my vrae te beantwoord. Watter een, en hoekom nie net gebruik wat direk?