Nejlepší samovyvažující BST pro rychlé vložení velkého počtu uzlů

hlasů
8

Byl jsem schopen najít podrobnosti o několik samovyvažující BSTs pomocí několika zdrojů, ale nenašel jsem nějaké dobré popisy popisovat, který z nich je nejlepší používat v různých situacích (nebo je-li to opravdu nezáleží).

Chci BST, která je optimální pro ukládání více než deset milionů uzlů. Pořadí vložení uzlů je v podstatě náhodný, a nikdy nebudu muset odstranit uzly, takže čas vložení karty, je jediná věc, která by musela být optimalizována.

Mám v úmyslu ji použít k ukládání dříve na herní stavy ve puzzle hra, takže mohu rychle zkontrolovat, zda již byl narazí na předchozí konfiguraci.

Položena 05/08/2008 v 16:40
zdroj uživatelem
V jiných jazycích...                            


4 odpovědí

hlasů
3

Proč používat BSTvůbec? Z vašeho popisu slovníku bude fungovat stejně dobře, ne-li lepší.

Jediným důvodem, proč pomocí BSTby bylo, kdyby jste chtěli uvést mimo obsah kontejneru v pořadí klíče. Rozhodně to nezní jako vy chcete dělat, že v tomto případě jít na hash tabulky. O(1)vkládání a vyhledávání, žádné obavy o vymazání, co by mohlo být lepší?

Odpovězeno 29/08/2008 v 01:10
zdroj uživatelem

hlasů
3

Červeno-černá je lepší než AVL pro vložení těžkých aplikací. Máte-li předpokládat relativně rovnoměrné look-up, pak Red-black je způsob, jak jít. Jestliže předpokládáte relativně nevyvážená look-up, kde jsou více pravděpodobné, že bude opět viděn v poslední době viděli elementy, které chcete použít splay strom .

Odpovězeno 05/08/2008 v 16:59
zdroj uživatelem

hlasů
0

Dva samovyvažující BSTs Nejvíce mě znají, jsou červeno-černé AVL, takže nemohu s jistotou říci, zda některé jiné řešení jsou lepší, ale pokud si vzpomínám, červeno-černá má rychlejší vkládání a pomalejší načítání ve srovnání s AVL.

Takže pokud vložení je vyšší prioritu než načítání, červeno-černá, může být lepší řešení.

Odpovězeno 05/08/2008 v 16:50
zdroj uživatelem

hlasů
-2

[Hashovací tabulky mají] O (1) vložení a vyhledávání

Myslím, že je to špatně.

Za prvé, pokud si omezit keyspace být konečný, mohl ukládat prvky v poli a provést O (1) lineární skenování. Nebo byste mohli shufflesort pole a proveďte lineární prohledávání v O (1) předpokládané doby. Když věci jsou konečné, materiál je snadno O (1).

Takže řekněme, že vaše hash tabulky bude ukládat libovolný bitový řetězec; to není moc záležitost, jak dlouho jak tam je nekonečný svazek klíčů, z nichž každá je konečný. Pak budete muset přečíst všechny kousky jakéhokoliv dotazu a vkládání vstup, jinak bych vložit Y0 do prázdné hash a dotazu na y1, kde y0 a y1 se liší v jedné poloze bitu, které nechcete podívat.

Ale řekněme, že klíčové délky nejsou parametr. Pokud váš vkládání a hledání trvat O (1), zejména na hash trvá O (1) čas, což znamená, že se díváte pouze na konečné množství výstupu z hashovací funkce (z nichž je pravděpodobné, aby se jen konečný výstup, udělil ).

To znamená, že se konečně mnoha kbelíky, musí být nekonečná množina řetězců, které všechny mají stejnou hodnotu hash. Dejme tomu, že vložíte hodně, tj ω (1), z těch, a začít dotazování. To znamená, že hash tabulky se musí opřít o nějaké jiné O (1) mechanizmu vkládání / vyhledávání se odpovědět na mé dotazy. Který z nich, a proč ne jen používat, která přímo?

Odpovězeno 01/02/2009 v 13:49
zdroj uživatelem

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