4.6.5 Amortized Analysis of Splaying

• As a measure of complexity, we shall take the depth within the tree that the desired node has before splaying.

T	:	BST on which we are performing a splay
		insertion or retrieval
Ti	:	tree T as it has been transformed after
		step i of the splaying process, with T0 = T
x	:	any node in Ti
Ti(x)	:	subtree of Ti with root x
| Ti(x)|	:	number of nodes of Ti(x)

• We consider bottom-up splaying at a node x, so that x begins somewhere in the tree T but after m splaying steps, ends up as the root of T.
• Rank

 

 

For each step i of the splaying process and each vertex x$\in$T, we define rank at step i of x to be 

r_i(x) = $$\underbrace{\log \vert T_i(x)\vert}_{\begin{array}{c}\mbox{heigh...... \mbox{if it} \\\mbox{were completely }\\\mbox{balanced.}\end{array}}^{}\,$$
• Portion out the credit balance of the tree among all its vertices by requiring the following credit invariant to hold:

 

 

For every node x of T and after every step i of splaying, node x has credit equal to its rank r_i(x).

• Define the total credit balance for the tree as 

                                                                     C_i = $$\sum_{x \in T_i}^{}$$r_i(x)

• If the tree is empty or contains only one node, then its credit balance is 0. As the tree grows, its credit balance increases. The credit balance should reflect the work needed to build the tree.
• Our goal is to determine bounds on a_i that will allow us to find the cost of the splaying process, amortized over a sequence of retrievals and insertions.
• A useful Result:

 

 

If $\alpha$,$\beta$,$\gamma$ are positive real numbers with $\alpha$ + $\beta$$\leq$$\gamma$, then 
                                                                                                                    log$$\alpha$$ + log$$\beta$$$$\leq$$ 2log$$\gamma$$ - 2                (*)

This can be easily proved as follows:

$$\left(\vphantom{\sqrt{\alpha} - \sqrt{\beta}}\right. \sqrt{\alpha} \sqrt{\beta} \left.\vphantom{\sqrt{\alpha} - \sqrt{\beta}}\right)^{2}_{} \geq \Rightarrow \sqrt{\alpha\beta} \leq {\frac{\alpha+ \beta}{2}} \Rightarrow \sqrt{\alpha\beta} \leq {\frac{\gamma}{2}}$$

$$\Rightarrow \alpha \beta \leq \gamma$$


 

Result 1

If the i^th splaying step is a zig-zig or a zag-zag step at node x, then its amortized complexity a_i satisfies 

a_i < 3(r_i(x) - r_{i - 1}(x))

See Figure 4.26.
 

Figure 4.26: A zig-zig at the ith splaying step

• The actual complexity t_i of a zig-zig or a zag-zag is 2 units
• Only the sizes of the subtrees rooted at x, y, z change in this step. Hence, all terms in the summation defining C_i cancel against those for C_{i - 1} except those indicated below

a_i = t_i + C_i - C_{i - 1}

= 2 + r_i(x) + r_i(y) + r_i(z)     - r_{i - 1}(x) - r_{i - 1}(y) + r_{i - 1}(z)

$$\bullet$$ =


 

Since | T_i(x)| = | T_{i - 1}(z)| as the subtree rooted at z before the splaying step has the same size as that rooted at x after the step.

                                                                                                                            Let

                                                                                                                        $\alpha$ = | T_{i - 1}(x)|,$\beta$ = | T_i(z)|, and $\gamma$ = | T_i(x)|. Then observe that $\alpha$ + $\beta$$\leq$$\gamma$. This is because

$$\mbox{contains all these components (plus $y$\space besides)}$$

Thus by (*) 

r_{i - 1}(x) + r_i(z) $$\leq$$ 2r_i(x) - 2 $$\Rightarrow$$  2r_i(x) - r_{i - 1}(x) - r_i(z) - 2 $$\geq$$ 0 Adding this to ($\bullet$), we get  a_i$$\leq$$ 2r_i(x) - 2r_{i - 1}(x) + r_i(y) - r_{i - 1}(y) Before step i, y is the parent of x so that  | T_{i - 1}(y)| > | T_{i - 1}(x)| After step i, x is the parent of y so that  | T_i(x)| > | T_i(y)| Taking logarithms we have  r_{i - 1}(y) > r_{i - 1}(x) and  r_i(x) > r_i(y) Thus we obtain  a_i < 3r_i(x) - 3r_{i - 1}(x) Similarly, we can show Results 2 and 3 below:

Result 2

                            If the ith splaying step is a zig-zag or zag-zig at node x, then its amortized complexity ai satisfies

a_i < 2(r_i(x) - r_{i - 1}(x))

Result 3

                                                                                                                        If the ith splaying step is a zig or a zag, then

a_i < 1 + (r_i(x) - r_{i - 1}(x))

Result 4

The total amortized cost over all the splaying steps can be computed by adding the costs of all the splay steps. If there are k such steps, only the last can be a zig or zag and the others are all zig-zag or zig-zag or zag-zig or zag-zag. Since (*) provides the weaker bound, we get,

$$\sum_{i=1}^{k} \sum_{i=1}^{k-1}$$ =

$$\leq \sum_{i-1}^{k-1}$$

= 1 + 3r_k(x) - 3r₀(x)

$$\leq$$ 1 + 3r_k(x)

= 1 + 3log n

Thus the amortized cost of an insertion or retrieval with splaying in a BST with n nodes does not exceed 1 + 3log n upward moves of the target node in the tree.

Result 5

Now consider a long sequence of m splay insertions or retrievals. We seek to compute the actual cost of all these m operations.

Let Tj and Aj be the actual cost and amortized cost of the jthoperation, where j = 1, 2,..., m, now represents a typical insertion or retrieval operation.

We have

$$\sum_{j=1}^{m}$$T_j = $$\left(\vphantom{\sum_{j=1}^m \space A_j}\right.$$$$\sum_{j=1}^{m}$$A_{j$$\left.\vphantom{\sum_{j=1}^m \space A_j}\right)$$} + $$\mbox{{$C_O - C_m$}}$$ If the tree never has more than n nodes, then C0 and Cm lie between 0 and log n, so that 

                                                                                                        C₀ - C_m$$\leq$$ log n
Also we know that 

                               A_j$$\leq$$ 1 + 3logn  for j = 1, 2,..., m
Thus the above becomes 
                            $$\sum_{j=1}^{m}$$T_j = m(1 + 3logn) + log n
The above gives the total actual time of m insertions or retrievals on a tree that never has more than n nodes.

This gives O(log n) actual running time for each operation.