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$$\eqno$$(*)

  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}}$$ (4.22)

  $$\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} (4.23)

  = 2 + r_i(x) + r_i(y) + r_i(z) (4.24)

      - r_{i - 1}(x) - r_{i - 1}(y) + r_{i - 1}(z) (4.25)

  $$\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

T_{i - 1}(x)  contains components  x, A, B (4.26)

T_i(z)  contains components  z, C, D (4.27)

$$\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: