Skip to content

Instantly share code, notes, and snippets.

@DyadicGit
Last active October 28, 2020 08:59
Show Gist options
  • Save DyadicGit/223c3936b9d34eca267e919530867efc to your computer and use it in GitHub Desktop.
Save DyadicGit/223c3936b9d34eca267e919530867efc to your computer and use it in GitHub Desktop.
Trie in JS/Typescript with data storing, used for fast searching
class TrieNode {
constructor(key) {
this.key = key
this.parent = null
this.children = {}
this.end = false
}
getWord() {
const output = [];
let node = this;
while (node !== null) {
output.unshift(node.key)
node = node.parent
}
return output.join('')
}
}
class Trie {
constructor() {
this.root = new TrieNode(null)
}
insert(word) {
let node = this.root;
for (let i = 0; i < word.length; i++) {
if (!node.children[word[i]]) {
node.children[word[i]] = new TrieNode(word[i])
node.children[word[i]].parent = node
}
node = node.children[word[i]]
if (i === word.length - 1) {
node.end = true
}
}
}
contains(word) {
let node = this.root;
for (let i = 0; i < word.length; i++) {
if (node.children[word[i]]) {
node = node.children[word[i]]
} else {
return false
}
}
return node.end
}
find(prefix) {
let node = this.root;
const output = [];
for (let i = 0; i < prefix.length; i++) {
if (node.children[prefix[i]]) {
node = node.children[prefix[i]]
} else {
return output
}
}
findAllWords(node, output)
return output
}
}
function findAllWords(node, arr) {
if (node.end) {
arr.unshift(node.getWord())
}
for (const child in node.children) {
findAllWords(node.children[child], arr)
}
}
export default Trie;
/*
// usage
var trie = new Trie();
// insert values
trie.insert("hello");
trie.insert("helium");
// check contains method
console.log(trie.contains("helium")); // true
console.log(trie.contains("kickass")); // false
// check find method
console.log(trie.find("hel")); // [ 'helium', 'hello' ]
console.log(trie.find("hell")); // [ 'hello' ]
// extended from https://gist.github.com/tpae gist
*/
class TrieNode {
key: string;
parent;
children;
end: boolean;
constructor(key) {
this.key = key
this.parent = null
this.children = {}
this.end = false
}
getWord() {
const output = [];
let node = this;
while (node !== null) {
output.unshift(node.key)
node = node.parent
}
return output.join('')
}
}
class Trie {
private readonly root: TrieNode;
constructor() {
this.root = new TrieNode(null)
}
insert(word) {
let node = this.root;
for (let i = 0; i < word.length; i++) {
if (!node.children[word[i]]) {
node.children[word[i]] = new TrieNode(word[i])
node.children[word[i]].parent = node
}
node = node.children[word[i]]
if (i === word.length - 1) {
node.end = true
}
}
}
contains(word) {
let node = this.root;
for (let i = 0; i < word.length; i++) {
if (node.children[word[i]]) {
node = node.children[word[i]]
} else {
return false
}
}
return node.end
}
find(prefix) {
let node = this.root;
const output = [];
for (let letter of prefix) {
if (node.children[letter]) {
node = node.children[letter]
} else {
return output
}
}
findAllWords(node, output)
return output
}
}
function findAllWords(node, arr) {
if (node.end) {
arr.unshift(node.getWord())
}
for (const child in node.children) {
findAllWords(node.children[child], arr)
}
}
export default Trie;
/*
// usage
var trie = new Trie();
// insert values
trie.insert("hello");
trie.insert("helium");
// check contains method
console.log(trie.contains("helium")); // true
console.log(trie.contains("kickass")); // false
// check find method
console.log(trie.find("hel")); // [ 'helium', 'hello' ]
console.log(trie.find("hell")); // [ 'hello' ]
// extended from https://gist.github.com/tpae gist
*/
class TrieNode {
key: string;
data: Array<any>;
children;
end: boolean;
constructor(key) {
this.key = key
this.data = []
this.children = {}
this.end = false
}
}
class TrieWithStorage {
private readonly root: TrieNode;
constructor(rootData) {
this.root = new TrieNode(null)
this.root.data = rootData;
}
insert(word, data) {
let node = this.root;
for (let i = 0; i < word.length; i++) {
if (!node.children[word[i]]) {
node.children[word[i]] = new TrieNode(word[i])
}
node.children[word[i]].data.push(data)
node = node.children[word[i]]
if (i === word.length - 1) {
node.end = true
}
}
}
contains(word) {
let node = this.root;
for (let i = 0; i < word.length; i++) {
if (node.children[word[i]]) {
node = node.children[word[i]]
} else {
return false
}
}
return node.end
}
find(prefix) {
let node = this.root;
const output = [];
for (let letter of prefix) {
if (node.children[letter]) {
node = node.children[letter]
} else {
return output
}
}
return node.data
}
}
export default TrieWithStorage;
/*
// usage
var trie = new Trie();
// insert values
trie.insert("hello", {mydata: 'example 1'});
trie.insert("helium", {mydata: 'example 2'});
// find
console.log(trie.find("hel")); // [ {mydata: 'example 1'}, {mydata: 'example 2'} ]
console.log(trie.find("hell")); // [ {mydata: 'example 1'} ]
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment