Proof Spaly trees?

In Splay trees, by definition - the desired element x is raised to the root of the tree, using the operations: zig, zig-zig, zigzag. And the formula zig step like this: 1+3(r'(v)-r(v)) , where - r'(v)-r(v) is the length of the way to raise the x way to the top, and the factor 1 - "the actual price paid for actions"

But here's the question: where does the coefficient 3?

And evaluation of the zig-zig and zigzag step is: 3(r'(v)-r(v))

again, the question: what does the coefficient 3?

and what happened to 1 - as the "actual price paid for actions" ? ("the actual price paid for the action" - in terms of account value)
June 10th 19 at 16:31
0 answer

Find more questions by tags Algorithms