@datastructures-js/trie
Trie implementation in javascript. Each Trie node holds one character of a word.
Trie |
|
Contents
Install
npm install --save @datastructures-js/trie
require
const { Trie, TrieNode } = require('@datastructures-js/trie');
import
import { Trie, TrieNode } from '@datastructures-js/trie';
API
constructor
const dictionary = new Trie();
.insert(value)
insert the string form of value (value.toString()
) into the trie.
Note: the empty string is not a default word in the trie. empty word can be added by explicitly calling .insert('')
params |
return |
runtime |
value: { toString: () => string } |
Trie |
O(k): k = length of string value |
dictionary
.insert('hi')
.insert('hit')
.insert('hide')
.insert('hello')
.insert('sand')
.insert('safe')
.insert('noun')
.insert('name');
.has(value)
checks if a word exists in the trie.
params |
return |
runtime |
value: { toString: () => string } |
boolean |
O(k): k = length of string value |
dictionary.has('hi'); // true
dictionary.has('sky'); // false
.find(value)
finds a word in the trie and returns the node of its last character.
params |
return |
runtime |
value: { toString: () => string } |
TrieNode |
O(k): k = length of string value |
const hi = dictionary.find('hi');
// hi.getChar() = 'i'
// hi.getParent().getChar() = 'h'
const safe = dictionary.find('safe');
// safe.getChar() = 'e'
// safe.getParent().getChar() = 'f'
// safe.getParent().getParent().getChar() = 'a'
const nothing = dictionary.find('nothing'); // null
.remove(value)
removes a word from the trie.
params |
return |
runtime |
value: { toString: () => string } |
string: the removed word |
O(k): k = length of string value |
dictionary.remove('hi'); // hi
// none existing word
dictionary.remove('sky'); // null
.forEach(cb)
traverses all words in the trie.
params |
runtime |
cb: (word: string) => void |
O(n): n = number of nodes in the trie |
dictionary.forEach((word) => console.log(word));
/*
hit
hide
hello
sand
safe
noun
name
*/
.toArray()
converts the trie into an array of words.
return |
runtime |
string[] |
O(n): n = number of nodes in the trie |
console.log(dictionary.toArray());
// ['hit', 'hide', 'hello', 'sand', 'safe', 'noun', 'name']
.wordsCount()
gets the count of words in the trie.
return |
runtime |
number |
O(1) |
console.log(dictionary.wordsCount()); // 7
.nodesCount()
gets the count of nodes in the trie.
return |
runtime |
number |
O(1) |
console.log(dictionary.nodesCount()); // 23
.clear()
clears the trie.
dictionary.clear();
console.log(dictionary.wordsCount()); // 0
console.log(dictionary.nodesCount()); // 1
Trie.fromArray(list)
converts an existing array of values into a trie.
params |
return |
runtime |
list: string[] |
boolean |
O(n * k) |
const numbersTrie = Trie.fromArray([1, 32, 123, 21, 222, 132, 111, 312]);
console.log(numbersTrie.wordsCount()); // 8
console.log(numbersTrie.has('132')); // true
console.log(numbersTrie.has(123)); // true
TrieNode
new TrieNode(char)
.isRoot()
.getChar()
.getParent()
.setParent(parent)
params | return |
parent: TrieNode | TrieNode |
.isEndOfWord()
.setEndOfWord(isEndOfWord)
params | return |
isEndOfWord: boolean |
TrieNode |
.getChild(char)
params | return |
char: string | TrieNode |
.hasChild(char)
params | return |
char: string | boolean |
.childrenCount()
Build
grunt build
License
The MIT License. Full License is here