@datastructures-js/trie
npm i @datastructures-js/trie

@datastructures-js/trie

🔡 Trie data structure implementation in javascript

by datastructures-js

4.2.0 (see all)License:MITTypeScript:Not FoundCategories:Vanilla JavaScript Trie
npm i @datastructures-js/trie
Readme

@datastructures-js/trie

build:? npm npm npm

Trie implementation in javascript. Each Trie node holds one character of a word.

Trie
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.

runtime
O(1)
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)

params
char: string

.isRoot()

return
boolean

.getChar()

return
string

.getParent()

return
TrieNode

.setParent(parent)

paramsreturn
parent: TrieNodeTrieNode

.isEndOfWord()

return
boolean

.setEndOfWord(isEndOfWord)

paramsreturn
isEndOfWord: boolean TrieNode

.getChild(char)

paramsreturn
char: stringTrieNode

.hasChild(char)

paramsreturn
char: stringboolean

.childrenCount()

return
number

Build

grunt build

License

The MIT License. Full License is here