Expand description
A safe, indexed, n-ary tree implementation
§About
This module using arena-like backing primarily as an easy way to provide safe node referencing to mutable tree structures in a way that avoids complex lifetime management, overly-restrictive API design, and the runtime overhead of reference counting.
Compromises over the link-based tree include being less spatially efficient as the arena’s growth algorithm logically shifts “pointers” to Nodes in the arena.
§Design
The implementation stores all Node values in a flat Vec-backed arena. For small trees (fewer than ~100 nodes), it is marginally slower than the Rc<RefCell>-based design due to fixed arena management overhead. However, for larger trees (starting around 1,000–10,000 nodes), it improves construction speed by roughly 20–25%, primarily from reduced heap allocations and better cache locality.
§Drawbacks
This implementation includes several critical compromises over a more traditional link-based approach. This Vec-backed design is intended to provide a more ergonomic design over reference counted alternatives with interior mutability, as well as raw pointer-based designs with complex lifetime management and restrictive APIs. Unfortunately, this Vec-backed design also comes with its own compromises. The Vec-backed design is far less spatially efficient due to the structure’s growth. As the tree gets mutated, it also potentially loses cache locality.
§Example