ARTP - 10 - Pravdepodobnostné dátové štruktúry

Zhrnutie prednášky

Prednáška sa venuje pravdepodobnostným dátovým štruktúram skip list a treap (v prepise skomolene „trip“) ako implementáciám asociatívneho poľa. Úvodom porovnáva hašovacie tabuľky, ktoré pri náhodnej hašovacej funkcii dosahujú očakávaný konštantný čas, s binárnymi vyhľadávacími stromami, ktoré umožňujú aj usporiadaný výpis či hľadanie najbližšieho kľúča. Skip list kombinuje výhody utriedeného poľa (rýchle vyhľadávanie) a spájaného zoznamu (rýchle vkladanie): ide o viacúrovňový spájaný zoznam so skratkami a zarážkou (sentinel) s kľúčom mínus nekonečno. Vyhľadávanie začína v zarážke na najvyššej úrovni a posúva sa doprava alebo nadol, pričom pomocná funkcia nájde predchodcu hľadanej hodnoty a na nej stavajú operácie find aj add. Obe štruktúry dosahujú logaritmický očakávaný čas operácií find, add a remove a sú jednoduchšie na implementáciu než vyvažované stromy typu AVL.

• - Hašovacie tabuľky s náhodnou hašovacou funkciou majú očakávaný konštantný čas operácií find, add a remove.
• - Binárne vyhľadávacie stromy podporujú usporiadaný výpis, hľadanie najbližšieho kľúča a k-ty najmenší prvok.
• - Utriedené pole má rýchle vyhľadávanie, ale lineárne vkladanie; spájaný zoznam má rýchle vkladanie, ale lineárne vyhľadávanie.
• - Skip list je viacúrovňový spájaný zoznam, kde každý uzol má pole smerníkov rôznej dĺžky a zarážka (sentinel) má najvyššiu výšku.
• - Vyhľadávanie v skip liste hľadá predchodcu hodnoty x: ide doprava, ak sa dá, inak nadol, až kým nedosiahne úroveň 0.
• - Operácie find a add využívajú nájdenie predchodcu; nový uzol sa vloží za predchodcu a jeho výška sa určí náhodne.
• - Skip list aj treap dosahujú očakávaný logaritmický čas operácií, nie najhorší, ale sú jednoduché a v praxi rýchle.

Zhrnutie pripravené s pomocou AI z prepisu videa.