senthil28's blog

Splay Tree Analysis
By senthil28, history, 4 years ago, In English

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!

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
4 years ago, # |
  Vote: I like it +44 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What do you mean by "weight"?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +66 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +13 Vote: I do not like it

    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.)

    → Reply