Last active
December 19, 2018 22:49
-
-
Save benjamine/dc27fdfd828da04bf90019cc85b0f387 to your computer and use it in GitHub Desktop.
trie.js
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Trie { | |
head = { | |
key: "", | |
children: {} | |
}; | |
add(key) { | |
var curNode = this.head, | |
newNode = null, | |
curChar = key.slice(0, 1); | |
key = key.slice(1); | |
while ( | |
typeof curNode.children[curChar] !== "undefined" && | |
curChar.length > 0 | |
) { | |
curNode = curNode.children[curChar]; | |
curChar = key.slice(0, 1); | |
key = key.slice(1); | |
} | |
while (curChar.length > 0) { | |
newNode = { | |
key: curChar, | |
value: key.length === 0 ? null : undefined, | |
children: {} | |
}; | |
curNode.children[curChar] = newNode; | |
curNode = newNode; | |
curChar = key.slice(0, 1); | |
key = key.slice(1); | |
} | |
} | |
search(key) { | |
var curNode = this.head, | |
curChar = key.slice(0, 1), | |
d = 0; | |
key = key.slice(1); | |
while ( | |
typeof curNode.children[curChar] !== "undefined" && | |
curChar.length > 0 | |
) { | |
curNode = curNode.children[curChar]; | |
curChar = key.slice(0, 1); | |
key = key.slice(1); | |
d += 1; | |
} | |
if (curNode.value === null && key.length === 0) { | |
return d; | |
} else { | |
return -1; | |
} | |
} | |
remove(key) { | |
var d = this.search(key); | |
if (d > -1) { | |
removeH(this.head, key, d); | |
} | |
} | |
} | |
function removeH(node, key, depth) { | |
if (depth === 0 && Object.keys(node.children).length === 0) { | |
return true; | |
} | |
var curChar = key.slice(0, 1); | |
if (removeH(node.children[curChar], key.slice(1), depth - 1)) { | |
delete node.children[curChar]; | |
if (Object.keys(node.children).length === 0) { | |
return true; | |
} else { | |
return false; | |
} | |
} else { | |
return false; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Trie { | |
head = { | |
key: "", | |
children: {} | |
}; | |
add(key) { | |
var curNode = this.head, | |
newNode = null, | |
curChar = key.slice(0, 1); | |
key = key.slice(1); | |
while ( | |
typeof curNode.children[curChar] !== "undefined" && | |
curChar.length > 0 | |
) { | |
curNode = curNode.children[curChar]; | |
curChar = key.slice(0, 1); | |
key = key.slice(1); | |
} | |
while (curChar.length > 0) { | |
newNode = { | |
key: curChar, | |
value: key.length === 0 ? null : undefined, | |
children: {} | |
}; | |
curNode.children[curChar] = newNode; | |
curNode = newNode; | |
curChar = key.slice(0, 1); | |
key = key.slice(1); | |
} | |
} | |
search(key) { | |
var curNode = this.head, | |
curChar = key.slice(0, 1), | |
d = 0; | |
key = key.slice(1); | |
while ( | |
typeof curNode.children[curChar] !== "undefined" && | |
curChar.length > 0 | |
) { | |
curNode = curNode.children[curChar]; | |
curChar = key.slice(0, 1); | |
key = key.slice(1); | |
d += 1; | |
} | |
if (curNode.value === null && key.length === 0) { | |
return d; | |
} else { | |
return -1; | |
} | |
} | |
remove(key) { | |
var d = this.search(key); | |
if (d > -1) { | |
removeH(this.head, key, d); | |
} | |
} | |
} | |
function removeH(node, key, depth) { | |
if (depth === 0 && Object.keys(node.children).length === 0) { | |
return true; | |
} | |
var curChar = key.slice(0, 1); | |
if (removeH(node.children[curChar], key.slice(1), depth - 1)) { | |
delete node.children[curChar]; | |
if (Object.keys(node.children).length === 0) { | |
return true; | |
} else { | |
return false; | |
} | |
} else { | |
return false; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment