Bottom-Up Splay Trees–AnalysisPotential FunctionExampleRoot RankInsertJoinSplay Step Amortized CostSlide 8Slide 92-Level Move (case 1)Slide 11Slide 12Slide 13Slide 142-Level Move (case 2)Splay OperationSlide 17Actual Cost Of Operation SequenceSlide 19Bottom-Up Splay Trees–Analysis•Actual and amortized complexity of join is O(1).•Amortized complexity of search, insert, delete, and split is O(log n).•Actual complexity of each splay tree operation is the same as that of the associated splay.•Sufficient to show that the amortized complexity of the splay operation is O(log n).Potential Function•size(x) = #nodes in subtree whose root is x.•rank(x) = floor(log2 size(x)).•P(i) = x is a tree node rank(x).P(i) is potential after i’th operation.size(x) and rank(x) are computed after i’th operation.P(0) = 0.•When join and split operations are done, number of splay trees > 1 at times.P(i) is obtained by summing over all nodes in all trees.Example•size(x) is in red.20106840301•rank(x) is in blue.•Potential = 5.23126011012Root Rank•rank(root) = floor(log2 n).2010684030123126011012Insert•On every leaf to root path ranks are non-decreasing.•At most floor(log2 n)+1 different ranks on such a path.•Insert may increase the rank of only the last node in each sequence of equal rank nodes.•When you insert, potential increases by up to floor(log2 n)+1.0114447Join•Rank of root is floor(log2 n).•Other ranks unchanged.•Potential increases by floor(log2 n).SmBSplay Step Amortized Cost•If q = null or q is the root, do nothing (splay is over).-P = 0.•amortized cost = actual cost + P = 0.Splay Step Amortized Cost•If q is at level 2, do a one-level move and terminate the splay operation.pqa bcb caqp• r(x) = rank of x before splay step.•r’(x) = rank of x after splay step.Splay Step Amortized Costpqa bcb caqp• P = r’(p) + r’(q) – r(p) – r(q) <= r’(q) – r(q).• amortized cost = actual cost + P <= 1 + r’(q) – r(q).2-Level Move (case 1)• P = r’(gp) + r’(p) + r’(q) – r(gp) – r(p) – r(q)pqa bcgpdc dbpgpqa2-Level Move (case 1)• r’(q) = r(gp)•r’(p) <= r’(q)pqa bcgpdc dbpgpqa•r’(gp) <= r’(q)• r (q) <= r(p)2-Level Move (case 1)-P = r’(gp) + r’(p) + r’(q) – r(gp) – r(p) – r(q)•r’(q) = r(gp)•r’(gp) <= r’(q)•r’(p) <= r’(q)• r (q) <= r(p)-P <= r’(q) + r’(q) – r(q) – r(q) = 2(r’(q) – r(q))2-Level Move (case 1)more careful analysis reveals thatP <= 3(r’(q) – r(q)) –12-Level Move (case 1)•amortized cost = actual cost + P <= 1 + 3(r’(q) – r(q)) –1 = 3(r’(q) – r(q))2-Level Move (case 2)•Similar to Case 1.Splay Operation•When q != null and q is not the root, zero or more 2-level splay steps followed by zero or one 1-level splay step.•Let r’’(q) be rank of q just after last 2-level splay step.•Let r’’’(q) be rank of q just after 1-level splay step.Splay Operation•Amortized cost of all 2-level splay steps is <= 3(r’’(q) – r(q)) •Amortized cost of splay operation <= 1 + r’’’(q) – r’’(q) + 3(r’’(q) – r(q)) <= 1 + 3(r’’’(q) – r’’(q)) + 3(r’’(q) – r(q)) = 1 + 3(r’’’(q) – r(q)) <= 3(floor(log2n) – r(q)) + 1Actual Cost Of Operation Sequence•Actual cost of an n operation sequence = O(actual cost of the associated n splays).•actual_cost_splay(i) = amortized_cost_splay(i) – P <= 3(floor(log2i) – r(q)) + 1 + P’(i) – P(i) •P’(i) = potential just before i’th splay.•P(i) = potential just after i’th splay.•P’(i) <= P(i – 1) + floor(log2i) + 1Actual Cost Of Operation Sequence•actual_cost_splay(i) = amortized_cost_splay(i) – P <= 3(floor(log2i) – r(q)) + 1 + P’(i) – P(i) <= 3 * floor(log2i) + 1 + P’(i) – P(i) <= 4 * floor(log2i) + 2 + P(i – 1) – P(i)•P(0) = 0 and P(n) >= 0.-iactual_cost_splay(i) <= 4n * floor(log2n) + 2n + P(0) – P(n)<= 6n * floor(log2n)(n log