Now, let's focus on the algorithm for inserting words in a Trie:
- Consider the current node as the root.
- Loop the given word character by character, starting from the first character.
- If the current node (the Map<Character, Node>) maps a value (a Node) for the current character, then simply advance to this node. Otherwise, create a new Node, set its character equal to the current character, and advance to this node.
- Repeat from step 2 (pass to next character) until the end of the word.
- Mark the current node as a node that completes the word.
In terms of code lines, we have the following:
public void insert(String word) {
Node node = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
Function function = k -> new Node();
node = node.getChildren().computeIfAbsent(ch, function);
}
node.setWord(true);
}
The complexity of insertion is O(n), where n represents the word size.