Lista z przeskokami: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
Literówka w nazwisku autora |
m dm |
||
Linia 1:
{{dopracować|dodać algorytm wyszukiwania, wstawiania, usuwania, sposób losowania stopnia}}
'''Lista z przeskokami''' (ang. ''skip list'') – w [[informatyka|informatyce]] probabilistyczna [[struktura danych]] przeznaczona do przechowywania danych uporządkowanych (np. posortowanych rosnąco liczb), będąca rozwinięciem [[lista|listy jednokierunkowej]], a stanowiąca alternatywę dla drzew zbalansowanych (wyważonych), takich jak [[drzewo AVL|drzewa AVL]], czy [[drzewo czerwono-czarne|czerwono-czarne]].
Została opracowana przez Williama Pugha w [[1989]] roku. Oczekiwana [[złożoność obliczeniowa|złożoność]] operacji wyszukiwania, wstawiania nowego elementu do listy oraz usunięcia elementu wynosi <math>O(\log n)</math>.
| |||