Trie is a data structure used to present a dynamic set which contains data (usually this data is strings). We can think of Trie as a dictionary which supports the following operations:
- Insert a word (data) into dictionary
- Search for an existing word in the dictionary
- Delete a word from the dictionary
The most important properties of Trie are:
- Each operation above (insert, search, delete) has a time complexity of O(L), where L is the length of the word.
- Memory complexity of trie is O(TOTAL_LENGTH), where TOTAL_LENGTH is the sum of the lengths of the individual words.
Implementation (memory allocation) note:
Most people implement trie by dynamic allocation of memory, which requires you to have a background about pointers in programming languages. However, this is not necessary as tries can also be implemented using static pre-allocated memory.
After finishing videos you can refer to :
Video tutorials:
This video is provided by CS50 channel (CS50 is a course taught in Harvard University, one of the most famous courses in Computer Science).
Here is a nice video also with more detailed simulation.
However, if you prefer text tutorials, here's a nice one from TopCoder: Using Tries – topcoder