Does the subtree under x being splayed become necessarily balanced after the splay operation?

Question

Here is the problem:

Let T be a splay tree on n nodes, and let x be a node of T. Consider a splay operation at x. Does the subtree under x become necessarily balanced (i.e., the height of the subtree rooted at x in the splay tree becomes O(logn) after the splay operation?

I spent lots of time on it, but still frustrated....I appreciate your answer.

Answer 1

No. Consider the absolute worst-case where T looks something like this:

y
 \
  y
   \
   ...
     \
      x

where the ys are arbitrary nodes. Once you splay x, the tree will look something like this:

  x
 /
y
 \
  y
 / \
y   y
   / \
  y   y
     / \
    y  ...
         \
          y

(again, with ys as arbitrary nodes). The depth then, is still O(n) in this case.

EDIT: Realized I messed up the "after" tree, so updating my answer with a more correct example.

Answer 2

No. See these notes. The average depth of traversed nodes is cut in half, but that doesn't guarantee that a balanced tree results.