Trie ( Delete ) Advantages & Disadvantages
After learning how to insert and search in Trie, let us see how we delete in Tries.
There are 4 possible cases while deleting a key from the Trie.
1. Key may not be present in the Trie. Then, delete operation should not modify trie.
2. If the key doesn’t contains another key ( no part of key containing another prefix ) .Then, we delete all the nodes.
3. If key is prefix key of another long key in trie. Then we make the end of node as 0.
4. If key has atleast one other prefix key. Then, we delete nodes from end of key until first leaf node of longest prefix key.
Let us see the delete operation of Trie with an example :
- Let us call delete operation on string “am”
- Then it searches for the string “am” and at the letter “m” it checks whether it is end of word or not. If it is end of word and it doesn’t contain another key. We delete all the nodes.
- When we call search operation on string “am” . It returns false.
- Let us call delete operation on string “bed”
- Then it searches for the string “bed” and at the letter “e” we cannot move further hence we do not find the key that matches the string “bed”. Hence, we do not modify our Trie.
Output :
0
1
0
1
0
Advantages of Tries:
· We can find insert and find the string in O(length_of_string) time
· Searching of prefix words is very efficient.
· We can print the words in alphabetically order.
Disadvantages of Tries :
· If we choose space as our primary concern, Tries need a lot of space for storing strings in our memory.
Note : Try solving these problems for making your newly learned concept concrete:
Happy Coding 😊
By Programmers Army
Contributed by: Ravi Teja Chidurala