+1 vote
in Data Structures & Algorithms I by (110k points)
To which datastructure are skip lists similar to in terms of time complexities in worst and best cases?

(a) balanced binary search trees

(b) binary search trees

(c) binary trees

(d) linked lists

The doubt is from Skip List in chapter Types of Lists of Data Structures & Algorithms I

This question was posed to me during a job interview.

1 Answer

+1 vote
by (408k points)
selected by
Best answer
Correct answer is (a) balanced binary search trees

The explanation is: Skip lists are similar to any randomly built binary search tree. a BST is balanced because to avoid skew tree formations in case of sequential input and hence achieve O(logn) in all 3 cases. now skip lists can gurantee that O(logn) complexity for any input.

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.