Lista z przeskokami

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Lista z przeskokami (ang. skip list) – w informatyce 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 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 i-te połączenie wskazuje na kolejny element stopnia co najmniej i. Stopnie węzłów są wybierane losowo, ale z rozkładem geometrycznym (prawdopodobieństwa dane wzorem p^i (1-p), gdzie p \le 1/2); np. dla 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.

Przykładowa lista z węzami o maksymalnym stopniu 4

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]

Literatura dodatkowa[edytuj | edytuj kod]

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