I am looking into the amortized analysis of splay trees and seem to be missing something.

Pretty much every resource uses the accounting method which I believe I grasp. What confuses me is the part where an upper bound is put on credits:

$ δ≤3(r′(x)−r(x)) $ where $r'(x)$ is the rank of a node after splaying and $r(x)$ is the rank before.

Could someone help me with there the $3$ is coming from? It appears to be common knowledge which I'm missing as everyone just uses it as given. Thanks!

  • $\begingroup$ Can you edit the question to add a reference to that part that is easily accessible and likely to be stably available? $\endgroup$ – John L. Jun 10 '19 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.