### Trie Data Structure – Introduction

Data structure for Strings:-

If we have a set of Strings (all words in a dictionary) , and we want to search for a particular word in that set , so to perform searching faster, we need a efficient way to store set of strings.

There are 3 Data Structures to store Strings:-

1:- Hashing

2:- Binary search tress

3:- Trie

**Hashing for Strings:-** Hashing use hash tables for storing strings or integers. A hash function is applied on the strings for storing it in a particular index.

The problem with the hash table implementation is that it takes a lot of time for searching as we loses the ordering information. Also , the hash function takes the complete string and place it somewhere in the table.

**Binary Search Tress for Strings:-**

In Binary search tress , every strings is stored as a node in the alphabetically order.

As strings are already stored in the sorted order, it is easy to find the word rather than searching the whole tree for a particular word.

Example :- This is a coding website

The problem with this method is that the search operation performs the complete match of the given key with the data of node and hence increasing the time complexity of the operation. This method is good in terms of storage.

**Trie Data Structure for strings:-**

Trie is an efficient and useful data Structure that is based on the prefix of a string. It is an Re**Trie**val Data structure which reduces the complexities to optimal.

Strings are generally stored in Top to bottom manner. Structure of the trie node looks like :-

Struct Tnode { struct Tnode *child[ALPHABET_SIZE]; bool ENDWORD; };

For example , if we want to store the strings formed by the English Alphabet characters ‘a’ to ‘z’ , then each node of the trie contains 26 pointers , pointing to the next children nodes.

Suppose we want to store ‘a’, ‘all’, ‘as’ , the trie tree will look like

**Click here for c++ implementation of trie data structure**

CommentsNo comment yet.