Can someone please help me understand the main differences between a simple skiplist and an indexable skiplist? How does an indexable skiplist work in comparison to a normal skiplist (maybe a little example?), I can only find so little about it online. Thanks.
1
-
$\begingroup$ (Please add what contents found here you think should have helped, and how it didn't.) $\endgroup$– greybeardDec 6, 2019 at 4:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
An Indexable Skiplist is a skiplist with the added property that it can quickly lookup the $m$th entry (in order) in a skiplist in $O(\log n)$ time in a skiplist of $n$ entries. In other words, it takes a skiplist that is not an indexable skiplist $O(n)$ time, on average, to find the $m$th element in order in a skiplist, while an ordered skiplist can do this in logarithmic time.
It does this by keeping track of the width of the links in the skiplist.
