Inserting in a Trie

Now, let's focus on the algorithm for inserting words in a Trie:

  1. Consider the current node as the root.
  2. Loop the given word character by character, starting from the first character.
  3. 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.
  4. Repeat from step 2 (pass to next character) until the end of the word.
  5. 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.
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
18.191.147.77