Skip to content

Instantly share code, notes, and snippets.

@Phryxia
Created January 12, 2022 08:41
Show Gist options
  • Save Phryxia/8908b775900a1409a0d342330e6bed13 to your computer and use it in GitHub Desktop.
Save Phryxia/8908b775900a1409a0d342330e6bed13 to your computer and use it in GitHub Desktop.
Simple Trie implementation for JavasScript/TypeScript
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;
}
}
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;
}
}
@Phryxia
Copy link
Author

Phryxia commented Jan 12, 2022

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment