Skip Lists (Q7361761)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry Skip_Lists
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Skip Lists |
AFP entry Skip_Lists |
Statements
9 January 2020
0 references
Max W. Haslbeck
0 references
Manuel Eberl
0 references
Skip Lists (English)
0 references
Skip lists are sorted linked lists enhanced with shortcuts and are an alternative to binary search trees. A skip lists consists of multiple levels of sorted linked lists where a list on level n is a subsequence of the list on level n − 1. In the ideal case, elements are skipped in such a way that a lookup in a skip lists takes O(log n) time. In a randomised skip list the skipped elements are choosen randomly. This entry contains formalized proofs of the textbook results about the expected height and the expected length of a search path in a randomised skip list.
0 references
