🌲 Link-Cut Tree

Explore the link-cut tree, an advanced data structure that maintains a dynamic forest of rooted trees under fast link, cut, and path-query operations using splay-tree-based preferred-path decomposition.

Algorithms & AI3DModerate60 FPS

The simulator demonstrates how a link-cut tree decomposes a dynamic forest into preferred paths represented as splay trees, and how access, link, and cut operations splice these paths together to keep path queries fast even as the forest's shape changes.

🔬 What It Demonstrates

🎮 How to Use

Add nodes to build a forest, then use link to attach one tree under another and cut to detach a subtree. Trigger an access on any node to see the preferred path from that node to its root highlighted, and watch the underlying splay-tree reorganization happen step by step. Run a path query, such as minimum edge weight, between two nodes to see the access operation used to answer it.

💡 Did You Know?

A single access operation in a link-cut tree can restructure the entire preferred-path decomposition along the way to the root, yet the amortized cost still works out to logarithmic time, the same trick that makes ordinary splay trees efficient despite occasionally expensive individual operations.

⚙ Under the hood

link-cut-treedata-structuressplay-treeamortized-analysisdynamic-treesgraph-algorithms

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install