I need help understanding a specific example of zig-zag and zig-zig rotations in splay trees. I have read about them in a book, and on Wikipedia as well as a few other online resources, and whilst I can understand them when they are applied on simple trees (i.e. trees with very few nodes), I get lost when I see examples of them applied to bigger trees (i.e. trees with more nodes).
In particular, I don't understand at least one of these 2 examples:
Example 1
(this is not the full example but this is the part of it I don't understand)
We can see in (1) that the node which is about to be splayed is the right child of a left child and therefore we have to do a zig-zag. I can therefore understand what happens between (1) and (2), where the node being splayed has now taken the place of its parent. In my understanding, the entire zig-zag operation has taken place there. So the first splay is over, and we still need to splay the node until it is at the root of the tree.
I don't understand what happens between (2) and (3). In (2), the node being splayed is the left child of a left-child, so I expected a zig-zig operation whereby the node being splayed rotates around its grandparent, which is (20, Z). Instead, the slide shows a rotation with its parent, (10, A). Why? What I would have expected there is that our splaying node (8, N) does a zig-zig and thereby takes the places of (20, N) which is its grandparent, and also the root. Why is the parent involved instead?
In the resource where I found this example (my lecturer's slides), a zig-zag rotation is described as "rotate node with its parents, then rotate node with its grand-parent". Is that what happens here? Is that the reason why between (2) and (3), (8, N) rotates with (10, A) instead of (20, Z)?
I am very confused about this description, because then the zig-zig rotation is described as "rotate node with its grand-parent, then rotate node with its parent". However, everytime I have seen an example of zig-zig rotation, there is always only one rotation with the grand-parent of the node and that's it. I have never seen 2 rotations.
Then there is this other example:
In that example, the splay operation involves a zig-zig. As you can see, there is only 1 rotation. Then there is a second splay because the node being accessed is still not in a root position.
What I would have expected here is that:
- Either the description of zig-zig and zig-zag provided are correct, and therefore there would have been 2 rotations in the second example: one around the grandparent of the node, then one around its parent.
- Or, the description provided are wrong, so then the second example is correct, but the first is not as we rotated the node with its parent and not its grandparent whilst it was in a zig-zig position.
Can you let me know if any of these 2 examples is wrong, and which one? If none of them is wrong, where am I wrong?
Thank you for your help.
PS: As it is obvious that I am a student, I would just like to let you know that I do not ask this question in the context of an assignment, and therefore I am not cheating. I have, however, an exam this coming Monday and I hope to have any misunderstanding clarified before I sit the exam.
Splaying of a node x is sequence of splay steps until x becomes root of the tree. These steps are zig, zag and zig-zag.
For a node x, its parent p and p's parent g, zig-zag operation on node x is defined for a case where p is not the root and x is the right child of p and p is the left child of g: first rotate left x, then rotate right x. Your first example shows exactly that case: zig rotates left x = (8, X) and its parent p = (7, T), then zag rotates right (8, X) and g = (10, A). So, this example shows zig-zag on x, but the splaying itself is not done because x is not root yet (meaning more splaying steps is necessary).
zig-zig is defined for the case when both x and p are right children of their respective parents: first rotate left p, then rotate left x. The second picture of your second example shows the result of zig-zig on x = (40, X), p = (37, P), g = (35, R): first p is rotated left, then x is rotated left. Third picture of the second example shows additional zig operation on x (rotating left x since its parent p is the root) moving to the root and finishing splaying of x.
(All zig, zig-zig and zig-zag operations have their symmetrical counterparts).