How to come up with sum-of-logs potential
Let's consider the BST algorithm $A$ that for each access for element $x$, it rearranges only elements in the search path $P$ of $x$ called before-path, into some tree called after-tree. For any element $a$, let $s(a)$ and $s'(a)$ be the size of subtree rooted at $a$ before and after the rearrangement respectively. So $s(a)$ and $s'(a)$ may differ iff $a \in P$.
Moreover, $A$ only rearranges constantly many elements in the search path at any moment. Let's call this type of algorithm "local" algorithm. For example, splay tree is local. It rearranges only at most 3 elements at a time by zig, zigzig and zigzag.
Now, any local algorithm that creates "many" leaves in the after-tree, like splay tree, has the following nice property.
We can create a mapping $f: P \rightarrow P$ such that
- There are linearly many $a \in P$, where $s'(f(a)) \le s(a)/2$.
- There are constantly many $a \in P$, where $s'(f(a))$ can be large but trivially at most $n$.
- Other elements $a \in P$, $s'(f(a)) \le s(a)$.
We can see this by unfolding the change of search path. The mapping is actually quite natural. This paper, A Global Geometric View of Splaying, precisely shows the details how to see the above observation.
After knowing this fact, it is very natural to choose sum-of-logs potential.
Because we can use the potential change of the type-1 elements to pay for the whole rearrangement. Moreover, for other-type elements, we have to pay for the potential change by at most logarithmic.
Hence, we can derive logarithm amortized cost.
I think the reason why people think this is "black magic" is that the previous analysis do not "unfold" the overall change of the search path, and see what really happens in one step.
Instead, they show the change in potential for each "local transformation", and then show that these potential changes
can be magically telescoped.
P.S. The paper even shows some limitation of sum-of-logs potential.
That is, one can prove satisfiability of access lemma via sum-of-logs potential to only the local algorithm.
Interpretation of sum-of-logs potential
There is another way to define the potential of BST in Georgakopoulos and McClurkin's paper which is essentially the same as sum-of-logs potential in Sleator Tarjan's paper. But this gives good intuition to me.
Now I switch to the notation of the paper. We assign a weight $w(u)$ to every node $u$. Let $W(u)$ be the sum of the weight of $u$'s subtree. (This is just the size of $u$'s subtree when the weight of every node is one.)
Now, instead of defining the rank on the nodes, we define the rank to the edges, which they called progress factor.
$$pf(e)=\log(W(u)/W(v)).$$
And the potential of tree $S$ is
$$\Phi(S) = \sum_{e\in S} pf(e).$$
This potential has a natural interpretation: if during a search we traverse an edge $(u,v)$ we reduce the search space from the descendants of $u$ to the descendants of $v$, a frantional reduction of $W(u)/W(v)$. Our progress factor is a logarithmic measure of this 'progress', hence its name. [From Section 2.4]
Observe that this is almost equal Sleator Tarjan's potential, and it is additive on paths.
edit: It turns out that this alternative definition and the intuition behind it was described long ago by Kurt Mehlhorn. See his book "Data Structures and Algorithms" Volume I, Section III. 6.1.2 Splay Trees, pages 263 - 274.
