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.