0
$\begingroup$

The paper "Self-Adjusting Binary Search Trees" defines (Page 658) the potential function for analyzing the amortized cost of a sequence of $m$ splay operations as the sum of the ranks of all nodes in the splay tree, where the rank of a node $x$ is taken as the logarithm of the size ($s(x)$; i.e., number of nodes in) of the subtree rooted at $x$:

$$\Phi(T_i) = \sum_{x \in T} \log (s(x)).$$

To make sure that the amortized cost is an upper bound of the actual cost, it is required that the final potential is no less than the initial potential $\Phi(T_0)$ (Page 657):

$$\forall 1 \le i \le m: \Phi(T_i) \ge \Phi(T_0).$$

Problem: How to verify the condition above? (I did not find the argument in the paper.) Maybe it is not necessary to verify this condition; if so, why?

$\endgroup$
0
$\begingroup$

Answer My Own Question:

The short answer:

We don't have to verify $$\forall 1 \le i \le m: \Phi(T_i) \ge \Phi(T_0).$$ This condition is a special case of a more general one, which we need to verify for this example.

The detailed answer:

Consider a data structure $D$ and its states $D_0 \cdots D_m$ produced by a sequence of $m$ operations $o_1 \cdots o_m$: $$ D_0,\; o_1,\; D_1,\; o_2,\; \cdots,\; \underbrace{D_{i-1},\; o_{i},\; D_{i}}_{\text{the $i$-th operation}},\; \cdots,\; D_{m-1},\; o_{m},\; D_{m}. $$

The amortized cost of the $i$-th operation $o_i$ is defined as: $$\hat{c_i} = c_i + \Big(\Phi(D_{i}) - \Phi(D_{i-1})\Big)$$

Therefore, the total actual cost of these $m$ operations equals the total amortized cost plus the net decrease in potential from the initial to the final state.

$$ \sum_{1 \le i \le m} c_i = \left( \sum_{1 \le i \le m} \hat{c_i} \right) + \Big(\underbrace{\Phi(D_{0}) - \Phi(D_m)}_{\text{net decrease in potential}} \Big). $$

For each upper bound $\Box$ for $\Phi(D_{0}) - \Phi(D_m)$, we get a corresponding upper bound for the total actual cost of all operations:

$$ \sum_{1 \le i \le m} c_i \le \left( \sum_{1 \le i \le m} \hat{c_i} \right) + \Box. $$

The condition $$\forall 1 \le i \le m: \Phi(D_i) \ge \Phi(D_0)$$ in the post is just a special case of deriving upper bounds for the total actual cost, where the upper bound is the total amortized cost. Moreover, it is common to choose $\Phi$ such that $\Phi(D_0) = 0$ and $\Phi(D_i) \ge 0$ for all $i$.

To verify the validity of the potential function for splay trees, we use the following upper bound for $\Phi(T_{0}) - \Phi(T_i)$:

$$\Phi(T_{0}) - \Phi(T_i) \le n \log n.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.