Question

Which of the following data structure can provide efficient searching of the elements?

(a) unordered lists

(b) binary search tree

(c) treap

(d) 2-3 tree

Question is from B-Trees in chapter B-Trees of Data Structures & Algorithms I

The question was posed to me in final exam.

Answer 1

The correct choice is (d) 2-3 tree

Easiest explanation - The average case time for lookup in a binary search tree, treap and 2-3 tree is O(log n) and in unordered lists it is O(n). But in the worst case, only the 2-3 trees perform lookup efficiently as it takes O(log n), while others take O(n).