Skip-list - použití a implementace
Skiplist je alternativa ke stromům, která je snadno implementovatelná. Operace se skiplistem jsou podobné složitosti jako u stromů (O(n log n)), ale paměťová náročnost může být o něco větší.
Skiplist si lze představit následovně: seznam, ve kterém některé prvky ukazují i na vzdálenější prvky než jsou prvky bezprostředně následující. Tyto ukazatele "přeskakují" položky seznamu, odtud skiplist.
Maximální výška uzlu = Maxlevel, každý prvek může mít 1 <= k <= Maxlevel ukazatelů na další prvky
Popisky (obrázek je z přednášky):
- a) vidíme nejjednoduší skiplist se skokem 1, tedy lineární spojový seznam
- b) skiplist se skokem 2. Každý druhý prvek obsahuje kromě hodnoty a ukazatele na následníka také ukazatel na následovníka následovníka (next[next[x]]). Už touto změnou zkrátíme vyhledávání na polovinu, jelikož abychom se dostali na prvek např. 25, stačí nám pouze 5 skoků (> 6, >9, >17, >21, >25) na rozdíl od seznamu, kde jich je 9
- c) skiplist se skokem 4. na prvek 25 se dostaneme pouze 2 skoky
- d) skiplist se skokem 8. na prvek se dostaneme 1 skokem => ideální skip-list: každý 2i-tý prvek má ukazatel, který ukazuje o 2i prvků dopředu
- e) skiplist s náhodným skokem - ?? skoků, ale ve velkém skiplistu je rychlejší, než lineární seznam, a operace přidání a odebírání jsou jednodušší
Výhody:
- Skiplist je extrémně rychlý (vyhledávání je log n)
- Velmi snadná implementace (pouze pole ukazatelů v každém prvku)
Nevýhody:
- Pomalé operace insert a delete (je nutné reorganizovat skiplist)
Řešení: skiplist s náhodnými velikostmi uzlů. Potom:
- Vložení - najdeme místo, kam prvek patří, pomatujeme si všechny předchůdce. Po nalezení vložíme prvek s náhodnou výškou 1 < k < Maxlevel, a napojíme všechny předchůdce do výšky tohoto prvku (samozřejmě na obě strany, předchůdci ukazují na tento prvek, a ten ukazuje na prvky, na které předchůdci ukazovali původně)
- Mazání - opačný proces, najdeme prvek a pomatujeme si předchůdce. Pro všechny předchůdce do výšky hledaného prvku upravíme ukazatele (předchůdci budou ukazovat na prvky, na které ukazoval hledaný prvek). Hledaný prvek smažeme.
Tento skip-list není zcela log n, a nelze (díky náhodnosti) jeho složitost určit. S vysokou pravděpodobností však všechny operace budou rychlejší než O(n) (samozřejmě můžeme mít smůlu a všechny prvky budou náhodně výšky 1).