1. What is a Trie Tree?¶
A Trie Tree, also known as a Prefix Tree or Dictionary Tree, is a data structure specifically designed to handle string prefix problems. Imagine needing to quickly look up words in a dictionary, or perform auto-completion or spell checking—using a Trie Tree is more efficient than arrays or hash tables. Its core idea is: “Save space by leveraging common prefixes of strings, making lookups faster”. For example, storing “apple” and “app” reuses the first three characters of “apple” for “app”, avoiding redundant storage.
2. What does a Trie Tree node look like?¶
Each node represents a character and mainly contains three parts:
- Character: The letter stored in the current node (e.g., ‘a’, ‘p’).
- Children: Up to 26 child nodes (assuming lowercase letters, each child corresponds to one letter).
- isEnd flag: A boolean indicating whether the current node marks the end of a word (e.g., the third ‘p’ node in “app” is marked isEnd=true).
3. How to “insert” a word into the Trie Tree?¶
Taking the insertion of “apple” as an example:
1. Start from the root node: The root has no character and is the starting point for all words.
2. Process each character one by one:
- First character ‘a’: No ‘a’ child exists in the root node. Create a new ‘a’ node and move the pointer to it.
- Second character ‘p’: No ‘p’ child exists in the ‘a’ node. Create a new ‘p’ node and move the pointer.
- Third character ‘p’: No ‘p’ child exists in the current ‘p’ node. Create a new ‘p’ node and move the pointer.
- Fourth character ‘l’: No ‘l’ child exists in the current ‘p’ node. Create a new ‘l’ node and move the pointer.
- Fifth character ‘e’: No ‘e’ child exists in the current ‘l’ node. Create a new ‘e’ node and move the pointer.
3. Mark the end: Set the isEnd of the ‘e’ node to true to indicate the end of “apple”.
4. How to “search” for a word in the Trie Tree?¶
Taking the search for “apple” as an example:
1. Start from the root node and match characters one by one:
- First character ‘a’: The root has an ‘a’ child. Move the pointer to ‘a’.
- Second character ‘p’: The ‘a’ node has a ‘p’ child. Move the pointer.
- Third character ‘p’: The current ‘p’ node has a ‘p’ child. Move the pointer.
- Fourth character ‘l’: The current ‘p’ node has an ‘l’ child. Move the pointer.
- Fifth character ‘e’: The current ‘l’ node has an ‘e’ child. Move the pointer.
2. Check the end flag: After processing all characters, confirm that isEnd is true. If yes, the word exists; if not (e.g., it’s just a prefix), the word does not exist.
5. Practical Example: Storage and Search¶
Suppose we store 4 words: app, apple, banana, bat.
Insertion Process:¶
- Insert “app”:
Root → a → p → p (setisEnd=truefor the last ‘p’ node). - Insert “apple”:
Root → a → p → p → l → e (setisEnd=truefor the last ‘e’ node). - Insert “banana”:
Root → b → a → n → a → n → a (setisEnd=truefor the last ‘a’ node). - Insert “bat”:
Root → b → a → t (setisEnd=truefor the last ‘t’ node).
Search Process (Verification):¶
- Search “app”:
Root → a → p → p. CheckisEnd=trueat the last ‘p’ node → exists. - Search “apple”:
Root → a → p → p → l → e. CheckisEnd=trueat the last ‘e’ node → exists. - Search “banana”:
Root → b → a → n → a → n → a. CheckisEnd=trueat the last ‘a’ node → exists. - Search “bat”:
Root → b → a → t. CheckisEnd=trueat the last ‘t’ node → exists. - Search “ball”:
Root → b → a →? The ‘a’ node has children ‘n’ (banana) and ‘t’ (bat), but no ‘l’ → does not exist.
6. Why Use a Trie Tree?¶
- More space-efficient: If multiple words share prefixes (e.g., “app” and “apple”), the Trie Tree stores the common part (“app”) only once, saving redundant space.
- Faster lookups: The time complexity for lookup is O(n) (n = word length), which is more efficient than array lookups (also O(n) in the worst case). Additionally, Trie Trees natively support prefix queries (e.g., finding all words starting with “app”).
Through the examples above, you’ll see the Trie Tree’s core is “shared prefixes” and “end markers”. Once you master insertion and lookup logic, you’ll easily understand its applications in dictionaries, search engines, spell checkers, and other scenarios!