This TypeScript library provides a trie (prefix tree) implementation with various operations for efficient data storage and retrieval.
Install the library using npm:
npm install trie-dsa
import {
constructTrieNode,
mergeTrieNode,
contstructTrie,
trieHasKey,
trieGetValue,
trieDeleteKey,
traverseTrie,
type TrieKeyType,
type ArrayWithLastOfType,
type Trie,
} from "trie";
Represents the type of keys that can be used in the trie (string
, number
, or symbol
).
A utility type for arrays where the last element has a specific type.
The trie data structure type, where T
represents the type of keys and K
represents the type of values stored in the trie.
Constructs a trie node from an array of keys ending with a terminator value.
Merges two trie nodes into a single trie node.
Constructs a trie from raw data represented as an array of arrays, where each inner array ends with a terminator value.
Checks if a key exists in the trie.
Retrieves the value associated with a key in the trie.
Deletes a key and its associated value from the trie.
traverseTrie(trie: Trie<T, K>, callback: (key: T[], value: K | Trie<T, K>) => void, key: T[] = []): void
Traverses the trie and invokes a callback function for each node, passing the current key path and node value.
// Constructing a trie node
const nodeArray = ["x", "y", "z"];
const terminator = 10;
const result = constructTrieNode(nodeArray, terminator);
console.log(result);
// Output: { 'x': { 'y': { 'z': 10 } } }
// Merging two trie nodes
const trie1: Trie<string | number, number> = { a: { b: 1 } };
const trie2: Trie<string | number, number> = { a: { c: 2 } };
const merged = mergeTrieNode(trie1, trie2);
console.log(merged);
// Output: { 'a': { 'b': 1, 'c': 2 } }
// Constructing a trie from raw data
const rawTrieData: Array<ArrayWithLastOfType<TrieKeyType, number>> = [
["a", "b", "c", 1],
["a", "b", "d", 2],
["a", "e", 3],
["f", 4],
[1, 5],
];
const trie = contstructTrie(rawTrieData);
console.log(trie);
// Output: {
// 'a': {
// 'b': {
// 'c': 1,
// 'd': 2,
// },
// 'e': 3,
// },
// 'f': 4,
// 1: 5,
// }
// Checking if a key exists in the trie
console.log(trieHasKey(trie, ["a", "b", "c"])); // true
console.log(trieHasKey(trie, ["a", "b", "x"])); // false
console.log(trieHasKey(trie, [1])); // true
console.log(trieHasKey(trie, ["g"])); // false
// Retrieving a value from the trie
console.log(trieGetValue(trie, ["a", "b", "c"])); // 1
console.log(trieGetValue(trie, ["a", "e"])); // 3
console.log(trieGetValue(trie, [1])); // 5
console.log(trieGetValue(trie, ["g"])); // undefined
// Deleting a key from the trie
trieDeleteKey(trie, ["a", "b", "c"]);
console.log(trieHasKey(trie, ["a", "b", "c"])); // false
console.log(trieGetValue(trie, ["a", "b", "c"])); // undefined
// Traversing the trie
const keys: string[] = [];
const values: number[] = [];
traverseTrie(trie, (key, value) => {
keys.push(key.join("."));
values.push(value as number);
});
console.log(keys); // Output: ['a.b.d', 'a.e', 'f', '1']
console.log(values); // Output: [2, 3, 4, 5]
The trie data structure provides efficient operations for storing and retrieving data, especially useful for scenarios requiring prefix-based searches or hierarchical data organization. However, like any data structure, performance can vary based on implementation details and usage patterns.
This library is licensed under the MIT License. See the LICENSE file for more details.
Contributions are welcome! Please fork the repository and submit a pull request.