CODEWITHSUNDEEP
data-structuressplay-tree
Pauline
Pauline

Reputation: 3836

Splay trees: how do the zig-zig and zig-zag rotations work, in details?

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

Splay 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: Splay example 2

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:

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.

Upvotes: 1

Views: 2150

Answers (1)

karastojko
karastojko

Reputation: 1181

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).

Upvotes: 0

Related Questions