#trie #prefix-tree #digital-tree #retrieval-tree

dyn_trie

Dynamic trie is trie capable of mapping any T to any char iterator

16 stable releases

new 2.3.3 Mar 9, 2025
2.3.1 Feb 16, 2025
1.1.1 Jan 19, 2025
1.0.5 Dec 15, 2024
1.0.2 Jul 22, 2024

#1646 in Data structures

Download history 1/week @ 2024-11-18 77/week @ 2024-12-09 50/week @ 2024-12-16 1/week @ 2025-01-06 241/week @ 2025-01-13 71/week @ 2025-01-20 460/week @ 2025-01-27 327/week @ 2025-02-03 91/week @ 2025-02-10 74/week @ 2025-02-17 5/week @ 2025-02-24 172/week @ 2025-03-03

353 downloads per month

MIT license

60KB
1.5K SLoC

Dynamic Trie

Dynamic trie is trie that allows mapping of any T to any char iterator with asymptotical computational complexity based on that of std::collections::HashMap.

Node occurs for each char as defined by Rust language.

let mut trie = Trie::<char>::new();

let some = "información meteorológica".chars();
trie.ins('🌩', some.clone());

let one_more = "alimentación RSS".chars();
trie.ins('😋', one_more.clone());

assert_eq!(RemRes::Ok('😋'), trie.rem(one_more.clone()));
assert_eq!(AcqRes::Err(KeyErr::Unknown), trie.acq(one_more.clone()));
assert_eq!(AcqRes::Ok(&'🌩'), trie.acq(some.clone()));

lib.rs:

Dynamic trie in contrast to classic trie does not have fixed size alphabet associated with node.

Each node has dynamic alphabet of size as to satisfy exactly associated branches.

No runtime deps