Vă mulțumim pentru susținere

Cel mai bun BST cu auto-echilibrare pentru introducerea rapidă a unui număr mare de noduri

Am reușit să găsesc detalii despre câteva coduri de auto-echilibrare BST s prin mai multe surse, dar nu am găsit nicio descriere bună detaliind care este cea mai bună utilizare în situații diferite nu contează).

Vreau un BST care este optim pentru stocarea a peste zece milioane de noduri. Ordinea de inserare a nodurilor este în principiu aleatorie și nu voi mai trebui să șterg nodurile, deci timpul de inserție este singurul lucru care ar trebui să fie optimizat.

Intenționez să-l folosesc pentru a stoca stările de joc vizitate anterior într-un joc de puzzle, astfel încât să pot verifica rapid dacă o configurație anterioară a fost deja întâlnită.

0
adăugat editat

3 răspunsuri

Red-black is better than AVL for insertion-heavy applications. If you foresee relatively uniform look-up, then Red-black is the way to go. If you foresee a relatively unbalanced look-up where more recently viewed elements are more likely to be viewed again, you want to use splay trees.

0
adăugat

[tabelele de hash au] O (1) inserare și căutare

Cred că este greșit.

Mai întâi, dacă limitați spațiul de chei pentru a fi finit, puteți stoca elementele într-o matrice și puteți efectua o scanare liniară O (1). Sau ai putea shufflesort matricea și apoi face o scanare liniară în O (1) timpul așteptat. Când lucrurile sunt finite, lucrurile sunt ușor O (1).

Deci, să spunem că tabela dvs. de hash va stoca orice șir de biți arbitrari; nu contează prea mult, atâta timp cât există un set infinit de chei, fiecare dintre acestea fiind finite. Apoi trebuie să citiți toți biții oricărei interogări și intrări de introducere, altfel am inserat y0 într-o hash goală și o interogare pe y1, unde y0 și y1 diferă la o poziție de un singur bit pe care nu te uiți la.

Dar să presupunem că lungimea cheilor nu este un parametru. Dacă inserarea și căutarea dvs. iau O (1), în special hashing-ul are o durată O (1), ceea ce înseamnă că vă uitați doar la o cantitate finită de ieșire din funcția hash (de la care este probabil să fi numai o ieșire finită, acordată).

This means that with finitely many buckets, there must be an infinite set of strings which all have the same hash value. Suppose I insert a lot, i.e. ω(1), of those, and start querying. This means that your hash table has to fall back on some other O(1) insertion/search mechanism to answer my queries. Which one, and why not just use that directly?

0
adăugat
Aceasta este înțelepciunea convențională. Cel mai bun caz, O (1), în mod evident implementările vor varia. Există o varietate de algoritmi diferite de tabele hash.
adăugat autor ApplePieIsGood
@MeNoMore Jonas corect a folosit un format de cotatie pentru prima linie a raspunsului sau, pentru ca a fost o citare a altcuiva. Nu faceți astfel de modificări în viitor.
adăugat autor Andrew Barber
@menomore Parantezele reprezintă conținut parafrazat, realizat pentru ușurință în înțelegere. Este o utilizare foarte comună. Parafrazarea și citatul provin din răspunsul lui boyetboy.
adăugat autor Andrew Barber
@ JonasKölker Scuzele mele; ai dreptate. Vă mulțumim pentru memento :)
adăugat autor Andrew Barber
@AndrewBarber Data viitoare când aveți o solicitare de utilizare a cuvântului sau vă rugăm să contactați un moderator. Acum, la această problemă, în timp ce v-ați referit la acest lucru, am fost îngrămădit de parantezele pătrate în: [tabelele hash] vedeți vreun motiv pentru asta? acest termen nu este în nici un alt loc pe pagină?
adăugat autor CloudyMarble
@AndrewBarber Mulțumesc
adăugat autor CloudyMarble
"Aceasta este înțelepciunea convențională". - Am auzit de multe ori, dar încă nu am văzut o dovadă. Cred că ar fi bine să contestați această piesă de folclor dacă doriți rezultatul teoretic "este O (1)" sau să măsurați diferite structuri de căutare dacă doriți "rapid în practică". "Cel mai bun caz, O (1)" - arborele de căutare dezechilibrat are și el acest lucru, dar nimeni nu susține că are "O (1) inserare și căutare".
adăugat autor Jonas Kölker
În cel mai bun caz, utilizatorul caută valoarea stocată la nodul rădăcină, care are timp O (1) pentru a accesa ...
adăugat autor Jonas Kölker
@AndrewBarber: "Data viitoare când aveți o solicitare de utilizare a cuvântului sau vă rugăm să contactați un moderator." // data viitoare când ați corecta pe cineva, v-ați dori ca decența să fie un model bun pentru comportamentul pe care îl doriți de la ceilalți?
adăugat autor Jonas Kölker
Cu plăcere :-)
adăugat autor Jonas Kölker
un arbore de căutare dezechilibrat cu cel mai bun caz va fi un nod de la echilibrat. Cel mai bun caz de inserare / căutare este încă log (n)
adăugat autor µBio

De ce să folosiți deloc un BST ? Din descrierea dvs. un dicționar va funcționa la fel de bine, dacă nu chiar mai bine.

Singurul motiv pentru care ați folosit BST ar fi dacă doriți să afișați conținutul containerului în ordinea cheie. Cu siguranta nu suna ca si cum ai vrea sa faci asta, caz in care mergem la masa de hash. O (1) inserare și căutare, nu vă faceți griji despre ștergere, ce ar putea fi mai bine?

0
adăugat