[Solved] To which data structure are skip lists similar to in terms of time complexities in worst and best cases?

To which data structure 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

Answer: a
Explanation: 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.

Comments