Top Tree

Top tree is a hierarchical dynamic tree data structure within computation and algorithms that maintains a dynamic forest of unrooted trees under edge insertions (Link), edge deletions (Cut), vertex and edge weight updates, and both path-based and subtree-based aggregation queries in O(log n) time per operation. Developed by Danish computer scientists Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup in 1997 (and published in archival form in 2005), the top tree unifies and generalizes the capabilities of Sleator and Tarjan's link/cut tree, Frederickson's topology trees, and Henzinger and King's Euler tour tree under a clean algebraic interface based on clusters and two local contraction primitives: rake and compress.

Whereas a link/cut tree decomposes a rooted tree into vertex-disjoint preferred paths (making path queries natural but whole-subtree aggregation over arbitrary high-degree vertices awkward without auxiliary tree-transformation tricks), and an Euler tour tree linearizes Euler tours into balanced search trees (supporting whole-subtree sums easily but lacking path queries), a top tree decomposes an unrooted tree recursively by contracting edges into connected subtrees called clusters that communicate with the rest of the tree through at most two boundary vertices.

Boundary Vertices and Cluster Types

Let T = (V, E) be an unrooted tree containing n vertices and n − 1 edges. For any connected edge-induced subgraph (subtree) C ⊆ T containing at least one edge, a vertex v ∈ V(C) is called a boundary vertex of C if v is incident to at least one edge of T \ C (or if v has been explicitly designated as an external terminal vertex of T). We denote the set of boundary vertices of C by ∂C.

A cluster is a connected edge-induced subgraph C ⊆ T that has at most two boundary vertices (1 ≤ |∂C| ≤ 2):

1. Path Cluster (|∂C| = 2): A cluster C with two distinct boundary vertices ∂C = {a, b}. The unique simple path π(a, b) between a and b inside C is called the cluster path of C. Every edge of T outside C attaches to C only through a or b, while all vertices of C \ {a, b} are internal vertices that have zero incident edges outside C.
2. Point Cluster (|∂C| = 1): A cluster C with only one boundary vertex ∂C = {a} (or 0 boundary vertices at the final root of the hierarchy if no external terminals are designated, in which case one vertex a is retained as its representative boundary). A point cluster acts as a rooted subtree hanging off vertex a; its cluster path has length zero (the single vertex a).

At the base of the hierarchy, every individual edge e = (u, v) ∈ E forms an atomic leaf cluster containing that single edge, with boundary ∂e = {u, v} (if both u and v have degree > 1) or ∂e = {u} (if v is a leaf of T with degree 1).

Rake and Compress Cluster Contractions

A top tree ℜ_T over an unrooted tree T is a binary tree of height O(log n) whose nodes represent clusters of T:

• The leaves of ℜ_T are the n − 1 individual edges of T.
• The root of ℜ_T is a single cluster representing the entire tree T.
• Every internal node C of ℜ_T is the edge-disjoint union C = A ∪ B of two child clusters A and B that share a single common vertex V(A) ∩ V(B) = {v} such that A ∪ B itself has at most two boundary vertices in T.

Depending on the boundary types of A and B, merging A and B across their shared vertex v corresponds to one of two classical tree-contraction operations (Miller and Reif, 1985):

1. Compress(A, B): Two path clusters A (with boundary {a, v}) and B (with boundary {v, b}) share the middle vertex v, and v has no other incident edges in T outside A ∪ B (so v is not a boundary vertex of A ∪ B). Merging A and B hides the degree-2 boundary vertex v as an internal vertex and produces a combined path cluster C = A ∪ B with boundary ∂C = {a, b} whose cluster path is the concatenation π(a, v) · π(v, b).
2. Rake(A, B): A point cluster A with single boundary vertex ∂A = {v} shares v with another cluster B (which may be either a path cluster with boundary {v, b} or a point cluster with boundary {v}). Merging A into B folds the hanging subtree A onto boundary vertex v of B, producing a cluster C = A ∪ B with the same boundary vertices as B.

Because every rake eliminates a degree-1 leaf cluster and every compress eliminates a degree-2 chain vertex, applying a maximal independent set of non-overlapping rakes and compresses reduces the number of remaining clusters in any tree by a constant fraction (at least 1/8) per level. Consequently, any tree T of n vertices admits a balanced top tree ℜ_T of height O(log n) with 2n − 3 cluster nodes.

A major software-engineering advantage of top trees is that an algorithm designer never needs to manipulate internal tree rotations or splay steps directly. Instead, the user defines what summary information (such as path length, maximum edge weight, subtree weight sum, or distance moments) to store inside each cluster C, and supplies four constant-time callback procedures:

• Create(e): Initializes the summary data for an atomic single-edge leaf cluster e = (u, v).
• Join(A, B): Given two child clusters A and B being merged by a rake or compress, computes the summary data of the parent cluster C = A ∪ B in O(1) time from the summaries of A and B.
• Split(C): Before a parent cluster C = A ∪ B is broken apart during a dynamic update or lazy path update, propagates any lazy modifiers (such as "+Δ to all edges on the cluster path of C" or "+Δ to all vertices in the subtree C") down to children A and B in O(1) time.
• Destroy(e): Cleans up an atomic leaf cluster when edge e is deleted.

In addition, the top tree supports Expose(u, v), which temporarily designates vertices u and v as the external boundary vertices of the root cluster T in O(log n) time. After Expose(u, v), the cluster path of the root cluster of ℜ_T is the simple path between u and v in T, allowing any path aggregate or lazy path update between u and v to be read or applied at the root cluster in O(1) time!

Beyond local path and subtree sums, Alstrup et al. equipped top trees with a binary-search guided navigation primitive called Select. Suppose we seek a global optimal vertex in a dynamic weighted tree T, such as:

• The tree center: the vertex v* minimizing max_{u ∈ V} dist(v*, u).
• The tree median: the vertex v* minimizing ∑_{u ∈ V} weight(u) · dist(v*, u).

Both objective functions are convex along any path in T. Starting at the root cluster C = T of the top tree, the algorithm inspects the two child clusters A and B sharing boundary vertex v. Using the precomputed cluster summaries of A and B (together with a summary of the complement T \ A maintained top-down during the descent), a constant-time oracle determines whether the global optimum v* lies inside cluster A or inside cluster B. Stepping into the chosen child cluster at each level of ℜ_T locates the global center or median of the entire dynamic tree in O(log n) time per query!

Two primary architectures are used to implement top trees in practice:

1. Multi-Level Topology-Tree Representation (Alstrup et al., 2005): Maintains explicit levels of rake and compress pairings so that the height of ℜ_T is O(log n) in the worst case. Each Link(u, v) or Cut(e) affects O(1) clusters per level, performing O(log n) calls to Split, Destroy, Create, and Join in the worst case.
2. Self-Adjusting Top Trees (Splay Top Trees / Holm, Tarjan, Thorup, and Werneck, 2005–2019): Represents the rake and compress hierarchy using two interleaved families of splay trees (compress trees for preferred paths and rake trees for hanging point clusters), achieving O(log n) amortized time per operation with much smaller constant factors and without maintaining explicit level invariants.

How does a top tree differ from Frederickson's topology tree?

Greg Frederickson's topology trees (1985) pioneered hierarchical cluster decomposition for dynamic minimum spanning trees, but required the underlying tree T to have maximum vertex degree ≤ 3. Whenever a vertex in T had degree d > 3, topology trees had to replace that vertex with a cycle or binary tree of d dummy vertices connected by zero-weight dummy edges (ternarization), which complicated user algorithms and distorted path structures. A top tree handles arbitrary vertex degrees directly by allowing unlimited sequential rakes of point clusters onto a single shared boundary vertex via a balanced binary rake tree.

How is dynamic tree diameter maintained in O(log n) time per Link and Cut?

Inside every cluster C with boundary ∂C = {a, b} (or {a}), the user summary stores four numbers: the length len(C) of the cluster path between a and b, the maximum distance maxDist(a, C) from boundary a to any vertex inside C, the maximum distance maxDist(b, C) from boundary b to any vertex inside C, and the internal diameter diam(C) of C. When Join(A, B) merges two child clusters across shared vertex v, the new internal diameter is simply max(diam(A), diam(B), maxDist(v, A) + maxDist(v, B)), computed in O(1) additions and comparisons!

Can top trees maintain dynamic 2-edge-connected and biconnected components?

Yes. Holm, de Lichtenberg, and Thorup (2001) combined top trees with hierarchical edge-level invariants to maintain fully dynamic connectivity in O(log² n) amortized time, 2-edge connectivity in O(log⁴ n) amortized time, and biconnectivity in polylogarithmic amortized time per edge insertion or deletion in general undirected graphs.

1. Alstrup, S., Holm, J., de Lichtenberg, K., & Thorup, M. (2005). "Maintaining information in fully dynamic trees with top trees." ACM Transactions on Algorithms, 1(2), 243–264. https://doi.org/10.1145/1103963.1103966
2. Sleator, D. D., & Tarjan, R. E. (1983). "A data structure for dynamic trees." Journal of Computer and System Sciences, 26(3), 362–391. https://doi.org/10.1016/0022-0000(83)90006-590006-5)
3. Frederickson, G. N. (1985). "Data structures for on-line updating of minimum spanning trees, with applications." SIAM Journal on Computing, 14(4), 781–798. https://doi.org/10.1137/0214055
4. Tarjan, R. E., & Werneck, R. F. (2005). "Self-adjusting top trees." In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), 813–822. https://doi.org/10.5555/1070432.1070547