Блог пользователя senthil28

Автор senthil28, история, 4 года назад, По-английски

hello codeforces, I have been trying to learn about splay trees from this.In the analysis of alternate implementations insertion and deletion it has been mentioned that this follows from a modification of the proof of lemma 1(Access lemma).

I could find proofs for this when all weights are taken as 1 for example here

but i could'nt find one for the general weighted case nor can prove it myself. so can anyone please help ? thanks!

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

no need to prove it I can tell you that I complete all work in time

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

You can try asking the man who invented the splay tree who also competes on CodeForces: Darooha

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What do you mean by "weight"?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +66 Проголосовать: не нравится

It may be correct. I need to think about these questions carefully again.

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

    I'm still confused about the analysis for the alternative implementation of insertion. The 3.3.2 insertion proof in the original post bounds the change in potential for the case when all weights are 1, but I don't see how this generalizes to arbitrary weights.

    So I guess I don't see where the $$$\log \left(\frac{W-w(i)}{\min(w(i-),w(i+))}\right)$$$ term is coming from in the alternative version. (I see why this is included in the original version of insertion.)