Question

Skip lists are similar to which of the following datastructure?

(a) stack

(b) heap

(c) binary search tree

(d) balanced binary search tree

Answer 1

The correct choice is (d) balanced binary search tree

The explanation is: Skip lists have the same asymptotic time complexity as balanced binary search tree. For a Balanced Binary Search Tree, we skip almost half of the nodes after one comparison with root element. The same thing done in the skip lists. Hence skip lists are similar to balanced Binary search trees.