Splay trees: why are depths of nodes on the access path halved?

Question

The original paper describing splay trees Self-Adjusting Binary Search Trees by Sleator and Tarjan claims that:

Splaying not only moves x to the root, but roughly halves the depth of every node along the access path.

What is the intuition for this claim? The paper includes some figures (splaying in a tree of all zig-zigs or all zig-zags) and while I can see at a high level that splaying helps other parts of the tree, it's not really clear to me where the halving comes from?

Answer 1

Nobody has answered this question yet, and I can give some hints how to solve it. I would much rather post this as a comment, but I can't since I don't have enough reputation.

So here is a link to the original paper: https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf

The basic idea is looking at zig-zig and zig-zag (zig only happens once when the parent of x is the root!):

1. Notice that if a node was in the search path before x was pushed to that position, it is now either in A or in B.
2. Notice that all nodes in A and B have at least 1 depth less than before the zig-zig operation

1. Notice that if a node was in the search path before x was pushed to that position, it is now either in B or in C.
2. Notice that all nodes in B and C have at least 1 depth less than before the zig-zag operation

Now just think about how many zig-zig and zig-zag operations there are for a node with depth d in the search path.