Top tree

A top tree is a data structure based on a binary tree for unrooted dynamic trees that is used mainly for various path-related operations. It allows simple divide-and-conquer algorithms. It has since been augmented to maintain dynamically various properties of a tree such as diameter, center and median.
A top tree is defined for an underlying tree and a set of at most two vertices called as [|External Boundary Vertices]
Image:Top tree.jpg|thumb|250px|An image depicting a top tree built on an underlying tree. A tree divided into edge [|clusters] and the complete top-tree for it. Filled nodes in the top-tree are path-clusters, while small circle nodes are leaf-clusters. The big circle node is the root. Capital letters denote clusters, non-capital letters are nodes.

Glossary

Boundary Node

See [|Boundary Vertex]

Boundary Vertex

A vertex in a connected subtree is a Boundary Vertex if it is connected to a vertex outside the subtree by an edge.

External [|Boundary Vertices]

Up to a pair of vertices in the top tree can be called as External Boundary Vertices, they can be thought of as Boundary Vertices of the cluster which represents the entire top tree.

Cluster

A cluster is a connected subtree with at most two Boundary Vertices.
The set of Boundary Vertices of a given cluster is denoted as
With each cluster the user may associate some meta information and give methods to maintain it under the various [|internal operations].

Path Cluster

If contains at least one edge then is called a Path Cluster.

Point Cluster

See [|Leaf Cluster]

Leaf Cluster

If does not contain any edge i.e. has only one Boundary Vertex then is called a Leaf Cluster.

Edge Cluster

A Cluster containing a single edge is called an Edge Cluster.

Leaf Edge Cluster

A Leaf in the original Cluster is represented by a Cluster with just a single Boundary Vertex and is called a Leaf Edge Cluster.

Path Edge Cluster

Edge Clusters with two Boundary Nodes are called Path Edge Cluster.

Internal Node

A node in is called an Internal Node of.

Cluster Path

The path between the Boundary Vertices of is called the cluster path of and it is denoted by

Mergeable Clusters

Two Clusters and are Mergeable if is a singleton set and is a Cluster.

Introduction

Top trees are used for maintaining a Dynamic forest under link and cut operations.
The basic idea is to maintain a balanced Binary tree of logarithmic height in the number of nodes in the original tree ; the top tree essentially represents the recursive subdivision of the original tree into clusters.
In general the tree may have weight on its edges.
There is a one-to-one correspondence with the edges of the original tree and the leaf nodes of the top tree and each internal node of represents a cluster that is formed due to the union of the clusters that are its children.
The top tree data structure can be initialized in time.
Therefore the top tree over is a binary tree such that

The nodes of are clusters of ;
The leaves of are the edges of ;
Sibling clusters are neighbours in the sense that they intersect in a single vertex, and then their parent cluster is their union.
Root of is the tree itself, with a set of at most two External Boundary Vertices.

A tree with a single vertex has an empty top tree, and one with just an edge is just a single node.
These trees are freely augmentable allowing the user a wide variety of flexibility and productivity without going into the details of the internal workings of the data structure, something which is also referred to as the Black Box.

Dynamic Operations

The following three are the user allowable Forest Updates.

Link: Where and are vertices in different trees and. It returns a single top tree representing
Cut: Removes the edge from a tree with top tree thereby turning it into two trees and and returning two top trees and.
Expose: Is called as a subroutine for implementing most of the queries on a top tree. contains at most 2 vertices. It makes original external vertices to be normal vertices and makes vertices from the new External Boundary Vertices of the top tree. If is nonempty it returns the new Root cluster with Expose fails if the vertices are from different trees.
Internal Operations

The Forest updates are all carried out by a sequence of at most Internal Operations, the sequence of which is computed in further time. It may happen that during a tree update, a leaf cluster may change to a path cluster and the converse. Updates to top tree are done exclusively by these internal operations.
The is updated by calling a user defined function associated with each internal operation.
;: Here and are Mergeable Clusters, it returns as the parent cluster of and and with boundary vertices as the boundary vertices of Computes using and
;: Here is the root cluster It updates and using and then it deletes the cluster from.
Split is usually implemented using method which calls user method for updates of and using and updates such that it's known there is no pending update needed in its children. Then the is discarded without calling user defined functions. Clean is often required for queries without need to Split.
If Split does not use Clean subroutine, and Clean is required, its effect could be achieved with overhead by combining Merge and Split.
The next two functions are analogous to the above two and are used for base clusters.
;: Creates a cluster for the edge Sets is computed from scratch.
;: is the edge cluster User defined function is called to process and then the cluster is deleted from the top tree.

Non local search

User can define Choose operation which for a root cluster selects one of its child clusters. The top tree blackbox provides Search routine, which organizes Choose queries and reorganization of the top tree such that it locates the only edge in intersection of all selected clusters. Sometimes the search should be limited to a path. There is a variant of nonlocal search for such purposes.
If there are two external boundary vertices in the root cluster, the edge is searched only on the path. It is sufficient to do following modification: If only one of root cluster children is path cluster, it is selected by default without calling the Choose operation.

Examples of non local search

Finding i-th edge on longer path from to could be done by =Expose followed by Search with appropriate Choose. To implement the Choose we use global variable representing and global variable representing. Choose selects the cluster with iff length of is at least. To support the operation the length must be maintained in the.
Similar task could be formulated for graph with edges with nonunit lengths. In that case the distance could address an edge or a vertex between two edges. We could define Choose such that the edge leading to the vertex is returned in the latter case. There could be defined update increasing all edge lengths along a path by a constant. In such scenario these updates are done in constant time just in root cluster. Clean is required to distribute the delayed update to the children. The Clean should be called before the Choose is invoked. To maintain length in would in that case require to maintain unitlength in as well.
Finding center of tree containing vertex could be done by finding either bicenter edge or edge with center as one endpoint. The edge could be found by =Expose followed by Search with appropriate Choose. The choose selects between children with the child with higher maxdistance. To support the operation the maximal distance in the cluster subtree from a boundary vertex should be maintained in the. That requires maintenance of the cluster path length as well.

Interesting Results and Applications

A number of interesting applications originally implemented by other methods have been easily implemented using the top tree's interface. Some of them include

. We can maintain a dynamic collection of weighted trees in time per link and cut, supporting queries about the maximum edge weight between any two vertices in time.
*Proof outline: It involves maintaining at each node the maximum weight on its cluster path, if it is a point cluster then is initialised as When a cluster is a union of two clusters then it is the maximum value of the two merged clusters. If we have to find the max wt between and then we do and report
. In the scenario of the above application we can also add a common weight to all edges on a given path · · · in time.
*Proof outline: We introduce a weight called extra to be added to all the edges in Which is maintained appropriately ; split requires that, for each path child of, we set and. For := join, we set and. Finally, to find the maximum weight on the path · · ·, we set and return.
. We can ask for the maximum weight in the underlying tree containing a given vertex in time.
*Proof outline: This requires maintaining additional information about the maximum weight non cluster path edge in a cluster under the Merge and Split operations.
The distance between two vertices and can be found in time as.
*Proof outline:We will maintain the length length of the cluster path. The length is maintained as the maximum weight except that, if is created by a join, length is the sum of lengths stored with its path children.
Queries regarding diameter of a tree and its subsequent maintenance takes time.
The Center and Median can me maintained under Link and Cut operations and queried by non local search in time.
Top trees are used in state-of-the-art algorithms for dynamic two-edge connectivity. In this problem, similarly to dynamic connectivity, the graph is subject to edge deletions and insertions, as well as queries asking whether a pair of vertices are two-edge connected, or there is a bridge separating them. Holm, de Lichtenberg, and Thorup give a deterministic algorithm with amortized update time, and query time. Subsequent work by Holm, Rotenberg, and Thorup improves this to an amortized update time of, also using top trees
The graph could be maintained allowing to update the edge set and ask queries on vertex 2-connectivity. Amortized complexity of updates is. Queries could be implemented even faster. The algorithm is not trivial, uses space.
Top trees can be used to compress trees in a way that is never much worse than DAG compression, but may be exponentially better.