Splay Tree Analysis

Revision en1, by senthil28, 2020-07-03 14:04:36

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!

Tags splay tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English senthil28 2020-07-03 14:04:36 758 Initial revision (published)