Introduction to Trie

Now, let's look at the basic operations such as insertion, searching, and deletion on the Trie data structure.

Insertion in Trie Data Structure

Insertion in a Trie involves adding a string to the Trie, character by character, starting from the root. If the character already exists in the Trie, we move to the next node; otherwise, we create a new node for the character.

Algorithm

1. Start from the root node.
2. For each character in the string:
   • Check if the character exists in the current node's children.
   • If it exists, move to the corresponding child node.
   • If it doesn't exist, create a new node for the character and link it to the current node.
   • Move to the newly created node.
3. After processing all characters in the string, mark the current node as the end of the word.

Example

Consider that we need to insert the 'can', 'cat', 'cant', and 'apple' into the trie. We insert them in the following order:

1. Initial Trie:

Root

2. Insert 'can':

Root
 |
 c
 |
 a
 |
 n

Explanation: Starting from the root, we add nodes for each character in "can".

3. Insert 'cat':

Root
 |
 c
 |
 a
 | \
 n   t

Explanation: "cat" shares the first two characters with "can", so we just add a new branch for the 't' after 'a'.

4. Insert 'cant':

Root
 |
 c
 |
 a
 | \
 n   t
 |
 t

Explanation: "cant" extends from the path of "can", so we add a new node for 't' after the existing 'n'.

5. Insert 'apple':

   Root
  /   \
 c     a
 |     |
 a     p
 | \   |
 n  t  p
 |     |
 t     l
       |
       e

Explanation: Starting from the root, we add nodes for each character in "apple" branching from the 'a' node.

Code

Complexity Analysis

Time Complexity: O(n) - Where n is the length of the word. This is when the word doesn't share any prefix with the words already in the Trie or is longer than any word in the Trie.

Space Complexity:

• Best Case: O(1) - When the word is entirely a prefix of an existing word or shares a complete prefix with words in the Trie.
• Worst Case: O(n) - When the word doesn't share any characters with the words in the Trie.

Searching in Trie Data Structure

Searching into Trie is similar to the insertion into the Trie. Let's look at the below algorithm to search in the Trie data structure.

Algorithm

1. Start from the root node.
2. For each character in the word:
   • a. Calculate its index (e.g., 'a' is 0, 'b' is 1, ...).
   • b. Check if the corresponding child node exists.
   • c. If it exists, move to the child node and continue.
   • d. If it doesn't exist, return false (word not found).
3. After processing all characters, check the isEnd flag of the current node. If it's true, the word exists in the Trie; otherwise, it doesn't.

Code

Complexity Analysis

Time Complexity: O(n) - Where n is the length of the word. This happens when you have to traverse the Trie to the deepest level.

Space Complexity: O(1) - Searching doesn't require any additional space as it's just about traversing the Trie.

Deletion in Trie Data Structure

When we delete a key in a Trie, there are three cases to consider:

1. Key is a leaf node: If the key is a leaf node, we can simply remove it from the Trie.
2. Key is a prefix of another key: If the key is a prefix of another key in the Trie, then we cannot remove it entirely. Instead, we just unmark the isEnd flag.
3. Key contains another key as a prefix: If the key being deleted extends beyond other words in the Trie, we delete its nodes from the bottom up, stopping at the first node that either has other children or marks the end of another word.

Step-by-Step Algorithm

1. Initialization:

   • Start at the root of the Trie.
   • Begin processing the word you want to delete, starting from its first character.
   • Keep track of the current depth in the word.

2. Base Case:

   • If you've reached the end of the word (i.e., depth == word.length()):
     • Check the isEnd flag:
       • If the flag is not set, the word is not present in the Trie. Return the current node without changes.
       • If the flag is set, unset it. This marks the word as no longer valid in the Trie.
     • Check if the node has any children:
       • If it has no children, delete the node (set it to null) and return null to its parent, indicating that it can be removed.
       • If it has children, return the node, as it is part of other words.

3. Recursive Case:

   • For the current character of the word:
     • Compute its corresponding index in the children array (e.g., 'a' is 0, 'b' is 1, etc.).
     • Make a recursive call to the deleteKey function for the child node with the next character in the word.

4. Post-Recursive Handling:

   • After returning from the recursive call:
     • If the child node for the current character was deleted (i.e., set to null), update the children array of the current node to remove the reference to the child.
     • Check if the current node can also be deleted:
       • If the current node has no children (isEmpty() returns true) and is not marked as the end of another word (isEnd is false), delete it (set it to null) and return null to the parent.
       • Otherwise, return the current node.

5. Completion:

   • Once all characters of the word are processed, the word will be deleted if it exists, and the Trie structure will be updated accordingly.
   • If the word does not exist in the Trie, no changes will be made.

Example

Start from the trie built above, holding 'can', 'cat', 'cant' and 'apple'. A star marks a node where isEnd is true, so the path down to it spells a word.

   Root
  /   \
 c     a
 |     |
 a     p
 | \   |
 n* t* p
 |     |
 t*    l
       |
       e*

1. Delete 'can'. This is the second case, where the key is a prefix of another key.

Walk c, a, n and unset isEnd on that 'n'. The node itself has to stay, because its child 't' still leads to 'cant'. Nothing is removed, and only one flag changes.

   Root
  /   \
 c     a
 |     |
 a     p
 | \   |
 n  t* p
 |     |
 t*    l
       |
       e*

2. Delete 'cant'. This is the third case, where the key extends past other words.

Walk to the last 't' and unset its isEnd. It has no children, so it is removed and the call returns null to its parent. Back at 'n', that child reference is cleared, and 'n' now has no children and no longer marks the end of a word, so it is removed too. Back at 'a', the removal stops, because 'a' still has the child 't' for 'cat'.

   Root
  /   \
 c     a
 |     |
 a     p
  \    |
   t*  p
       |
       l
       |
       e*

3. Delete 'apple'. This is the first case, where nothing on the path is shared.

Unset isEnd on 'e' and remove it, then 'l', then 'p', then 'p', then the 'a' below the root. Each one is removed as the recursion returns, because each is left with no children and no isEnd.

   Root
   |
   c
   |
   a
    \
     t*

One point is worth repeating, because it is where most implementations go wrong. A node is removed only when both conditions hold at once: no children, and isEnd false. Checking only one of them either deletes nodes that other words still need, or leaves dead nodes behind.

Code

Complexity Analysis

Time Complexity: O(n) - Where n is the length of the word. This is when you have to traverse the Trie to the deepest level and potentially backtrack to delete nodes.

Space Complexity: The space complexity of the delete function in the Trie is O(n), where (n) is the length of the word. This is due to the recursion stack used during the deletion process.

Advantages of Using Tries

• Fast Pattern Matching: Tries provide rapid pattern matching queries, taking time proportional to the length of the pattern (or the string being searched).
• Common Prefix Sharing: Strings with common prefixes share nodes in the Trie, leading to efficient memory utilization and reduced redundancy.
• Efficient Insertion and Deletion: Tries are amenable to dynamic operations like insertion and deletion, while maintaining efficient search times. Alphabet Flexibility: Tries can handle various alphabets, making them versatile for a range of applications.
• Word Frequency Counting: Tries can be extended to store additional information at nodes, such as the frequency of words or strings.

In comparison to using a binary search tree, where a well-balanced tree would require time proportional to the product of the maximum string length and the logarithm of the number of keys, Tries offer the advantage of a search time linearly dependent on the length of the string being searched. This results in an optimization of search operations, especially when dealing with large datasets.

In summary, a Trie is a powerful data structure that optimizes string-related operations by efficiently storing and retrieving strings with shared prefixes. Its unique structure and fast search capabilities make it an invaluable tool in various text-based applications.

Now, let's start solving the problems on Trie Data Structure.