Hi. I implemented a Trie in java using HashMap. the search and insert function works properly. but i have issues with deleting a string from Trie. let’s say i put “bat” and “batman” into Trie, if i delete “bat” and search for batman, my result returns false, which should return true. I can’t find error in my code for delete. Below is my code.
import java.io.;
import java.util.;
public class Trie {
static class TrieNode {
HashMap<Character, TrieNode> map = new HashMap<Character, TrieNode>();
boolean isEnd;
}
// insert String in Trie
static void insert(TrieNode root, String key)
{
TrieNode curr = root;
for (int i=0; i<key.length(); i++) {
char c = key.charAt(i);
if (curr.map.containsKey(c) == false) {
curr.map.put(c, new TrieNode());
}
curr = curr.map.get(c);
}
curr.isEnd = true;
}
// search String in Trie
static boolean search(TrieNode root, String key)
{
if (root == null) {return false;}
TrieNode curr = root;
for (int i=0; i<key.length(); i++) {
char c = key.charAt(i);
if (curr.map.containsKey(c) == false) {
return false;
}
curr = curr.map.get(c);
}
return curr.isEnd;
}
static boolean isEmpty(TrieNode root)
{
return (root.map.size()==0);
}
// delete String from Trie
static TrieNode delete(TrieNode root, String key, int i)
{
if (root == null) {return null;}
if (i == key.length()) {
root.isEnd = false;
if (isEmpty(root) == true) {
root = null;
}
return root;
}
char c = key.charAt(i);
root.map.put(c, delete(root, key, i+1));
if (isEmpty(root) && root.isEnd==false) {
root = null;
}
return root;
}
public static void main(String[] args) {
TrieNode root = new TrieNode();
insert(root, "jigyansu");
insert(root, "jig");
insert(root, "bat");
insert(root, "batman");
System.out.println(search(root, "batman"));
root = delete(root, "bat", 0);
System.out.println(search(root, "batman"));
}
}