Collection Kit

RadixTree

Tree

A RadixTree (or Patricia Trie) is a space-optimized trie that allows for efficient retrieval of keys by compressing common prefixes. It is particularly useful for storing strings and performing prefix searches.

Import Statement
import { RadixTree } from "collection-kit";

Key Features

  • Space Efficiency: Reduces the number of nodes by merging nodes that share common prefixes.
  • Fast Search: Allows for quick lookups, insertions, and deletions.

Common Operations

Insert
Add a new string to the RadixTree.
Search
Check if a string exists in the tree.
Delete
Remove a string from the tree.

Example Code

import { RadixTree } from "collection-kit";

const tree = new RadixTree();
tree.insert("romane");
tree.insert("romanus");
tree.insert("romulus");

console.log(tree.search("romane"));  // true
console.log(tree.search("roman"));   // false