Splay Trees:Linking and Cutting Trees

Linking and Cutting Trees

Tarjan [15] and Sleator and Tarjan [13] have shown that splay trees can be used to implement linking and cutting trees.

We are given a collection of rooted trees. Each node will store a value, which can be any real number. These trees can “grow” by combining with another tree link and can shrink by losing an edge cut. Less informally, the trees are “dynamic” and grow or shrink by following operations (we assume that we are dealing with a forest of rooted trees).

link If x is root of a tree, and y is any node, not in the tree rooted at x, then make y the parent of x.

cut Cut or remove the edge between a non-root node x and its parent. Let us assume that we want to perform operations like

• Add (or subtract) a value to all ancestors of a node.

• Find the minimum value stored at ancestors of a query node x.

More formally, following operations are to be supported:

find cost(v): return the value stored in the node v.

find root(v): return the root of the tree containing the node v.

find min(v): return the node having the minimum value, on the path from v till find root(v), the root of the tree containing v. In case of ties, choose the node closest to the root.

add cost(v, δ): Add a real number δ to the value stored in every node on the path from v to the root (i.e., till find root(v)).

find size(v) find the number of nodes in the tree containing the node v.

link(v, w) Here v is a root of a tree. Make the tree rooted at v a child of node w. This operation does nothing if both vertices v and w are in the same tree, or v is not a root.

cut(v) Delete the edge from node v to its parent, thus making v a root. This operation does nothing if v is a root.

Data Structure

For the given forest, we make some of the given edges “dashed” and the rest of them are kept solid. Each non-leaf node will have only one “solid” edge to one of its children. All other children will be connected by a dashed edge. To be more concrete, in any given tree, the right-most link (to its child) is kept solid, and all other links to its other children are made “dashed”.

As a result, the tree will be decomposed into a collection of solid paths. The roots of solid paths will be connected to some other solid path by a dashed edge. A new data structure

called a “virtual tree” is constructed. Each linking and cutting tree T is represented by a virtual tree V , containing the same set of nodes. But each solid path of the original tree is modified or converted into a binary tree in the virtual tree; binary trees are as balanced as possible. Thus, a virtual tree has a (solid) left child, a (solid) right child and zero or more (dashed) middle children.

In other words, a virtual tree consists of a hierarchy of solid binary trees connected by dashed edges. Each node has a pointer to its parent, and to its left and right children (see Figure 12.4).

Solid Trees

Recall that each path is converted into a binary tree. Parent (say y) of a node (say x) in the path is the in-order (symmetric order) successor of that node (x) in the solid tree. However, if x is the last node (in symmetric order) in the solid sub-tree then its parent path will be the parent of the root of the solid sub-tree containing it (see Figure 12.4). Formally, Parentpath(v) =Node(Inorder(v) + 1).

Note that for any node v, all nodes in the left sub-tree will have smaller inorder numbers and those in the right sub-tree will have larger inorder numbers. This ensures that all nodes in the left subtree are descendants and all nodes in the right sub-tree are ancestors. Thus, the parent (in the binary tree) of a left child will be an ancestor (in the original tree). But, parent (in the binary tree) of a right child is a descendant (in the original tree). This order, helps us to carry out add cost effectively.

We need some definitions or notation to proceed.

Let mincost(x) be the cost of the node having the minimum key value among all descen- dants of x in the same solid sub-tree. Then in each node we store two fields δcost(x) and δmin(x). We define,

δmin(x) =cost(x)−mincost(x). And,

Rotation

Let us discuss rotation first (see Figure 12.5).

Let w be the parent of v in the solid tree, then rotation of the solid edge (v, p(v)) ≡ (v, w) will make w = p(v) a child of v. Rotation does not have any effect on the middle children.

Let a be the left solid child of w and v be the right solid child of w.

Let “non-primes” denote the values before the rotation and “primes” the values after the rotation of the solid edge (v, w). We next show that the new values δcost!, δmin! and δsize!, can be calculated in terms of old known values.

We assume that b is the left solid child of v and c is the right solid child of v.

First we calculate the new δcost! values in terms of old δcost values. From Figure 12.5,

Splicing

Let us next look at the other operation, splicing. Let w be the root of a solid tree. And let v be a child of w connected by a dashed edge. If u is the left most child of w, then splicing at a dashed child v, of a solid root w, makes v the left child of w. Moreover the previous left-child u, now becomes a dashed child of w. Thus, informally speaking splicing makes a node the leftmost child of its parent (if the parent is root) and makes the previous leftmost child of parent as dashed.

We next analyse the changes in “cost” and “size” of various nodes after splicing at a dashed child v of solid root w (whose leftmost child is u). As before, “non-primes” denote the values before the splice and “primes” the values after the splice.

As v was a dashed child of its parent, it was a root earlier (in some solid tree). And as w is also a root,

δcost!(v) =cost(v)−cost(w)

= δcost(v) − δcost(w).

And as u is now the root of a solid tree,

δcost!(u) =cost(u)

= δcost(u)+cost(w)

= δcost(u) + δcost(w).

Finally, δmin!(w) = max{0, δmin(v) − δcost!(v), δmin(right(w))-δcost(right(w))}

All other values are clearly unaffected.

As no rotation is performed, δsize( ) also remains unchanged, for all nodes.

Splay in Virtual Tree

In virtual tree, some edges are solid and some are dashed. Usual splaying is carried out only in the solid trees. To splay at a node x in the virtual tree, following method is used. The algorithm looks at the tree three times, once in each pass, and modifies it. In first pass, by splaying only in the solid trees, starting from the node x, the path from x to the root of the overall tree, becomes dashed. This path is made solid by splicing. A final splay at node x will now make x the root of the tree. Less informally, the algorithm is as follows:

Algorithm for Splay(x)

Pass 1 Walk up the virtual tree, but splaying is done only within solid sub-tree. At the end of this pass, the path from x to root becomes dashed.

Pass 2 Walk up from node x, splicing at each proper ancestor of x. After this step, the path from x to the root becomes solid. Moreover, the node x and all its children in the original tree (the one before pass 1) now become left children.

Pass 3 Walk up from node x to the root, splaying in the normal fashion.

Analysis of Splay in Virtual Tree

Weight of each node in the tree is taken to be the same (say) 1. Size of a node is total number of descendants— both solid and dashed. And the rank of a node as before is rank(x) = log(size(x)). We choose α = 2, and hence the potential becomes, potential= 2 ), rank(x).

We still have to fix β. Let us analyze the complexity of each pass.

Pass 1 We fix β = 1. Thus, from Lemma 12.1, the amortized cost of single splaying is at most 6(r(t) − r(x)) + 1. Hence, the total cost of all splays in this pass will be

≤ 6(r(t1) − r(x)) + 1 + 6(r(t2) − r(p(t1 )) + 1 + ··· + 6(r(tk ) − r(p(tk−1 ))) + 1 ≤ (6(r(t1) − r(x)) + +6(r(tk ) − r(p(tk−1 )))) + k.

Here, k is number of solid trees in path from x to root. Or the total cost ≤ k + (6(r(root) − r(x))) − 6(r(p(tk−1 )) − r(tk−1 ) + ··· + r(p(t1)) − r(t1 )))

Recall that the size includes those of virtual descendants, hence each term in the bracket is non-negative. Or the total cost ≤ k + 6(r(root) − r(x))

Note that the depth of node x at end of the first pass will be k.

Pass 2 As no rotations are performed, actual time is zero. Moreover as there are no rotations, there is no change in potential. Hence, amortized time is also zero. Alternatively, time taken to traverse k-virtual edges can be accounted by incorporating that in β in pass 3.

REMARK 12.3 This means, that in effect, this pass can be done together with Pass 1.

Pass 3 In pass 1, k extra rotations are performed, (there is a +k factor), thus, we can take this into account, by charging, 2 units for each of the k rotation in pass 3, hence we set β = 2. Clearly, the number of rotations, is exactly “k”. Cost will be 6 log n + 2. Thus, in effect we can now neglect the +k term of pass 1.

Thus, total cost for all three passes is 12 log n + 2.

Implementation of Primitives for Linking and Cutting Trees

We next show that various primitives for linking and cutting trees described in the beginning of this section can be implemented in terms of one or two calls to a single basic operation— “splay”. We will discuss implementation of each primitive, one by one.

find cost(v) We are required to find the value stored in the node v. If we splay at node v, then node v becomes the root, and δcost(v) will give the required value.

Thus, the implementation is splay(v) and return the value at node v

find root(v) We have to find the root of the tree containing the node v. Again, if we splay at v, then v will become the tree root. The ancestors of v will be in the right subtree, hence we follow right pointers till root is reached. The implementation is:

splay(v), follow right pointers till last node of solid tree, say w is reached, splay(w) and return(w).

find min(v) We have to find the node having the minimum value, on the path from v till the root of the tree containing v; in case of ties, we have to choose the node closest to the root. We again splay at v to make v the root, but, this time, we also keep track of the node having the minimum value. As these values are stored in incremental manner, we have to compute the value by an “addition” at each step.

splay(v), use δcost( ) and δmin( ) fields to walk down to the last mini- mum cost node after v, in the solid tree, say w, splay(w) and return(w).

add cost(v, δx) We have to add a real number δx to the values stored in each and every ancestors of node v. If we splay at node v, then v will become the root and all ancestors of v will be in the right subtree. Thus, if we add δx to δcost(v), then in effect, we are adding this value not only to all ancestors (in right subtree) but also to the nodes in the left subtree. Hence, we subtract δx from δcost( ) value of left child of v. Implementation is:

splay(v), add δx to δcost(v), subtract δx from δcost(LCHILD(v)) and return

find size(v) We have to find the number of nodes in the tree containing the node v.

If we splay at the node v, then v will become the root and by definition of δsize, δsize(v) will give the required number.

splay(v) and return(δsize(v)).

link(v, w) If v is a root of a tree, then we have to make the tree rooted at v a child of node w.

Splay(w), and make v a middle (dashed) child of w. Update δsize(v) and δsize(w), etc.

cut(v) If v, is not a root, then we have to delete the edge from node v to its parent, thus making v a root. The implementation of this is also obvious:

splay(v), add δcost(v) to δcost(RCHILD(v)), and break link between RCHILD(v) and v. Update δmin(v), δsize(v) etc.