Ternary Search Trie

A ternary search trie implementation in TypeScript.

Installing

You can install the package via npm or yarn.

NPM

npm install ternary-search-trie

Yarn

yarn add ternary-search-trie

Documentation

Trie

Represents a ternary search trie.

Usage

import { Trie } from 'ternary-search-trie';

interface Value {
  data: string;
}

const trie = new Trie<Value>();

Members

isEmpty
size

isEmpty

Returns true if the tree contains any nodes, otherwise false.

console.log(trie.isEmpty);
//=> true

size

Gets the size of the tree in terms of the number of nodes present within the tree.

console.log(trie.size);
//=> 0

set

set(key: string, value: Value): Trie<Value>

Adds the specified key/value pair to the tree.

Example:

const value = { data: 'test' };

trie.set('data', value);

get

get(key: string): Value | null

Returns the value of the node with the specified key.

Example:

const value = { data: 'test' };

trie.set('data', value);

console.log(trie.get('data'));
//=> { data: 'test' }

del

del(key: string): Trie<Value>

Deletes the node with the specified key.

Example:

const value = { data: 'test' };

trie.set('data', value);

console.log(trie.get('data'));
//=> { data: 'test' }

trie.del('data');

console.log(trie.get('data'));
//=> null;

contains

contains(key: string): boolean

Checks if a node with the specified key exists in the tree.

Example:

console.log(trie.contains('foo'));
//=> false

keys

keys(): string[]

Returns an array of all keys present in the tree.

Example:

const value = { data: 'test' };

trie.set('foo', value);
trie.set('bar', value);
trie.set('baz', value);

console.log(trie.keys());
//=>  [ 'bar', 'baz', 'foo' ]

keysWithPrefix

keysWithPrefix(prefix: string): string[]

Returns all keys present in the tree that begin with the specified prefix.

Example:

const value = { data: 'test' };

trie.set('foo', value);
trie.set('bar', value);
trie.set('baz', value);

console.log(trie.keysWithPrefix('ba'));
//=>  [ 'bar', 'baz' ]

searchWithPrefix

searchWithPrefix(prefix: string, callback: (key: string, value: Value) => void): void;

Executes the specified callback at each node in the tree whose key begins with the specified prefix.

Example:

const value = { data: 'test' };

trie.set('foo', value);
trie.set('bar', value);
trie.set('baz', value);

trie.searchWithPrefix('ba', (key, value) => console.log({ key, value }));
//=> { key: 'bar', value: { data: 'test' } }
//=> { key: 'baz', value: { data: 'test' } }

dfs

dfs(callback: (key: string, value: Value | null) => void): void;

Performs a depth-first search of the tree beginning from the root node. Executes the specified callback at each visited node.

Example:

const value = { data: 'test' };

trie.set('foo', value);

trie.dfs((key, value) => console.log({ key, value }));
//=> { key: 'f', value: null }
//=> { key: 'o', value: null }
//=> { key: 'o', value: { data: 'test' } }

toString()

Returns the tree as a string.

Contributing

Please read CONTRIBUTING.md for details on our code of conduct, and the process for submitting pull requests to us.

License

This project is licensed under the MIT License - see the LICENSE file for details

Acknowledgments

This project was heavily inspired by work done by @jakwings on node-ternary-search-trie. This project differs in that it is written in TypeScript and chose to implement the underlying functionality of the tree by making heavy use of recursion instead of loops.

Avoid exposing the Node interface

The current implementation of the callbacks that can be supplied to searchWithPrefix and dfs accept the entire Node object as a parameter. However, Nodes should never be exposed to the end user, only the key and value of the Node. In addition, the key value received by the searchWithPrefix callback should probably be the entire key used to retrieve the value of that Node, not just the single letter of the Node.

Provide the entire key as the parameter supplied to searchWithPrefix callback
Avoid exposing the full Node object in the callback parameter supplied to searchWithPrefix
Avoid exposing the full Node object in the callback parameter supplied to dfs

imax153 / ternary-search-trie Goto Github PK