#trie #collection #generic


A simple Trie implementation in Rust

15 releases (stable)

1.2.3 Aug 27, 2023
1.2.2 Aug 26, 2023
0.2.1 Jul 28, 2023
0.1.1 Jul 24, 2023
0.0.1 Jul 22, 2023

#211 in Data structures

Download history 48/week @ 2023-08-12 51/week @ 2023-08-19 74/week @ 2023-08-26 20/week @ 2023-09-02 3/week @ 2023-09-09 17/week @ 2023-09-16 17/week @ 2023-09-23 3/week @ 2023-09-30 19/week @ 2023-10-21 16/week @ 2023-10-28 17/week @ 2023-11-11 33/week @ 2023-11-18 31/week @ 2023-11-25

81 downloads per month

Custom license

1.5K SLoC

Basic Trie

Test CI

The trie data structure is used for quick access to words and data that should (could) be associated with them.

Basic Trie is implemented as a tree where each node holds a single character that could point at any other character thus allowing insertion of arbitrary words.

There are two major implementations:

  • Dataless Trie where words are inserted with nothing attached to them
  • Data Trie where each word has a corresponding vector of data attached to it

Dataless tries are often used for word lookups and prefix matching, and data tries are often used for finding all data that is connected to some prefix.

For example, when inserting a whole book in the trie, you could insert every word with the corresponding page number it's on. Later when searching for the word, you could get all the pages the word is on with no added performance cost.

Global features

  • insertion / removal of words
  • finding words based on prefix
  • longest / shortest words in the trie
  • number of complete words in the trie
  • generic methods: is_empty, contains, clear
  • Trie equality with ==
  • Trie merging with + or +=

Data Trie features

  • generic type implementation for associating a word to any type, with zero trait constraints
  • finding data of words based on exact match or prefix

Optional features

  • unicode support via the 'unicode' feature with the unicode-segmentation crate (enabled by default)
  • data trie support via the 'data' feature (enabled by default)
  • serialization and deserialization via the 'serde' feature with the serde crate


  • unicode-segmentation (enabled by default)
  • serde (only with 'serde' feature flag)
  • fxhash
  • thin-vec
  • arrayvec


The software is licensed under the MIT license.


use basic_trie::DatalessTrie;

let mut dataless_trie = DatalessTrie::new();

let mut found_longest_words = dataless_trie.longest_words().unwrap();

assert_eq!(vec![String::from("eating"), String::from("wizard")], found_longest_words);
assert_eq!(vec![String::from("eat")], dataless_trie.shortest_words().unwrap());
assert_eq!(3, dataless_trie.number_of_words());
use basic_trie::DataTrie;

let mut data_trie = DataTrie::<u32>::new();
data_trie.insert("apple", 1);
data_trie.insert("apple", 2);
data_trie.insert("avocado", 15);

let mut found_data = data_trie.find_data_of_word("apple", false).unwrap();
assert_eq!(vec![&1, &2], found_data);

let mut found_data = data_trie.find_data_of_word("a", true).unwrap();
assert_eq!(vec![&1, &2, &15], found_data);

assert_eq!(vec![15], data_trie.remove_word("avocado").unwrap());


  • 1.2.3 – Adding dependencies for even more memory layout optimisations.
  • 1.2.2 – More memory optimizations with Box.
  • 1.2.1 – Memory performance upgrade with Box. Mutable data retrieval.
  • 1.2.0 – Equality and addition operators support between same Trie types via ==, + and +=.
  • 1.1.1 – Adding FxHashMap dependency for boosted performance.
  • 1.1.0 – Serialization with the serde crate and the 'serde' feature.
  • 1.0.3 – Optimization of number_of_words(). Removing lifetime requirements for word insertion for much better flexibility at the same logical memory cost.
  • 1.0.2 – Bug fixes.
  • 1.0.1insert_no_data() for DataTrie. Bugfixes.
  • 1.0.0 – Separation of DataTrie and DatalessTrie. Optimizing performance for DatalessTrie. Incompatible with older versions.
  • <1.0.0 – Simple Trie with data and base features.


~12K SLoC