Which of the following is the efficient data structure for searching words in dictionaries?

Category: QuestionsWhich of the following is the efficient data structure for searching words in dictionaries?
Editor">Editor Staff asked 1 month ago

Which of the following is the efficient data structure for searching words in dictionaries?
 
(a) BST
 
(b) Linked List
 
(c) Balancded BST
 
(d) Trie
 
My question comes from Trie in chapter Trie of Data Structures & Algorithms I
 
This question was addressed to me in semester exam.

1 Answers
Editor">Editor Staff answered 1 month ago

Correct choice is (d) Trie
 
Easiest explanation – In a BST, as well as in a balanced BST searching takes time in order of mlogn, where m is the maximum string length and n is the number of strings in tree. But searching in trie will take O(m) time to search the key.