rubbish's blog

How to prove the time complexity of splay tree?
By rubbish, history, 16 months ago, In English

Hi guys,
I have learn splay tree for a while and read a lot of tutorial and I found that different tutorial have different explanation but the strange thing is they have the same proof about the time complexity of splay operation.
When i see the proof,there is always one sentence "First let us use the potential method,then let potential function be log(size(n))" but why?
Is that related to the observation?Some of the math theorem happen same thing,through the result we already observe that the theorem is correct but haven't prove it then the problem become how to prove a theorem which is already correct(or at least can't found a counterexample) then there will be a lot of not logic operation just for prove the theorem.Does the splay tree happen same condition?
Thank for you reading,if you know the answer please teach me.

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

Comments Comments (6)
| Write comment?
»
16 months ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

The proce could be found by clicking one of the following link and link

→ Reply
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The naive rebalancing approach involves repeatedly performing rotation operations on a node to elevate it until it becomes the root. The problem with this naive method lies in chain-like trees where all child nodes are left (or right) children. In such cases, it essentially corresponds to repeatedly performing zig operations. Consequently, the constant term 1 in the amortized complexity of zig operations would continuously accumulate, resulting in a final amortized complexity reaching O(log n + n). The design of the rebalancing operation in Splay trees prevents constant accumulation in consecutive zig scenarios by ensuring that during a complete splay operation, at most one standalone zig operation is performed, thereby optimizing the time complexity.

→ Reply