Trie facts for kids

A trie (pronounced "try") is a special kind of tree (data structure) used in computer science. It's like a super-organized way to store a list of words or phrases, also known as a set. The cool thing about a trie is that it stores common starting parts (called prefixes) of words only once. This makes it very efficient for finding and storing information, especially when you have many words that begin with the same letters.

A trie containing "Java", "Rad", "Rand", "Rau", "Raum", and "Rose".

What is a Trie?

A trie is sometimes called a "prefix tree" because of how it stores words based on their prefixes. Each node (a point in the tree) in a trie represents a single character or part of a word. When you follow the path from the very top (the root) of the trie down to another node, you are spelling out a word or a part of a word.

How Does a Trie Work?

Imagine you want to store words like "cat", "car", and "dog".

• The trie starts with an empty root node.
• To add "cat":

* From the root, you go to a node for 'c'. * From 'c', you go to a node for 'a'. * From 'a', you go to a node for 't'. * The node for 't' is marked as the end of a word.

• To add "car":

* You already have 'c' and 'a' nodes. * From the 'a' node, you go to a new node for 'r'. * The node for 'r' is marked as the end of a word.

• To add "dog":

* From the root, you go to a new node for 'd'. * From 'd', you go to a new node for 'o'. * From 'o', you go to a new node for 'g'. * The node for 'g' is marked as the end of a word.

Notice how "cat" and "car" share the 'c' and 'a' nodes. This saves space!

Building a Trie

Building a trie involves adding words one by one. For each word, you start at the root. You then follow the path of characters. If a character's node doesn't exist, you create it. Once you reach the last character of the word, you mark that node to show that a complete word ends there.

Searching in a Trie

Searching for a word in a trie is very fast. You just follow the path of characters from the root. If you reach the end of your word and the last node is marked as a word end, then the word exists in the trie. If you can't find a character's node along the path, or if the last node isn't marked as a word end, then the word is not in the trie.

Why Are Tries Useful?

Tries are super useful because they are very efficient for certain tasks.

• Fast Searching: Finding a word in a trie is usually quicker than searching in a regular list or even some other types of trees. The time it takes depends on the length of the word, not the total number of words in the trie.
• Space Saving: By sharing common prefixes, tries can save a lot of memory, especially when storing many words that are similar.
• Prefix Matching: Tries are perfect for finding all words that start with a certain prefix. For example, if you type "app" into a search bar, a trie can quickly suggest "apple", "application", "apply", etc.

Where Are Tries Used?

Tries are used in many real-world applications that you might use every day:

• Autocompletion: When you start typing a word in a search engine or on your phone, and it suggests words to finish what you're typing, that's often powered by a trie.
• Spell Checkers: Tries can quickly check if a word is spelled correctly by seeing if it exists in the dictionary stored in the trie.
• Dictionaries and Thesauruses: They help organize and quickly look up words.
• IP Routing: In computer networks, tries can be used to quickly find the correct path for data packets based on their IP addresses.
• Predictive Text: On your smartphone keyboard, tries help predict the next word you're likely to type.

See also

In Spanish: Trie para niños