Package Exports

@datastructures-js/trie

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (@datastructures-js/trie) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

@datastructures-js/trie

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

Trie

Install
require
import
API
Build
License

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)

params	return
parent: TrieNode	TrieNode

.isEndOfWord()

return
boolean

.setEndOfWord(isEndOfWord)

params	return
isEndOfWord: boolean	TrieNode

.getChild(char)

params	return
char: string	TrieNode

.hasChild(char)

params	return
char: string	boolean

.childrenCount()

return
number

Build

grunt build

License

The MIT License. Full License is here