I have a code from a trie tree that has insert and search methods, but does not contain a method of removal. I tried to implement but I did not succeed. I would like someone to give you a hint on how to implement it. Using this same code below is it possible to create a function that returns a word from the tree?
public class Trie {
class TrieNode {
char c;
HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
boolean isLeaf;
public TrieNode() {
}
public TrieNode(char c) {
this.c = c;
}
}
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Insere uma palavra na Trie tree.
public void insert(String word) {
HashMap<Character, TrieNode> children = root.children;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
TrieNode t;
if (children.containsKey(c)) {
t = children.get(c);
} else {
t = new TrieNode(c);
children.put(c, t);
}
children = t.children;
//set leaf node
if (i == word.length() - 1) {
t.isLeaf = true;
}
}
}
// Retorna se a palavra estiver na trie tree.
public boolean search(String word) {
TrieNode t = searchNode(word);
if (t != null && t.isLeaf) {
return true;
} else {
return false;
}
}
// Retorna se há alguma palavra na trie
// que começa com o prefixo fornecido.
public boolean startsWith(String prefix) {
if (searchNode(prefix) == null) {
return false;
} else {
return true;
}
}
public TrieNode searchNode(String str) {
Map<Character, TrieNode> children = root.children;
TrieNode t = null;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (children.containsKey(c)) {
t = children.get(c);
children = t.children;
} else {
return null;
}
}
return t;
}
}