loading words...

Apr 24, 2019 23:55:05

FT16 Trie

by @hiro | 236 words | 23🔥 | 256💌

Hiro

Current day streak: 23🔥
Total posts: 256💌
Total words: 70380 (281 pages 📄)

Trie [ˈtriː]  is also called "prefix tree", which is one type of tree structure where each node stores all values in the descendants. In other words, all the descendants of a node have a common prefix. That is why it is called "prefix tree."

For example, let's say we have a tree like below:

 - a - ap - app - appl - apple 

      - ap - app

             - apo - apol - apolo

Note that the root is typically empty. 


As you can see above, this structure can be seen somewhere in daily life. It is in a dictionary. When you are finding a word, you need to follow a trie structure. 


What is good for?

Trie is good for searching. It is very efficient in the worst case scenario where you have bad luck and end up with looking up all nodes while searching.  

As for application, this is useful to predict the next text or autocomplete dictionary where we also usually use when you type a few words and google or keyboard software suggests the next words.  

Limitation

Trie can be slower and would require more memory space than hash tables in some cases. 


Last Saturday, I joined the coding contest and solved the difficult problem but I did not feel like it was the best solution. A friend of mine gave me a hint that maybe we should use a trie, which I did not know yet. This is good to learn. 




From Hiro's collection:

contact: email - twitter / Terms / Privacy