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.

Install
API
Build
License

Install

npm install --save @datastructures-js/trie

API

require

const Trie = require('@datastructures-js/trie');

import

import Trie from '@datastructures-js/trie';

Create a Trie

// example
const englishLang = new Trie();

.insert(word)

insert a string word into the trie.

runtime	params	return
O(k) : k is the length of word	word: {string}	{TrieNode} .getChar(): {string} returns the node's char. .getParent(): {TrieNode} returns the parent node. .isEndOfWord() {boolean} check if a node donates an end of a word. .getChild(char): {TrieNode} returns the child node of a char .hasChild(char): {boolean} check the node has a child char. .childrenCount(): {number} returns the number of children nodes.

englishLang.insert('hi');
englishLang.insert('hit');
englishLang.insert('hide');
englishLang.insert('hello');
englishLang.insert('sand');
englishLang.insert('safe');
englishLang.insert('noun');
englishLang.insert('name');

.has(word)

checks if a word exists in the trie.

runtime	params	return
O(k) : k is the length of word	word: {string}	{boolean}

englishLang.has('hi'); // true
englishLang.has('sky'); // false

.find(word)

finds a word in the trie and returns the node of its last character.

runtime	params	return
O(k) : k is the length of word	word: {string}	{TrieNode}

const hi = englishLang.find('hi');
// hi.getChar() = 'i'
// hi.getParent().getChar() = 'h'

const safe = englishLang.find('safe');
// safe.getChar() = 'e'
// safe.getParent().getChar() = 'f'
// safe.getParent().getParent().getChar() = 'a'

.remove(word)

removes a word from the trie.

runtime	params	return
O(k) : k is the length of word	word: {string}	{boolean}

englishLang.remove('hi'); // true - hi removed
englishLang.remove('sky'); // false - nothing is removed

.forEach(cb)

traverses all words in the trie.

runtime	params
O(n) : n is the number of nodes in the trie	cb: {function(word)}

englishLang.forEach((word) => console.log(word));

/*
hit
hide
hello
sand
safe
noun
name
*/

.toArray()

converts the trie into an array of words.

runtime	return
O(n) : n is the number of nodes in the trie	{array}

console.log(englishLang.toArray());

// ['hit', 'hide', 'hello', 'sand', 'safe', 'noun', 'name']

.getWordsCount()

gets the count of words in the trie.

runtime	return
O(1)	{number}

console.log(englishLang.getWordsCount()); // 7

.getNodesCount()

gets the count of nodes in the trie.

runtime	return
O(1)	{number}

console.log(englishLang.getNodesCount()); // 23

.clear()

clears the trie.

runtime
O(1)

englishLang.clear();
console.log(englishLang.getWordsCount()); // 0
console.log(englishLang.getNodesCount()); // 1

Build

grunt build

License

The MIT License. Full License is here