Trie
============
A trie is a rooted tree used to store multiple words.
Each word is represented as a chain of letters starting from the root.
If two words share a common prefix, they will have the same chain in the tree.
Suppose the number of distinct letters used in the words is \(X\).
In this case, each node has at most \(X\) children.
Note that the nodes themselves do not contain letters; instead, the edge between each pair of nodes is labeled with a letter. For better understanding, refer to the figure below.
.. figure:: /_static/dot/Trie.svg
:width: 50%
:align: center
:alt: Trie example
Each node can also have a marker. If a node is marked, it signifies that a word ends at that node, and the path from the root to this node represents that word.
If duplicate words might exist in the collection, instead of a marker, a number can be used to keep track of the count of words ending at each node.
Search (Search)¶
You can check in \(O(n)\) whether a word of length n exists in the trie.
Starting from the root, you move letter by letter through the word. If you are at a node u and the next letter in the word is X, check if node u has an edge labeled X leading to a child v. If such an edge exists, move to node v and proceed to the next letter. If node u has no edge labeled X, the word does not exist in the trie. Continue this process until the word ends (no more letters remain). Suppose the word ends at node w. If node w is marked (or has a natural number value), the word exists; otherwise, it does not.
Insertion (Insertion)¶
You can insert a word of length n into the trie in \(O(n)\) time.
Starting from the root, traverse letter by letter. If you are at node u and the next letter is X: - If node u has an edge labeled X to a child v, move to v and proceed to the next letter. - If the word ends at the current node, mark it (or increment its numerical value by 1). - If no edge labeled X exists, create a new node, connect node u to this new node with an edge labeled X, move to the new node, and proceed to the next letter.
Repeat this process until the word is fully processed.
Applications¶
Used in some autocomplete systems.
Widely used for storage and fast access to dictionary strings.
Can be used as a replacement for hash tables in certain scenarios.
Tries enable linear-time data sorting. For example, inserting a set of strings into a trie and printing its pre-order traversal will output the strings in lexicographical order. Similarly, when building a trie with numbers, the first-level search traverses the numbers in sorted order.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
