MIT OpenCourseWarehttp://ocw.mit.edu 6.854J / 18.415J Advanced Algorithms Fall 2008��For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.18.415/6.854 Advanced Algorithms October 1, 2008 Lecture 8 Lecturer: Michel X. Goemans Previously, we introduced the dynamic tree data structure and the operations that dynamic trees must support. Today, we take a more detailed look at dynamic trees and describe the efficient implementation of the operations. In doing so, much of our focus will be on the Expose method, an extended splay operation that is essential in all these operations. We show that any sequence of m op e rations on a dynamic tree with n nodes takes O((m + n) log n) time. 1 Dynamic Trees Dynamic trees (also known as link-cut trees) introduced by Sleator and Tarjan are a data structure intended to maintain a representation of a set of rooted trees. We will be able to perform various operations on these trees, to be discussed later. Figure 1 shows an example tree as a virtual tree (left) and a rooted tree (right). 1.1 Rooted Trees We view rooted trees as unions of node-disjoint (directed) paths. This divides the edges of the tree into two sets. Solid edges are those that are on the node-disjoint paths that the tree is composed of, and dashed edges are those that are not on these paths. Note that each path consisting of solid edges is a directed path (we omit the arrows here) from top to bottom. 1.2 Virtual Trees The union of disjoint paths described above can be used to represent virtual trees . In a virtual tree, each solid path is represented by a splay tree such that the following conditions hold: A successor node in a splay tree is an ancestor in the rooted tree. • For each splay tree, its largest node is linked to the parent of the root in the rooted tree. • In the virtual tree, each node has at most one left child, at most one right child, and any • number of middle (virtual) children. There are three kinds of edges in a virtual tree, corresponding to the three types of children a node can have. Left and right children of a node are connected to the node by solid edges, and middle children of a node are connected to it by dashed edges. Note that there can be many virtual trees corresponding to a rooted tree, because there are two different degree s of freedom involved in constructing a virtual tree — the union of disjoint paths could be different, as could the structure of the splay tree s corresponding to the paths. An important consequence of this setup is that rotations in a splay tree do not affect the structure of the ro oted tree. 2 The Expose Operation The Expose(v) operation is an extended splay operation that brings v to the root of the virtual tree without changing the structure of the rooted tree. The important parts of this operation are to 8-1Figure 1: Virtual tree (left) and corresponding rooted tree (right). make sure that the path from v to the root is solid and that the splay tree representing the path to which v belongs is rooted at v. We can describe this operation in three steps. In our example, we run Expose on node 15. 2.1 Step 1 Step 1 consists of walking from v to the root of the virtual tree. Whenever the walk enters a splay tree (solid edges) at some node w, a Splay(w ) operation is performed, bringing w to the root of that tree. Middle children are not affe cted in this step. For instance, we splay nodes 11 and 5 in our example tree as in figure 2. Note that at the end of step 1 of an Expose(v) operation, v will be connected to the ro ot of the virtual tree only by dashed edges. 2.2 Step 2: Splicing Step 2 consists of walking from v to the root of the virtual tree exchanging along the way each middle edge with the left subtree of the parent. This is illustrated in Figure 3 and called splicing. A middle child of a node w and its left child can be exchanged (without changing the rooted tree) only if w is the root of its splay tree. This justifies our execution of step 1 first since at the end of step 1 all edges from v to the root are middle edges. Splicing is a valid operation on virtual trees. Indeed, referring to Figure 3, the left subtree of w in the splay tree corresponds to the part of the solid path that is below w in the rooted tree; this is because w is the root of its splay tree. Exchanging that solid subpath with the solid path corresponding to the splay tree rooted at v still leaves the rooted tree decomposed into a node-disjoint union of paths. Note that after performing this operation on every edge to the root of the virtual tree, there will be a solid path from the root of the rooted tree to the node being exposed. 8-2Figure 2: Walking Up and Splaying. The virtual tree after splaying 15 and 11 is shown on the left. The virtual tree on the right is at the end of step 1, after splaying also node 5. Figure 3: Splicing. w needs to be the root of its splay tree. 8-3Figure 4: Left virtual tree is after first splicing, the right virtual tree is the one at the end of step 2. The result of splicing every node on the path to the root for our example is illustrated in Figure 4. 2.3 Step 3 Step 3 consists of walking from v to the root in the virtual tree, splaying v to the root. Note that in the analysis, we can charge the entire cost of step 2 to the final splaying operation in step 3. Figure 5 shows the rele vant splay tree before and after this step. 3 Operations on Dynamic Trees We will now describe the desired operations on a dynamic tree and how to implement them efficiently using the Expose me thod just defined. Some of these operations require keeping track of different costs in the tree, so we first consider an efficient way of doing this. 3.1 Maintaining Cost Information When performing operations on the dynamic tree, we need to keep track of cost(x) for each node x, and we need to be able to find the minimum cost along paths to the root of the rooted tree. I f such a path is the prefix of a path corresponding to a splay tree, it seems that, knowing the minimum cost in any subtree of any our splay trees might be helpful. So, in addition to cost(x), we would like to keep track of the value mincost(x), given by mincost(x) = min{cost(y) | y in the subtree rooted at x of x’s splay tree}. We’ll see that, instead of