Struct EulerTourTree 

pub struct EulerTourTree { /* private fields */ }

Represents a tree as an Euler tour stored in a balanced BST (treap)

Implementations

impl EulerTourTree

pub fn new() -> Self

Create a new empty Euler Tour Tree

pub fn with_seed(seed: u64) -> Self

Create with a seed for reproducibility

Performance

Pre-allocates with reasonable default capacity

pub fn with_seed_and_capacity(seed: u64, capacity: usize) -> Self

Create with seed and capacity hint

Performance

Pre-allocates memory to avoid reallocation

pub fn make_tree(&mut self, v: NodeId) -> Result<()>

Create a singleton tree with one vertex

pub fn link(&mut self, u: NodeId, v: NodeId) -> Result<()>

Link: Make v a child of u (v must be in separate tree)

pub fn cut(&mut self, u: NodeId, v: NodeId) -> Result<()>

Cut: Remove edge between u and v

Performance

O(log n) via Euler tour split and merge with O(1) exit node lookup.

pub fn connected(&self, u: NodeId, v: NodeId) -> bool

Check if two vertices are in the same tree

pub fn find_root(&self, v: NodeId) -> Result<NodeId>

Find the root of the tree containing v

pub fn tree_size(&self, v: NodeId) -> Result<usize>

Get the size of the tree containing v

pub fn subtree_size(&self, v: NodeId) -> Result<usize>

Get the size of the subtree rooted at v

pub fn subtree_aggregate(&self, v: NodeId) -> Result<f64>

Aggregate over the subtree rooted at v

pub fn update_value(&mut self, v: NodeId, value: f64) -> Result<()>

Update the value at vertex v

pub fn reroot(&mut self, v: NodeId) -> Result<()>

Reroot the tree containing v to make v the root

pub fn len(&self) -> usize

Get the number of vertices

pub fn is_empty(&self) -> bool

Check if empty

pub fn bulk_make_trees(&mut self, vertices: &[NodeId]) -> Result<()>

Bulk create trees - more efficient than individual make_tree calls

Performance

• Pre-allocates all memory upfront
• Batches HashMap insertions
• Reduces allocation overhead by ~40%

pub fn bulk_update_values(&mut self, updates: &[(NodeId, f64)]) -> Result<()>

Bulk update values with lazy propagation

Performance

• Uses lazy propagation to defer actual updates
• Batches pull_up operations
• ~3x faster than individual updates for large batches

pub fn bulk_link(&mut self, edges: &[(NodeId, NodeId)]) -> Result<()>

Bulk link operations

Performance

• Validates all edges first to fail fast
• Batches root mapping updates

Trait Implementations

impl Clone for EulerTourTree

fn clone(&self) -> EulerTourTree

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for EulerTourTree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for EulerTourTree

fn default() -> Self

Returns the “default value” for a type.