Trie | Data structure implementation in Typescript
Sandro Maglione
Get in touch with meWeb development
5 June 2023
β’3 min read
Sandro Maglione
Web development
In my projects I work a lot with list of words. If you ever have to deal with words and texts, you will eventually discover (and implement) a Trie data structure.
This is what happened to me. I ended up implementing a Trie in various languages and with different strategies.
Finally, I settled on one implementation that is efficient and complete (complete enough for my purposes).
Here it is π
export class Trie {
/** Check if the current node marks a complete word */
#isEnd = false;
/** Store sub-`Trie` */
#children: Record<string, Trie> = {};
constructor() {}
public get isEnd() {
return this.#isEnd;
}
public get children() {
return this.#children;
}
/**
* Check if given `char` is present in current `Trie`.
*/
hasChar(char: string): Trie | null {
const searchChar = this.children[char];
if (typeof searchChar !== "undefined") {
return searchChar;
}
return null;
}
/**
* Add `Trie` at given `char`, and return new added `Trie`.
*/
addChar(char: string): Trie {
const newSubTrie = new Trie();
this.children[char] = newSubTrie;
return newSubTrie;
}
/**
* Mark complete word found in current `Trie`.
*/
makeEnd(): void {
this.#isEnd = true;
}
/**
* Search given `word` in `Trie`.
*/
searchTrie(word: string): boolean {
if (word.length === 0) {
return this.#isEnd;
}
const subTrie = this.hasChar(word[0]);
if (subTrie === null) {
return false;
}
return subTrie.searchTrie(word.slice(1));
}
/**
* Add `word` to this `Trie`.
*/
addWord(word: string): void {
if (word.length === 0) {
this.makeEnd();
return;
}
const subTrie = this.hasChar(word[0]);
if (subTrie !== null) {
return subTrie.addWord(word.slice(1));
} else {
const newSubTrie = this.addChar(word[0]);
return newSubTrie.addWord(word.slice(1));
}
}
/**
* Static constructor to build a `Trie` from a list of words (`wordList`).
*/
static buildTrie = (wordList: string[]): Trie => {
const trie = new Trie();
for (let i = 0; i < wordList.length; i++) {
const word = wordList[i];
trie.addWord(word);
}
return trie;
};
}What is a Trie?
A Trie is a data structure used to store a list of words. Using a Trie makes searching for a word efficient (O(dm), where d is the length of the string you are searching, and m is the alphabet size).
When to use a Trie
Following a simple usecase example.
You have a list of words and a long text, and you want to search all the occurrences of each word in the text.
The naive / brute-force approach consists splitting the text in words and, for each word, search in the list. This gets slow pretty fast π
In this case a Trie is ideal, since it stores words more efficiently and it makes searching much faster ποΈ
How to use Trie
You usually start from a list of words.
You can build a Trie from the list using the static constructor buildTrie:
const wordList: string[] = ...; // Your list of words π
const trie = Trie.buildTrie(wordList);That's basically it! ππΌββοΈ
Now the Trie allows to search for any word (using searchTrie) and add any word (using addWord):
const hasWord = trie.searchTrie("sandro"); // Search word "sandro" in `trie`
trie.addWord("sandro"); // Add word "sandro" to `trie`Note: This
Trieimplementation is mutable, you are allowed to modify theTrie(children,addWord,addChar) βοΈ