1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
| package trie;
import java.util.HashMap;
import java.util.Map;
public class Trie {
// Private class
private class TrieNode {
Map<Character, TrieNode> children;
boolean endOfWord;
// Constructor
public TrieNode() {
children = new HashMap<>();
endOfWord = false;
}
}// End of inner class
private final TrieNode root;
// Constructor
public Trie() {
root = new TrieNode();
}
// Insert word into Trie
public void insert(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = current.children.get(ch);
if (node == null) {
node = new TrieNode();
current.children.put(ch, node);
}
current = node;
}
current.endOfWord = true;
System.out.println("Successfully inserted " + word + " in Trie !");
}
// Search for a word in Trie
public boolean search(String word) {
TrieNode currentNode = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = currentNode.children.get(ch);
if (node == null) { //CASE#1 -- if node does not exist for given char then return false
System.out.println("Word: " + word + " does not exists in Trie !");
return false;
}
currentNode = node;
}
if(currentNode.endOfWord == true) {
System.out.println("Word: " + word + " exists in Trie !"); //CASE#2 -- Word exists in Trie
}else {//CASE#3 -- Current word is a prefix of another word. But this word does not exists
System.out.println("Word: " + word + " does not exists in Trie ! But this is a Prefix of another Word !");
}
return currentNode.endOfWord;
}
// Delete word from Trie
public void delete(String word) {
if (search(word) == true) {
delete(root, word, 0);
}
}
// Returns true if parent should delete the mapping
private boolean delete(TrieNode parentNode, String word, int index) {
// CASE#1 -- Some other word's prefix is same as Prefix of this word (BCDE, BCKG)
// CASE#2 -- We are at last character of this word and This word is a Prefix of some other word (BCDE, BCDEFG)
// CASE#3 -- Some other word is a Prefix of this word (BCDE, BC)
// CASE#4 -- No one is dependent on this Word (BCDE, BCDE)
char ch = word.charAt(index);
TrieNode currentNode = parentNode.children.get(ch);
boolean canThisNodeBeDeleted;
if (currentNode.children.size() > 1) {
System.out.println("Entering Case#1");
delete(currentNode, word, index + 1); // CASE#1
return false;
}
if (index == word.length() - 1) { // CASE#2
System.out.println("Entering Case#2");
if (currentNode.children.size() >= 1) {
currentNode.endOfWord = false;//updating endOfWord will signify that this word is not there in Trie
return false;
} else {
System.out.println("Character " + ch + " has no dependency, hence deleting it from last");
parentNode.children.remove(ch);
return true;// If this word is not a prefix of some other word, and since this is last
// character, we should
// return true, indicating we are ok to delete this node
}
}
if (currentNode.endOfWord == true) { // CASE#3
System.out.println("Entering Case#3");
delete(currentNode, word, index + 1);
return false;
}
System.out.println("Entering Case#1");
canThisNodeBeDeleted = delete(currentNode, word, index + 1); // CASE#4
if (canThisNodeBeDeleted == true) {
System.out.println("Character " + ch + " has no dependency, hence deleting it");
parentNode.children.remove(ch);
return true; // Current node can also be deleted
} else {
return false; // Someone is dependent on this node, hence dont delete it
}
}
}// End of class
|