# Proof of Zig-Zig step

There was a question connected with one of the video lecture lessons that I'm currently watching.

Let two trees be given - the original and the tree after the zig-zig step:

Calculate the cost of this operation.

Where it is: the sum of the ranks of the new tree (after the zig-zig step) minus the sum of the ranks of the source tree. Now pay attention to the root tops of the trees. - because their rank is equal, then we can delete them from equation

Now, we carry out the upper bound. r '(u) and r' (w) - they can be estimated as r '(v) in the initial tree (up to the zig-zig step) in the upper estimate - the vertices u and w are above the vertex v - therefore, when estimating from above with respect to the vertex v in the source tree - we simply consider the potential of the vertices r (u) and r (w) as r (v) with the opposite sign. As a result, we get the expression: Now the question is: why does index 2 change to 3?

At first I thought that it was +1 as an accounting cost for the actual action, but it turned out that this +1 should be performed for each vertex - that breaks all the evidence - there it is explained later in the lecture and also how to avoid it, But now this is not about it , but why, if this is not +1 for the actual action, then where did the index 3 come from?

P.s : Further in the lecture, attention is not focused on this - therefore I ask.

• They probably only need to show the upper bound $3(r'(v)-r(v))$. It's certainly the case that $2(r'(v)-r(v)) \leq 3(r'(v)-r(v))$, assuming that $r'(v) \geq r(v)$. – Yuval Filmus Dec 12 '17 at 21:27
• Could you explain more? You are welcome? – BadCatss Dec 13 '17 at 13:01
• Having not seen the video, unfortunately I cannot say anything more. – Yuval Filmus Dec 13 '17 at 13:04
• The rest of the argument presumably only needs the upper bound $3(r'(v)-r(v))$. The argument gives the stronger upper bound $2(r'(v)-r(v))$, from which we can derive the weaker upper bound $3(r'(v)-r(v))$. For anything more, you will need to explain the rest of the argument. – Yuval Filmus Dec 13 '17 at 14:36
• Could you please provide a link to this video lecture? – hengxin Oct 6 '18 at 7:35