imsuck's vault

Home

❯

00 Notes

❯

Top Tree

Top Tree

Properties3
categories—
upTree data structure
statusopen

10 Apr 20261 min read

  • atomic
  • cs/dsa
  • moc

A way to decompose a tree into clusters which allows efficient operations on tree—like link, cut, query path, query subtree, search for a vertex.

TODO: write more about clusters and stuff

Related

Link-cut Tree: a light-weight alternative of top trees for when only path operations are needed.

Applications

Self-adjusting top tree
Splay top tree
Online dynamic connectivity

References

Paper by Holm and Lichtenberg


Graph View

Backlinks

  • Link-cut Tree

Created with Quartz © 2026

  • GitHub
  • Discord Community