JavaScript/Data-Structures/Tree/Trie.js at master · flexycode/JavaScript · GitHub

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
constTrieNode=functionTrieNode(key,parent){
this.key=key
this.count=0
this.children=Object.create(null)
if(parent===undefined){
this.parent=null
}else{
this.parent=parent
}
}

functionTrie(){
// create only root with null key and parent
this.root=newTrieNode(null,null)
}

// Recursively finds the occurrence of all words in a given node
Trie.findAllWords=function(root,word,output){
if(root===null)return
if(root.count>0){
if(typeofoutput==='object'){
output.push({ word,count: root.count})
}
}
letkey
for(keyinroot.children){
word+=key
this.findAllWords(root.children[key],word,output)
word=word.slice(0,-1)
}
}

Trie.prototype.insert=function(word){
if(typeofword!=='string')return
if(word===''){
this.root.count+=1
return
}
letnode=this.root
constlen=word.length
leti
for(i=0;i<len;i++){
if(node.children[word.charAt(i)]===undefined){
node.children[word.charAt(i)]=newTrieNode(word.charAt(i),node)
}
node=node.children[word.charAt(i)]
}
node.count+=1
}

Trie.prototype.findPrefix=function(word){
if(typeofword!=='string')returnnull
letnode=this.root
constlen=word.length
leti
// After end of this loop node will be at desired prefix
for(i=0;i<len;i++){
if(node.children[word.charAt(i)]===undefined)returnnull// No such prefix exists
node=node.children[word.charAt(i)]
}
returnnode
}

Trie.prototype.remove=function(word,count){
if(typeofword!=='string')return
if(typeofcount!=='number')count=1
elseif(count<=0)return

// for empty string just delete count of root
if(word===''){
if(this.root.count>=count)this.root.count-=count
elsethis.root.count=0
return
}

letchild=this.root
constlen=word.length
leti,key
// child: node which is to be deleted
for(i=0;i<len;i++){
key=word.charAt(i)
if(child.children[key]===undefined)return
child=child.children[key]
}

// Delete no of occurrences specified
if(child.count>=count)child.count-=count
elsechild.count=0

// If some occurrences are left we don't delete it or else
// if the object forms some other objects prefix we don't delete it
// For checking an empty object
// https://stackoverflow.com/questions/679915/how-do-i-test-for-an-empty-javascript-object
if(
child.count<=0&&
Object.keys(child.children).length&&
child.children.constructor===Object
){
child.parent.children[child.key]=undefined
}
}

Trie.prototype.findAllWords=function(prefix){
constoutput=[]
// find the node with provided prefix
constnode=this.findPrefix(prefix)
// No such prefix exists
if(node===null)returnoutput
Trie.findAllWords(node,prefix,output)
returnoutput
}

Trie.prototype.contains=function(word){
// find the node with given prefix
constnode=this.findPrefix(word)
// No such word exists

returnnode!==null&&node.count!==0
}

Trie.prototype.findOccurrences=function(word){
// find the node with given prefix
constnode=this.findPrefix(word)
// No such word exists
if(node===null)return0
returnnode.count
}

export{Trie}