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í na více následující prvky, ktery na prvky, které jsou za prvky bezprostředně následujícími. Tyto ukazatele "přeskakují" položky seznamu, odtud skiplist Graf obsahující strom (lineární strom) a dopředné hrany, které "zkracují" cestu od kořene k prvku, případně od prvku k prvku
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):
- vidíme nejjednoduší skiplist se skokem 1, tedy lineární (a spojový) seznam
- skiplist se skokem 2. Každý druhý prvek obsahzje 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 4 skoky (> 6, >9, >17, >21) na rozdíl od seznamu, kde jich je 9
- skiplist se skokem 4. na prvek 25 se dostaneme pouze 2ma skoky
- 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
- 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).
