+1 vote
in Data Structures & Algorithms I by (110k points)
Skip lists are similar to which of the following datastructure?

(a) stack

(b) heap

(c) binary search tree

(d) balanced binary search tree

Origin of the question is Skip List topic in portion Types of Lists of Data Structures & Algorithms I

This question was posed to me in a job interview.

1 Answer

+1 vote
by (444k points)
selected by
Best answer
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.

Related questions

Welcome to TalkJarvis QnA, a question-answer community website for the people by the people. On TalkJarvis QnA you can ask your doubts, curiosity, questions and whatever going in your mind either related to studies or others. Experts and people from different fields will answer.