Dynamic Trees:Introduction and Linking and Cutting Trees

Introduction

In this chapter we consider the problem of maintaining properties of a collection of vertex- disjoint trees that change over time as edges are added or deleted. The trees can be rooted or free, and vertices and edges may be associated with real-valued costs that may change as well. A straightforward solution would be to store explicitly with each vertex its parent and cost, if any: with this representation each update would cost only O(1) time, but answering queries would be typically proportional to the size or to the depth of the tree, which may be linear in the worst case. By representing the structure of the trees implicitly, one can reduce the query time while slightly increasing the update time. The typical achieved bounds are logarithmic in the number of vertices of the forest, either in the worst-case or amortized over a sequence of operations.

While the basic tree update operations are edge insertions, edge deletions, and possibly vertex/edge cost changes, many properties of dynamically changing trees have been con- sidered in the literature. The basic query operation is tree membership: while the forest of trees is dynamically changing, we would like to know at any time which tree contains a given vertex, or whether two vertices are in the same tree. Dynamic tree membership is a special case of dynamic connectivity in undirected graphs, and indeed in Chapter 36 we will see that some of the data structures developed here for trees are used to solve the more general problem on graphs. We remark that, if only edge insertions are allowed, the tree membership problem is equivalent to maintaining disjoint sets under union operations and thus the well known set union data structures can solve it [17]. In this chapter we will instead consider the problem in a fully dynamic setting, in which also edge deletions are allowed, and present efficient data structures such as the linking and cutting trees of Sleator and Tarjan [15] and the topology trees of Frederickson [6].

Other properties that have been considered are finding the least common ancestor of two vertices, the center, the median, or the diameter of a tree [1, 2, 15]. When costs are associated either to vertices or to edges, one could also ask what is the minimum or maximum cost in a given path. A variant of topology trees, known as top trees [1], are especially well suited at maintaining this kind of path information.

ET trees, first introduced in [18] and much used in [10], allow it to deal easily with forests whose vertices are associated with weighted or unweighted keys, supporting, e.g., minkey queries, which require to return a key of minimum weight in the tree that contains a given vertex. Reachability trees, introduced by Even and Shiloach in [5], support instead distance and shortest path queries and have been widely used to solve dynamic path problems on directed graphs (see, e.g., [10, 12]).

Linking and Cutting Trees

In this section we present a data structure due to Sleator and Tarjan [15] useful to maintain a collection of rooted trees, each of whose vertices has a real-valued cost, under an arbitrary sequence of the following operations:

• maketree(v): initialize a new tree consisting of a single vertex v with cost zero.

• findroot(v): return the root of the tree containing vertex v.

• findcost(v): return a vertex of minimum cost in the path from v to findroot(v).

• addcost(v, δ): add the real number δ to the cost of every vertex in the path from v to findroot(v).

• link(v, w): merge the trees containing vertices v and w by inserting edge (v, w).

This operation assumes that v and w are in different trees and that v is a tree root.

• cut(v): delete the edge from v to its parent, thus splitting the tree containing vertex v into two trees. This operation assumes that v is not a tree root.

The data structure of Sleator and Tarjan is known as linking and cutting trees and sup- ports all the above operations in O(log n) time, by representing the structure of the trees implicitly. Other operations that can be supported within the same time bound are changing the root of a tree, finding the parent of a vertex, and finding the least common ancestor of two vertices. In particular, the possibility of making a given vertex v root of a tree makes the data structure powerful enough to handle problems requiring linking and cutting of free (i.e., unrooted) trees. Furthermore, the same time bounds can be obtained when real costs are associated with edges rather than with vertices.

The rest of this section is organized as follows. In Section 35.2.1 we show how to implement the operations given above using simpler primitives defined on paths (rather than on trees), and in Section 35.2.2 we describe the implementation of these primitives on paths. For simplicity, we only describe a solution that achieves O(log n) amortized (rather than worst-case) time per operation. Details of all these results may be found in [15].

Using Operations on Vertex-Disjoint Paths

In this section we show the reduction between the operations on trees and a suitable collection of operations on vertex-disjoint paths. Assume we know how to perform the following operations:

• makepath(v): initialize a new path consisting of a single vertex v with cost zero;

• findpath(v): return the path containing vertex v;

• findpathtail(p): return the tail (last vertex) of path p;

• findpathcost(p): return a vertex of minimum cost in path p;

• addpathcost(p, δ): add the real value δ to the cost of every vertex in path p;

• join(p, v, q): merge path p, vertex v, and path q into a single path by inserting one edge from the tail of p to v, and one edge from v to the head (first vertex) of q, and return the new path. Either p or q can be empty;

• split(v): divide the path containing vertex v into at most three paths by deleting the edges incident to v. Return the two new paths p (containing all the vertices before v) and q (containing all the vertices after v). Again, either p or q can be empty.

In order to solve the problem of linking and cutting trees, we partition each tree into a set of vertex disjoint paths. Each tree operation will be defined in terms of one or more path operations. This partition is defined by allowing each tree edge to be either solid or dashed and by maintaining the invariant that at most one solid edge enters each vertex (we consider an edge oriented from a child to its parent). Removing dashed edges therefore partitions the tree into vertex-disjoint solid paths . Dashed edges are represented implicitly: we associate with each path p its successor , that is the vertex entered by the dashed edge leaving the tail of p. If the tail of p is a root, successor(p) is null . Each path will be represented by a vertex on it (an empty path being represented by null ). In order to convert dashed edges to solid (and vice-versa) we will be using the following operation:

• expose(v): make the tree path from v to findroot(v) solid. This is done by converting dashed edges in the path to solid, and solid edges incident to the path to dashed. Return the resulting solid path.

Now we describe how to implement tree operations in terms of path operations:

• a maketree(v) is done by a makepath(v) followed by setting successor(v) to null ;

• a findroot(v) is a findpathtail(expose(v));

• a findcost(v) is a findpathcost(expose(v));

• an addcost(v, δ) is an addpathcost(expose(v), δ);

• a link(v, w) is implemented by performing first an expose(v) that makes v into a one-vertex solid path, then an expose(w) that makes the path from w to its root solid, and then by joining these two solid paths: in short, this means assigning null to successor(join(null,expose(v),expose(w)));

• to perform a cut(v), we first perform an expose(v), which leaves v with no entering solid edge. We then perform a split(v), which returns paths p and q:

since v is the head of its solid path and is not a tree root, p will be empty, while q will be non-empty. We now complete the operation by setting both successor(v) and successor(q) to null .

To conclude, we need to show how to perform an expose, i.e., how to convert all the dashed edges in the path from a given vertex to the tree root to solid maintaining the invariant that at most one solid edge enters each vertex. Let x be a vertex of this path such that the edge from x to its parent w is dashed (and thus w = successor(x)). What we would like to do is to convert edge (x, w) into solid, and to convert the solid edge previously entering w (if any) into dashed. We call this operation a splice. The pseudocode in Figure 35.1 implements expose(v) as a sequence of splices.

Path p, initialized to be

empty, at the end of the execution will contain the solid path from v to findroot(v). Each iteration of the while loop performs a splice at v by converting to solid the edge from the tail of p to v (if p j= null ) and to dashed the edge from the tail of q to v (if q j= null ). A step-by-step execution of expose on a running example is shown in Figure 35.2.

From the description above, each tree operation takes O(1) path operations and at most one expose. Each splice within an expose requires O(1) path operations. Hence, in order to compute the running time, we need first to count the number of splices per expose and then to show how to implement the path operations. With respect to the former point, Sleator and Tarjan prove that a sequence of m tree operations causes O(m log n) splices, and thus O(log n) splices amortized per expose.

THEOREM 35.1 [15] Any sequence of m tree operations (including n maketree) re- quires O(m) path operations and at most m expose. The exposes can be implemented with O(m log n) splices, each of which requires O(1) path operations.

Implementing Operations on Vertex-Disjoint Paths

We now describe how to represent solid paths in order to implement efficiently tree operations. Each solid path is represented by a binary tree whose nodes in symmetric order are the vertices in the path; each node x contains pointers to its parent p(x), to its left child l(x), and to its right child r(x). We call the tree representing a solid path a solid tree. The vertex representing a solid path is the root of the corresponding solid tree, and thus the root of the solid tree contains a pointer to the successor of the path in the dynamic tree.

Vertex costs are represented as follows. Let cost(x) be the cost of vertex x, and let mincost(x) be the minimum cost among the descendants of x in its solid tree. Rather than storing these two values, in order to implement addcost operations efficiently, we store at x the incremental quantities ∆cost(x) and ∆min(x) defined as follows:

An example of this representation is given in Figure 35.3.

Given ∆cost and ∆min, we can compute mincost(x) by summing up ∆min for all vertices in the solid tree path from the root to x, and cost(x) as mincost(x) + ∆cost(x). Moreover, note that ∆cost(x) = 0 if and only if x is a minimum cost node in the subtree rooted at x. If this is not the case and the minimum cost node is in the right subtree, then ∆min(r(x)) = 0; otherwise ∆min(l(x)) = 0. With this representation, rotations can be still implemented in O(1) time.

The path operations can be carried out as follows:

FIGURE 35.2: Effect of expose(v). (a) The original decomposition into solid paths; (b–e) vertices and paths after the execution of line 5 in the four consecutive iterations of the while loop; (f) the decomposition into solid paths after expose(v).

• makepath(v): initialize a binary tree of one vertex v with ∆min(v) = 0 and ∆cost(v) = 0.

• findpath(v): starting from v, follow parent pointers in v’s solid tree until a node with no parent is found. Return this node.

• findpathtail(p): assuming that p is the root of a solid tree, follow right pointers and return the rightmost node in the solid tree.

• findpathcost(p): initialize v to p and repeat the following step until ∆cost(v) = 0: if v has a right child and ∆min(r(v)) = 0, replace v by r(v); otherwise, replace

FIGURE 35.3: Representing solid paths with binary trees. (a) A solid path and its vertex costs; (b) solid tree with explicit costs (the bold value is cost(v) and the italic value is mincost(v)); (c) corresponding solid tree with incremental costs (the bold value is ∆cost(v) and the italic value is ∆min(v)).

v by l(v). At the end, return v.

• addpathcost(p, δ): add δ to ∆min(p).

• join(p, v, q): join the solid trees with roots p, v and q.

• split(v): split the solid tree containing node v.

We observe that operations findpath, findpathtail and findpathcost are essentially a look up in a search tree, while split and join are exactly the same operations on search trees. If we represent solid paths by means of balanced search trees, the time per path operation becomes O(log n), and by Theorem 35.1 any sequence of m tree operations can be supported in O(m(log n)2) time. Using self-adjusting binary search trees [16] to represent solid paths, together with a more careful analysis, yields a better bound:

THEOREM 35.2 [15] Any sequence of m tree operations (including n maketree) requires O(m log n) time.

Insights on the use of self-adjusting binary search trees in the implementation of path operations are given in Chapter 12.

Using biased search trees [3], the O(log n) amortized bound given in Theorem 35.2 can be made worst-case. Details can be found in [15].