CODEWITHSUNDEEP
data-structurestreebinary-treebinary-search-tree
chickenman
chickenman

Reputation: 798

Is a Zig-zig rotation in a Splay Tree different than two right or two left rotations?

I understand that the Zig-Zag rotation is basically an AVL double rotation. Is a Zig-zig rotation something different than two left or two right rotations? I thought they weren't but if I merely do 2 right rotations for something like the image below I'll get a wrong answer.

If it is indeed not the same thing, is it then correct to assume that a Zig-zig rotation is a special type of rotation?

enter image description here

Upvotes: 2

Views: 1051

Answers (1)

uSeemSurprised
uSeemSurprised

Reputation: 1834

The difference is which nodes you use to do the rotations and the specific order in which those rotations are performed. Lets call the nodes that we use as a reference to rotate as base nodes, so in the zig zig case we have 2 base nodes, the first is the parent of the x in the example i.e p, we first do a right rotation along this node and then we do a right rotation along the node x. In the case that you mentioned the 2 right rotations will be performed on the same nodes. So to conclude they are different in terms of which nodes we use to rotate and in which order we use them, zig zig first does a right or left rotation of the parent before doing a right or left rotation of the node.

Upvotes: 3

Related Questions