prefix-tree.H File Reference

Trie (prefix tree) implementation. More...

#include <cassert>
#include <cstddef>
#include <iostream>
#include <optional>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <tpl_tree_node.H>
#include <tpl_dynArray.H>
#include <tpl_dynList.H>
#include <ah-errors.H>

Include dependency graph for prefix-tree.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Cnode
	Low-level prefix tree node for storing character sequences. More...
class	Aleph::Cnode::Detached_Subtree_Guard
	Own a detached subtree until it is committed elsewhere. More...
class	Aleph::Cnode::Pending_Path_Guard
	Own standalone nodes until an insertion path is committed. More...
class	Aleph::Cnode::Clone_Target_Rollback
	Restore a clone target if appending cloned children fails. More...
class	Aleph::Prefix_Tree
	Owning prefix tree wrapper. More...
class	Aleph::Prefix_Tree_Map< T >
	Owning prefix tree map from strings to values. More...
class	Aleph::Prefix_Tree_Map< T >::Node
	Internal trie node storing one character and an optional value. More...
class	Aleph::Prefix_Tree_Map< T >::Node::Detached_Subtree_Guard
	Own a detached map subtree until it is committed. More...
class	Aleph::Prefix_Tree_Map< T >::Node::Pending_Path_Guard
	Own standalone insertion nodes until a new path is committed. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Trie (prefix tree) implementation.

Efficient string prefix search structure for autocomplete, dictionary lookup, and prefix matching. Prefer Prefix_Tree for ordinary use; Cnode remains available as the low-level node API.

Features

• O(k) lookup for k-length strings
• Prefix search support
• Memory-efficient for shared prefixes

Author

Leandro Rabindranath León

Definition in file prefix-tree.H.