Insertion in a Trie
Explore the method of inserting words into a Trie data structure, including handling cases with no common prefix, shared prefixes, and existing words. Understand the process of setting end-of-word markers and the time complexity of the insertion operation, to build efficient string storage and retrieval systems in Java.
We'll cover the following...
Inserting a word in Trie
Insertion is simple for individual characters in the trie. If the character is already present, we follow the path; if that character is not present, then we insert the corresponding nodes. While inserting the last node, we must also set the value of isEndWord() to true.
Case 1: What if the word has no common subsequence? i.e. No Common Prefix
For example, if we want to insert a new word into the trie below, e.g. “any”, then we need to insert all of the characters for the word “any”; currently, “the” is the only word in the trie, and there are no common character subsequences between “any” and “the”.
Case 2: If the word has a common subsequence? i.e. Common Prefix Found
For example, if we want to insert the word “there” into the trie below-- which already consists of the word “ their”–then the path to “ the” already exists. After that, we need to insert two ...