An implementation of a Trie data structure.

README.md

Usage

A trie is a key-value pair data structure, that allows you to store a value, by associating it with some string value. If you happen to know what that string value is, then you can retrieve the original value associated with the string.

If the string value is not associated to any value, then a null is returned.

As opposed to an associative array, tries actually save memory, by not storing redundant character prefixes of strings.

import Trie from './trie';

const set = new Trie();
set.set('foo', 42);
set.set('bar', 3);
set.set('baz', 10);
set.set('foobar', 20);

console.log(set.get('foo')); // -> 42
console.log(set.get('bar')); // -> 3
console.log(set.get('baz')); // -> 10
console.log(set.get('foobar')); // -> 20
console.log(set.get('nothing')); // -> null

trie.ts

const firstRemainderString = (value: string) => {
  const [ first, ...remainder ] = value;
  return { first, remainder: remainder.join('') };
}

class TrieNode<T> {
  value: T
  children: Map<string, TrieNode<T>>
  set(key: string, value: T) {
    if (key.length <= 0) { this.value = value; return; }
    const { first, remainder } = firstRemainderString(key);
    const node = this.children.get(first);
    if (!node) {
      this.children.set(first, new TrieNode(remainder, value));
    } else {
      node.set(remainder, value);
    }
  }
  get(key: string) {
    if (key.length <= 0) { return this.value; }
    const { first, remainder } = firstRemainderString(key);
    const node = this.children.get(first);
    if (!node) {
      return null;
    }
    return node.get(remainder);
  }

  constructor(key: string, value: T) {
    this.value = null;
    this.children = new Map();
    this.set(key, value);
  }
}

class Trie<T> {
  emptyStringValue: T
  children: Map<string, TrieNode<T>>

  constructor() {
    this.emptyStringValue = null;
    this.children = new Map();
  }

  set(key: string, value: T) {
    if (key.length <= 0) {
      this.emptyStringValue = value;
    }
    
    const { first, remainder } = firstRemainderString(key);
    const node = this.children.get(first);
    if (!node) {
      this.children.set(first, new TrieNode(remainder, value));
    } else {
      node.set(remainder, value);
    }
  }

  get(key: string) {
    if (key.length <= 0) {
      return this.emptyStringValue;
    }
    const { first, remainder } = firstRemainderString(key);
    const node = this.children.get(first);
    if (!node) {
      return null;
    }
    return node.get(remainder);
  }
}