Skip to main content

​
Trie

#include <trie.hpp>
Trie (prefix tree) for efficient string prefix operations. Space-optimized prefix tree supporting insert, exact search, and prefix-based autocomplete operations. :::note Memory: O(total characters stored) - shared prefixes ::: :::note Operations: O(length of string) for insert/search :::

​
Example:

Trie t;
t.insert("api");
t.insert("app");
t.insert("apple");

t.search("api");              // true
t.search("ap");               // false
t.starts_with("ap");          // {"api", "app", "apple"}

​
Public Methods

ReturnNameDescription
voidinsertInsert a word into the trie.
boolsearch constSearch for exact word.
std::vector< std::string >starts_with constFind all words starting with prefix.

​
insert

inline 
inline void insert(std::string_view w)
Insert a word into the trie.

​
Parameters

  • w Word to insert (ASCII characters)
Word can be found via search() :::note Duplicate inserts are idempotent :::
const 
inline bool search(std::string_view w) const
Search for exact word.

​
Parameters

  • w Word to search for

​
Returns

true if word exists in trie

​
starts_with

const 
inline std::vector< std::string > starts_with(std::string_view prefix) const
Find all words starting with prefix.

​
Parameters

  • prefix Prefix to search for

​
Returns

Vector of all words starting with prefix Returns empty vector if prefix not found

​
Private Attributes

ReturnNameDescription
Noderoot_Root node.

​
root_

Node root_
Root node.

​
Private Methods

ReturnNameDescription
voidcollect constCollect all words with given prefix.

​
collect

const 
inline void collect(const Node & n, std::string & acc, std::vector< std::string > & out) const
Collect all words with given prefix.