2
$\begingroup$

The original paper describing splay trees Self-Adjusting Binary Search Trees by Sleator and Tarjan claims that:

Splaying not only moves x to the root, but roughly halves the depth of every node along the access path.

What is the intuition for this claim? The paper includes some figures (splaying in a tree of all zig-zigs or all zig-zags) and while I can see at a high level that splaying helps other parts of the tree, it's not really clear to me where the halving comes from?

$\endgroup$
0
$\begingroup$

Nobody has answered this question yet, and I can give some hints how to solve it. I would much rather post this as a comment, but I can't since I don't have enough reputation.

So here is a link to the original paper: https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf

The basic idea is looking at zig-zig and zig-zag (zig only happens once when the parent of x is the root!):

zig-zig

  1. Notice that if a node was in the search path before x was pushed to that position, it is now either in A or in B.
  2. Notice that all nodes in A and B have at least 1 depth less than before the zig-zig operation

zig-zag

  1. Notice that if a node was in the search path before x was pushed to that position, it is now either in B or in C.
  2. Notice that all nodes in B and C have at least 1 depth less than before the zig-zag operation

Now just think about how many zig-zig and zig-zag operations there are for a node with depth d in the search path.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.