A prefix tree (trie) is a data structure that allows you to store an associative array whose keys are strings

Last update: Jan 28, 2022

Related tags

Data structures radix-trie

Overview

RadixTrie

A prefix tree (trie) is a data structure that allows you to store an associative array whose keys are strings. It is a root tree, each edge of which is marked with some character. Algorithmic complexity for all operations(insert, remome, contains) - O(n) where n is the length of the string that is queried/deleted/inserted, i.e. the number of different characters on the edges of a given prefix tree.

Usage

use radixtrie::RadixTrie;

fn main() {
    let mut radix_trie = RadixTrie::<u32>::new();

    radix_trie.insert("first".as_bytes(), 1);
    radix_trie.insert("second".as_bytes(), 2);
    radix_trie.insert("third".as_bytes(), 3);

    assert_eq!(radix_trie.lookup("first".as_bytes()), Some(&1));
    assert_eq!(radix_trie.lookup("second".as_bytes()), Some(&2));

    radix_trie.remove("first".as_bytes());
    radix_trie.remove("second".as_bytes());

    assert_eq!(radix_trie.lookup("first".as_bytes()), None);
    assert_eq!(radix_trie.lookup("second".as_bytes()), None);
}

use radixtrie::RadixTrie;

fn main() {
    let mut radix_trie = RadixTrie::<()>::new();
    radix_trie.insert("kare".as_bytes(), ());
    radix_trie.insert("kanojo".as_bytes(), ());
    radix_trie.insert("karetachi".as_bytes(), ());
    radix_trie.insert("sakura".as_bytes(), ());
    radix_trie.insert("korosu".as_bytes(), ());
    let mut keys = vec![];

    radix_trie.traversal("kar".as_bytes(), |key: &[u8], _|{
        keys.push(String::from_utf8(key.to_vec()).unwrap());
    });
    assert_eq!(keys, vec!["kare".to_string(), "karetachi".to_string()]);
}