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.
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.
Add node, link two trees, cut an edge, access a node to view its preferred path, run a path query (such as minimum edge weight) between two selected nodes, and toggle a step-by-step view of the splay-tree splicing during access.
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.
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.
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.
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.
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.