$1$ Alternate Splay Tree Insertion

Here is an alternate implementation of insert for Splay trees. First, insert $x$ as you would normally do in a binary search tree. After this insertion $x$ becomes a leaf. Then, rotate $x$ as you would in the splay operation until $x$ is the root of the tree.

This implementation is actually different from the one discussed in lecture. In this implementation, $x$ becomes the root of the tree, which is not the case in the original implementation.

Fortunately, we do not have to redo the entire amortized analysis of Splay trees for this change, because the amortized analysis is valid as long as each node in the tree has enough credits $($i$.$e$.,$ as long as the invariant holds$).$ It does not matter that the tree was not constructed using splay tree operations. We just have to make sure that every node $y$ still has rank$(y)$ credits after we insert $x$ at the leaf $($and before we run the splay operation$).$

After inserting $x$ as a leaf in the alternate implementation of insert, which nodes might see an increase in their size?

How many nodes are there that see an increase in their size? Briefly justify your answer.

Note: recall that the height of a splay tree could be linear.

How many nodes are there that see an increase in their rank? Briefly justify your answer.

Note: it is possible that a node's size increases, but its rank does not.

If a node's rank does increase, how much can the rank change? Briefly justify your answer.

How many credits would you need to add to make sure that every node $y$ still has rank$(y)$ credits? Briefly justify your answer.

Argue that the amortized running time of the entire alternate insert operation $($including inserting $x$ at the leaf and splaying at $x$ is $(logn).$ Briefly justify your answer.

Why is it necessary splay the newly inserted $x?$ Why can't we just do a normal binary tree insertion and add enough credits to maintain the invariant?