Created
January 12, 2022 08:41
-
-
Save Phryxia/8908b775900a1409a0d342330e6bed13 to your computer and use it in GitHub Desktop.
Simple Trie implementation for JavasScript/TypeScript
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 { | |
constructor() { | |
this.root = { children: {} }; | |
this.size = 0; | |
} | |
add(key, value) { | |
let node = this.root; | |
for (let i = 0; i < key.length; ++i) { | |
if (!node.children[key[i]]) node.children[key[i]] = { children: {} }; | |
node = node.children[key[i]]; | |
} | |
node.value = value; | |
this.size += 1; | |
return value; | |
} | |
get(key) { | |
let node = this.root; | |
for (let i = 0; i < key.length; ++i) { | |
if (!node.children[key[i]]) return undefined; | |
node = node.children[key[i]]; | |
} | |
return node.value; | |
} | |
remove(key) { | |
this._remove(this.root, key, 0); | |
} | |
_remove(node, key, index) { | |
if (!node) return undefined; | |
if (index === key.length) { | |
delete node.value; | |
this.size -= 1; | |
} else { | |
const c = key[index]; | |
const child = this._remove(node.children[c], key, index + 1); | |
if (child) node.children[c] = child; | |
else delete node.children[c]; | |
} | |
if (Object.keys(node.children).length === 0 && node.value === undefined) | |
return undefined; | |
return node; | |
} | |
} |
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
type TrieNode<T> = { | |
children: Record<string, TrieNode<T>>; | |
value?: T; | |
}; | |
class Trie<T> { | |
private root: TrieNode<T> = { children: {} }; | |
private _size: number = 0; | |
public add(key: string, value: T): T { | |
let node = this.root; | |
for (let i = 0; i < key.length; ++i) { | |
if (!node.children[key[i]]) node.children[key[i]] = { children: {} }; | |
node = node.children[key[i]]; | |
} | |
node.value = value; | |
this._size += 1; | |
return value; | |
} | |
public get(key: string): T | undefined { | |
let node = this.root; | |
for (let i = 0; i < key.length; ++i) { | |
if (!node.children[key[i]]) return undefined; | |
node = node.children[key[i]]; | |
} | |
return node.value; | |
} | |
public remove(key: string): void { | |
this._remove(this.root, key, 0); | |
} | |
private _remove( | |
node: TrieNode<T>, | |
key: string, | |
index: number | |
): TrieNode<T> | undefined { | |
if (!node) return undefined; | |
if (index === key.length) { | |
delete node.value; | |
this._size -= 1; | |
} else { | |
const c = key[index]; | |
const child = this._remove(node.children[c], key, index + 1); | |
if (child) node.children[c] = child; | |
else delete node.children[c]; | |
} | |
if (Object.keys(node.children).length === 0 && node.value === undefined) | |
return undefined; | |
return node; | |
} | |
public size(): number { | |
return this._size; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Note that javascript trie is not appropriate for set/map purpose.
Native object is thousands times faster. (https://www.measurethat.net/Benchmarks/Show/16659/0/trie-vs-native-map)
This is only meaningful when you need some other algorithmic approaches.