Crate trailtree 

TrailTree

TrailTree is a hierarchical search tree structure designed for efficiently searching and traversing paths using layer-scoped, unique keys.

Features

• Path-based Operations: Provides efficient insertion and retrieval of paths using subtrees.
• Generic Keys and Data: Supports keys K: Clone + Ord and associated data T.
• Persistent Identification: Operations return stable usize identifiers (except where explicitly stated as a side effect).

Implementation

TrailTree is implemented as a recursive, tertiary, AVL search tree—such that the Equal child of each element is the root of its subtree—stored on top of an object pool.

Time

Efficiencies are expressed in terms of fundamental operations—complex operations will need to be multiplied by path length or number of operations. The term n refers to the number of elements in the local tree, while m refers to the number of elements in the complete subtree.

• Insert—binary search + rebalance, O(log n)
• Delete—subtree deletion + rebalance, O(m + log n)
• Relocate—binary search + rebalance (x2), O(log n)
• Key Search—binary search, O(log n)
• Enumeration—exhaustive iteration, O(n)
• Sibling key traversal—subtree traversal, O(log n)
• Upward traversal—O(1)
• Access—O(1)

Memory

TrailTree trades some memory overhead for improved time efficiency, resulting in nonoptimal memory usage. Update operations may incur memory spikes due to the use of an underlying Vec.

Caching

While the structure uses continuous memory, the positions of related elements are not guaranteed to be cache efficient.

Example

use trailtree::TrailTree;

let mut tree = TrailTree::<u32, ()>::new();

// Insert a path into the tree
let leaf = tree.insert(&[10, 12, 2]);

// Retrieve the path associated with the leaf
assert_eq!(&tree.path(leaf), &[10, 12, 2]);

When to Use

TrailTree is best suited for workloads where paths are queried incrementally, subtrees are traversed frequently, and element identity must remain stable across mutations.

• File systems
• Namespaces
• Type systems
• Organizational charts

Structs

TrailTree

A hierarchical search tree structure for efficiently searching paths. Operates over locally-unique, searchable keys K with associated data T.