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 29, 2001 Lecture 13 Lecturer: Michel X. Goernans Scribe: Naveen Sunkavally 1 Introduction In the last lecture we introduced splay trees and defined the three different types of splay steps used to splay an element (i.e. bring it to the root). The three types (shown below as operating on node X) are: ZIG A,& AA Figure 1: The parent of X is the root ZIG-ZIG Figure 2: X and its parent are both left (or right) children ZIG-ZAG Figure 3: X is a right child and its parent is a left child (or vice versa)2 Amortized Analysis of Splay Tree Operations In this lecture we use amortized analysis to obtain bounds on the running times of splay operations. The analysis will show that the amortized cost of any splay tree operation (find, insert, delete, etc.) is of the order O(log(n)), where n is the number of nodes in the tree. Any single operation on a splay tree may take O(n) time, but it also tends to make the tree more balanced, so that over time the average cost of any operation is O(log(n)). The analysis uses the potential method (see CLR, chapter 18 for a description) to obtain the O(log(n)) bound. The first step is to define a weight, sum, and rank function at each node: Every node X has a weight w (X) > 0 We define the potential on the entire splay tree data structure at any moment in time i as the sum of all the ranks in the tree: The potential is a measure of how balanced the tree is: trees with low potential for a given number of nodes are well balanced, while trees with high potential are poorly balanced. The amortized cost of a splay operation is then given by the actual cost of the operation plus the change in potential of the tree. Operations whose actual costs are high should come with the benefit of lowering the potential of the tree so that the amortized cost stays reasonable. 2.1 Amortized Cost of a Splay Step The following lemma gives the amortized cost of a single splay step: Lemma 1 Let r(X) be the rank of X before a splay step, and let r'(X) be the rank of X after a splay step. Then the amortized cost of the splay step shown in figure I (ZIG) is < 3(rt(X)-r(X)) + 1. The amortized cost of the splay steps shown in figure 2 and 3 (ZIG-ZIG and ZIG-ZAG) is < 3(r1(X)-r(X)). Proof of Lemma 1: Consider each of the cases separately: In case 1 (ZIG), we have Amortized cost = Actual cost + 4(i + 1) -$(i) = 1+ (rl(X)+rl(Y) -r(X) -r(Y)) The actual cost of the splay step in this case is 1because we only perform one rotation to bring X to the root. Because r' (X) = r(Y), and because rl(Y) 5 r' (X), we get: Amortized cost < 1+rl(X) -r(X) < 1+3(r1(X)-r(X))-In case 2 (ZIG-ZIG), the actual cost is 2 because we are performing a double rotation. We can take advantage of the fact that r' (X) = r(Z), r(Y) 2 r(X), and r' (Y) < rl(X) to arrive at:Amortized cost = Actual cost +$(i + 1) -$(i) = 2 + (rl(X)+rl(Y)+rl(Z)-r(X)-r(Y)-r(Z)) 5 2+r1(X)+rl(Z)-r(X) -r(X) To simplify further, we take advantage of the fact that the log function is concave, so that for any two points a and b, a and b > 0, it must be the case that z0g2(a)+10g2(b)2 5 logz(+). In figure 2, notice that s(X)+ sl(Z) 5 sl(X),or equivalently s(X):s'(z) 5 w.By the concavity of the log function, r(X):r'(Z) <-log2( s(X):sl (') ), which by transitivity implies that r(X);r'(Z) < s' X)1092(+) = rl(X)-1,and rl(Z)< 2r1(X)-2 -r (X). Thus, Amortized cost 5 2 +rl(X)+ (2r1(X)-2 -r (X))-r(X)-r (X) 5 3(r1(X)-r(X)) In case 3 (ZIG-ZAG),the actual cost of the double rotation is 2, and we again use the fact that rl(X)=r(Z) and r (Y)> r(X) to state: Amortized cost = Actual cost +$(i +1) -$(i) = 2 + (TI (x)+ri(Y)+r1(2)-r(X)-r(Y)-~(2)) 5 2 +TI (Y)+rl(Z)-r(X)-r (X) From figure 3, it is evident that sl(Y)+si(Z)5 si(X),and using the concavity of the log function, we get that rl(Y)+rl(Z)< 2(r1(X)-I). Thus, Amortized cost < 2 + (2r1(X)-2) -r(X)-r(X) 5 3(r1(X)-r(X)) 2.2 Amortized Analysis of a Splay Operation The following two corollaries follow from the above analysis of the amortized running time of a single splay step. Corollary 2 Let V be the vertex of the splay tree before a splay operation is carried out. Then the amortized cost of splaying a node X is O(log(n)). Proof of Corollary 2: The amortized cost of splaying at X equals the sum of the amortized costs of all the single splay steps. This sum telescopes to yield that the amortized cost of splaying X is 5 3(r(V)-r(X))+ 1. The extra constant term 1 accounts for the possibility of a case 1rotation. Note that this analysis is independent of the chosen weights in the tree. Suppose we set all weights to be 1. Then the maximum possible difference between r(V) and r(X) equals the log of number of nodes in the tree. So the amortized cost of splaying X is O(log(n)). Corollary 3 The actual cost of a sequence of m splayings is O((m+n)log(n)).Proof of Corollary 3: The actual cost equals the amortized cost plus the gain from the credit invariant. Or equivalently, if i corresponds to the time before the m splayings, and i +m corresponds to the time after the m splayings, we get: Actual cost of m splays = Amortized cost of m splays +$(i) -$(i +m) From corollary 2, the amortized cost of rn splays is O(mlog(n)). The maximum change in potential, again assuming all weights are 1, is O(nlog(n)), so the actual cost is O((m + n)log(n)). We have shown that the amortized cost of splaying is O(log(n)), but we have yet to show that the cost of operations such as find or insert are also O(log(n)). Most operations, e.g. find, which do not modify the tree are clearly within a constant factor of splaying operation, because we can argue that the cost, say, of finding an element is roughly twice the cost of splaying that element. Thus most operations have an amortized cost of O(log(n)). This analysis however does not necessarily follow for operations such as insert, which modify the tree. It can be shown that the insert operation also has an amortized running time of O(log(n)) by considering how much the potential of the tree increases right after a new node is added (prior to the subsequent splay that brings it to the root). If the potential increases by a factor of O(log(n)),