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.