Lista z przeskokami

Ten artykuł wymaga uzupełnienia informacji. Artykuł należy uzupełnić o istotne informacje: dodać algorytm wyszukiwania, wstawiania, usuwania, sposób losowania stopnia. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Lista z przeskokami (ang. skip list) – probabilistyczna struktura danych przeznaczona do przechowywania danych uporządkowanych (np. posortowanych rosnąco liczb), będąca rozwinięciem listy jednokierunkowej, a stanowiąca alternatywę dla drzew zbalansowanych (wyważonych), takich jak drzewa AVL czy czerwono-czarne.

Została opracowana przez Williama Pugha w 1989 roku. Oczekiwana złożoność operacji wyszukiwania, wstawiania nowego elementu do listy oraz usunięcia elementu wynosi ${\displaystyle O(\log n).}$

W zwykłej liście każdy element posiada połączenie (ze względu na prostotę implementacji najczęściej realizowane poprzez wskaźnik) wyłącznie do elementu następnego. W liście z przeskokami takich połączeń jest więcej: oprócz bezpośredniego następnika, wskazują także elementy znajdujące się dalej. Liczba połączeń powiązana z elementem określa jego stopień (ang. degree, lub wysokość [height]), przy czym ${\displaystyle i}$-te połączenie wskazuje na kolejny element stopnia co najmniej ${\displaystyle i.}$ Stopnie węzłów są wybierane losowo, ale z rozkładem geometrycznym (prawdopodobieństwa dane wzorem ${\displaystyle p^{i}(1-p),}$ gdzie ${\displaystyle p\leqslant 1/2}$); np. dla ${\displaystyle p=1/2}$ liczba elementów stopnia 1 powinna stanowić 50% całości, stopnia 2 – 25%, stopnia 3 – 12% itd.

Dzięki temu rozwiązaniu można szybciej przechodzić całą listę, a ponadto dzięki informacji o jej uporządkowaniu pomijać („przeskakiwać”) nieistotne fragmenty listy.

Zobacz też

• lista
• struktura danych

Literatura dodatkowa

• William Pugh, A Skip List Cookbook, 1989.
• William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM 33, 1990.