A trie (pronounced as "try") or prefix tree is a tree data structure used for storing and searching a specific key from a set, usually a string set.

Using Trie, search complexities can be brought to O(n)(n = key length).

208. Implement Trie (Prefix Tree)

Properties

Below are some important properties of the Trie data structure^{1}:

There is one root node in each Trie.

Each node of a Trie represents a string and each edge represents a character.

Every node consists of hashmaps or an array of pointers, with each index representing a character and a flag to indicate if any string ends at the current node.

Trie data structure can contain any number of characters including alphabets, numbers, and special characters. But for this article, we will discuss strings with characters a-z. Therefore, only 26 pointers need for every node, where the 0th index represents ‘a’ and the 25th index represents ‘z’ characters. 我们仅讨论key为[a-z]的Trie.

Each path from the root to any node represents a word or string.

Data Structure

Every node of Trie consists of multiple branches. Each branch represents a possible character of keys:

Mark the last node of every key as the end of the word node. A Trie node field isEndOfWord is used to distinguish the node as the end of the word node.

1 2 3 4 5 6 7 8 9 10 11 12

publicstaticclassTrieNode{ public TrieNode[] children; boolean isEndOfWord; // isEndOfWord is true if the node represents end of a word

// If not present, inserts key into trie. // If the key is prefix of trie node, just marks leaf node. publicvoidinsert(String word) { __insert(word, root); }

privatevoid__insert(String word, TrieNode currentRoot) { if(word.length() == 0) return;

intidx= word.charAt(0) - 'a';

if(currentRoot.children[idx] == null) currentRoot.children[idx] = newTrieNode(); if(word.length() == 1) currentRoot.children[idx].isEndOfWord = true;// mark last node as leaf

// Returns true if key presents in trie, else false privateboolean__search(String word, TrieNode currentRoot) { if(word.length() == 0)//If input is a null string, we just return false. returnfalse;