0
$\begingroup$

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: enter image description here

Calculate the cost of this operation. enter image description here

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 enter image description here

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: enter image description here Now the question is: why does index 2 change to 3?

enter image description here

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Yuval Filmus
    Dec 12 '17 at 21:27
  • $\begingroup$ Could you explain more? You are welcome? $\endgroup$
    – BadCatss
    Dec 13 '17 at 13:01
  • $\begingroup$ Having not seen the video, unfortunately I cannot say anything more. $\endgroup$
    – Yuval Filmus
    Dec 13 '17 at 13:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Dec 13 '17 at 14:36
  • 1
    $\begingroup$ Could you please provide a link to this video lecture? $\endgroup$
    – hengxin
    Oct 6 '18 at 7:35

Your Answer

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

Browse other questions tagged or ask your own question.