Dynamic Trees:Top Trees

Top Trees

Top trees have been introduced by Alstrup et al. [1] to maintain efficiently information about paths in trees, such as, e.g., the maximum weight on the path between any pair of vertices in a tree. The basic idea is taken from Frederickson’s topology trees, but instead of partitioning vertices, top trees work by partitioning edges: the same vertex can then appear in more than one cluster. Top trees can be also seen as a natural generalization of standard balanced binary trees over dynamic collections of lists that may be concatenated and split, where each node of the balanced binary tree represents a segment of a list. As we will see, in the terminology of top trees this is just a special case of a cluster.

We follow here the presentation in [2]. Similarly to [6, 7], a cluster is a connected subtree of the dynamic tree T , with the additional constraint that at most two vertices, called boundary vertices, have edges out of the subtree. We will denote the boundary of a cluster C as δC. If the boundary contains two vertices u and v, we call cluster path of C the unique path between u and v in T and we denote it as π(C). If |δC < 2|, then π(C) = ∅. Two clusters C1 and C2 are called neighbors if their intersection contains exactly one vertex:

since clusters are connected and have no edges in common, the intersection vertex must be in δC1 ∩ δC2. It is also possible to define a boundary δT , consisting of one or two vertices, for the entire tree T : we will call such vertices, if any, external boundary vertices. If external boundary vertices are defined, we have to extend the notion of boundary of a cluster: namely, if a cluster C contains an external boundary vertex v, then v ∈ δC even if

v has no edge out of C.

DEFINITION 35.3 A top tree T over a pair (T, δT ) is a binary tree such that:

• The leaves of T are the edges of T .

• The internal nodes of T are clusters of T .

• The subtree represented by each internal node is the union of the subtrees represented by its two children, which must be neighbors.

• The root of T represents the entire tree T .

• The height of T is O(log n), where n is the number of vertices of T .

A tree with a single node has an empty top tree.

Figure 35.6 shows the clusters at different levels of the recursive partition and the corresponding top tree. Note that a vertex can appear in many clusters, as many as Θ(n) in the worst case. However, it can be a non-boundary vertex only in O(log n) clusters. Indeed, for each vertex v which is neither an external boundary vertex nor a leaf in T , there exists a unique cluster C with children A and B such that v ∈ δA, v ∈ δB, and v j∈ δC. Then v is non-boundary vertex only in cluster C and in all its ancestors in the top tree.

A locally greedy approach similar to the one described in Section 35.3.1 for topology trees can be used to build a top tree. The only modifications require to reason in terms of edges, instead of vertices, and to check the condition on the cardinality of the boundary before unioning any two neighboring clusters.

Updates

Given a dynamic forest, top trees over the trees of the forest are maintained under the following operations:

• link(u,v), where u and v are in different trees Tu and Tv of the forest: link trees Tu and Tv by adding edge (u, v);

• cut(e): remove edge e from the forest;

• expose(u,v), where u and v are in the same tree T of the forest: make u and v the external boundary vertices of T and return the new root cluster of the top tree over T .

Top trees can be maintained under these operations by making use of two basic merge and split primitives:

• merge: it takes two top trees whose roots are neighbor clusters and joins them to form a unique top tree;

• split: this is the reverse operation, deleting the root of a given top tree.

The implementation of update operations starts with a sequence of Split of all ancestor clusters of edges whose boundary changes and finishes with a sequence of Merge. In case of insertion and deletions, since an end-point v of an edge has to be already boundary vertex of the edge if v is not a leaf, an update can change the boundary of at most two edges, excluding the edge being inserted/deleted. From [1, 2, 6] we have:

THEOREM 35.4 [1, 2] For a dynamic forest we can maintain top trees of height O(log n) supporting each link, cut, and expose operation with a sequence of O(log n) split and merge. The sequence itself is identified in O(log n) time. The space usage of top trees is linear in the size of the dynamic forest.

Representation and Applications

Top trees are represented as standard binary trees, with pointers to parent and children for each node. With each leaf is associated the corresponding edge in T and with each internal node the at most two boundary vertices of the corresponding cluster. In addition, each vertex v of T has a pointer to the deepest cluster for which v is a non-boundary vertex, or to the root cluster containing v if v is an external boundary vertex. Given this representation, top trees can be used as a black box for maintaining different kinds of information. Typically, the user needs to attach extra information to the top tree nodes and to show how such information can be maintained upon merge and split operations.

A careful choice of the extra information makes it possible to maintain easily path properties of trees, such as the minimum weight of an edge on the path between any two vertices. In this example, the extra information wC associated with a cluster C is the weight of the lightest edge on the cluster path π(C). Before showing how to maintain it, note that if cluster A is a child of cluster C in the top tree and A contains an edge from π(C), then π(A) ⊆ π(C): we call A a path child of C. When a cluster is created by a merge, we store as extra information the minimum weight stored at its path children. In case of a split, we just discard the information. Now, in order to find the minimum weight between any two vertices u and v, we compute the root cluster C of the top tree in which u and v are external boundary vertices by calling expose(u,v). Then π(C) is the path between u and v and wC is exactly the value we are looking for.

Top trees can be used quite easily if the property we wish to maintain is a local property, i.e., being satisfied by a vertex/edge in a tree implies that the property is also satisfied in all the subtrees containing the vertex/edge. Non-local properties appear to be more challenging. For general non-local searching the user has to supply a function select that can be used to guide a binary search towards a desired edge: given the root of a top tree, the function selects one of the two children according to the property to be maintained. Since the property is non-local, in general it is not possible to recurse directly on the selected child as is. However, Alstrup et al. [2] show that the top tree can be temporarily modified by means of a few merge operations so that select can be provided with the “right” input in the recursive call and guide the search to a correct solution.

LEMMA 35.1 Given a top tree, after O(log n) calls to select, merge, and split, there is a unique edge (u, v) contained in all clusters chosen by select, and then (u, v) is returned.

We refer the interested reader to [2] for the proof of Lemma 35.1, which shows how to modify the top tree in order to facilitate calls to select. We limit here to use the search as a black box in order to show how to maintain dynamically the center of a tree (i.e., a vertex which maximizes the distance from any other vertex) using top trees.

The extra information maintained for a cluster C with boundary vertices a and b are: the distance dist(C) between a and b, and the lengths £a(C) and £b(C) of a longest path in C departing from a and b, respectively. Now we show how to compute the extra information for a cluster C obtained by merging two neighboring clusters A and B. Let c be a boundary vertex of cluster C and, w.l.o.g., let c ∈ δA. The longest path from c to a vertex in A has length £c(A). Instead, in order to get from c to a vertex in B, we must traverse a vertex, say x, such that x ∈ δA ∩ δB: thus, the longest path from c to a vertex in B has length dist(c, x) + £x(B). This is equal to £c(B) if c ∈ δB (i.e., if x = c), or to dist(A) + £x(B) if c j∈ δB. Now, we set £c(C) = max{£c(A), dist(c, x) + £x(B)}. We can compute dist(C)

similarly. Finally, function select can be implemented as follows. Given a cluster C with children A and B, let u be the vertex in the intersection of A and B: if £u(A) ≥ £u(B) select picks A, otherwise it picks B. The correctness of select depends on the fact that if £u(A) ≥ £u(B), then A contains all the centers of C. Using Lemma 35.1 we can finally conclude that the center of a tree can be maintained dynamically in O(log n) time.

We refer the interested reader to [1, 2] for other sample applications of top trees, such as maintaining the median or the diameter of dynamic trees. As we will recall in Section 36.5.2, top trees are fundamental in the design of the fastest algorithm for the fully dynamic minimum spanning tree problem [11].