Insertion and deletion of nodes in Splay Trees

Question

I have 2 questions regarding splay trees:

1. Deletion of a node

The book I am using says the following: ''When deleting a key k, we splay the parent of the node w that gets removed. Example deletion of 8:

However, what I am doing is this: If the deleted node is not the root, I splay it (to the root), delete it, and splay the right-most node of the left-subtree. But since in this case, the deleted node is the root, I simply remove it and splay the right-most node of the left subtree immediately. Like this:

Is this way also correct? Notice that it is totally different (like my root is 7 not 6 like my book says).

2. In which order are the values in a splay tree inserted?

Is it possible to ''get'' the order of the values that are inserted in the left tree example above? In other words, how is this tree made (in which order are the nodes inserted to generate the following tree). Is there a way to figure this out?

Answer 1

Re deleting a node: both algorithms are correct, and both take time O(log n) amortized. Splaying a node costs O(log n). Creating a new link near the root costs O(log n). Splay trees have a lot of flexibility in how they are accessed and restructured.

Re reconstructing the sequence of insertions: assuming that the insert method is the usual unbalanced insert and splay, then the root is the last insertion. Unfortunately, there are, in general, several ways that it could have been splayed to the root. An asymptotic improvement on the obvious O(n! poly(n))-time brute force algorithm is to do an exhaustive search with memoization, which has cost O(4^n poly(n)).