Skiplists Flashcards
What interfaces can Skiplists implement?
SSet
List
What is the runtime of the add(x) method for a SkiplistSSet?
O(log n) expected time
What is the runtime of the remove(x) method for a SkiplistSSet?
O(log n) expected time
What is the runtime of the find(x) method for a SkiplistSSet?
O(log n) expected time
How much extra space does a SkiplistSSet require to store n elements?
O(n) extra space in expectation.
What is the search path for element x in a Skiplist?
It is the path constructed from the top left sentinel node to the node x in L0 that is constructed by moving right while you don’t overshoot x, and moving down otherwise, until you get to (the predecessor of) x in L0.
What is the expected length of a search path in a skiplist?
O(log n) in expectation
What is the backing storage of a skiplist?
A sentinel node
which itself is an array of Node pointers and a spot for data.
What is the runtime of the get(i) method for a SkiplistList?
O(log n) in expectation
What is the runtime of the set(i,x) method for a SkiplistList?
O(log n) in expectation
What is the runtime of the add(i,x) method for a SkiplistList?
O(log n) in expectation
What is the runtime of the remove(i) method for a SkiplistList?
O(log n) in expectation
