Module euler

ruvector_mincut

Module euler 

Source
Expand description

Euler Tour Trees for dynamic tree operations

Provides O(log n) operations for:

  • Dynamic connectivity queries
  • Subtree aggregation
  • Edge insertion/deletion in trees

§Overview

An Euler Tour Tree (ETT) represents a tree as a sequence of vertices encountered during an Euler tour (DFS traversal). Each edge (u, v) contributes two occurrences: entering and exiting the subtree rooted at v.

The sequence is stored in a balanced BST (treap) with implicit keys, where position = size of left subtree. This enables:

  • O(log n) split at any position
  • O(log n) merge of two sequences
  • O(log n) subtree aggregation via range queries

§Performance Optimizations

This implementation includes:

  • Optimized treap balancing with better priority generation (xorshift64)
  • Bulk operations for batch updates with reduced overhead
  • Lazy propagation for efficient subtree operations
  • Inline hints for hot path functions
  • Pre-allocation to reduce memory allocations
  • Improved split/merge algorithms with better cache locality

§Example

use ruvector_mincut::euler::EulerTourTree;

let mut ett = EulerTourTree::new();

// Create trees
ett.make_tree(1).unwrap();
ett.make_tree(2).unwrap();
ett.make_tree(3).unwrap();

// Link them: 1 - 2 - 3
ett.link(1, 2).unwrap();
ett.link(2, 3).unwrap();

// Check connectivity
assert!(ett.connected(1, 3));

// Get tree size
assert_eq!(ett.tree_size(1).unwrap(), 3);

Structs§

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

Type Aliases§

NodeId
Node identifier