Trie – An efficient way to search data

15 April, 2011

Trie – An efficient way to search data

Trie is an information retrieval data structure efficiently extracts required data. For example, see the following,

1. When we type a name on smart phones it displays all the contacts containing the typed-in string. What data structure will fill such needs?
2. In advanced editors like Visual Studio, Qt Creator, etc… when we type the identifier name, it automatically displays all the members part of that object. How is it possible?
3. On Linux (even on emulated DOS in Windows), if we type characters “gcc” + TAB key, it displays all the commands with “gcc” as prefix. What data structures is appropriate here?

All the above cases use a kind of trie data structure. Perhaps, the practical implementation may vary based on kind of application.
There is a demand for tries on Geeksforgeeks. We will be posting few articles on these in coming weeks.