Skip Lists Flashcards
1
Q
what is a skip list
A
a probabilistic data structure arranged horizontally into levels and vertically into towers.
2
Q
what does each node contain
A
key value pair and pointers to other nodes
3
Q
give the ADT of a skip list
A
after(p) - on same level
before(p) - on same level
above(p) - on same tower
below(p) - on same tower
4
Q
what do nodes above/below share
A
the same key value pair
5
Q
how are towers usually stored
A
using a separated data structure
6
Q
how do you search
A
zig zag down and right.
move sideways when the next key is bigger than k, down otherwise
7
Q
how do you insert
A
create a new node after search(k)
use coin flip to determine how many levels to go up.
