Zig-Zig Case

We're splaying x, with y and z as the immediate parents.

We need to show that $\hat{c}_t + \Phi(D_{t-1}) - \Phi(D_t) \ge c_t$.

Here, we'll take $\hat{c}_t = 3(\log s_{t}(x)- \log s_{t-1}(x))$. The actual cost c_t = 2. Why?

The last step here is sort of tricky.

• Claim: $2 \log s_t(x) - \log s_{t-1}(x) - \log s_t(z) \ge 2$.
• Let n = s_t(x).
• Note that if a+b = n, then $-\log a - \log b \ge -2\log n + 2$,and this is attained at n/2 (this isn't hard to show with calculus).
• Note that s_t(z) + s_t-1(x) = n. So,

  

Zig-zag case a little different, but same result.