# Rotations in splay trees

I am having some difficulties splaying the element 4 to the root. Considering the following splay tree.

0
\
1
\
2
\
3
\
4


Could anyone show me the steps how to get the 4 to the root?

• Strange title? Have a look at splay trees and their rotations at wikipedia. Then tell us what you don't understand. Commented Dec 14, 2014 at 14:05
• Sorry not for expression where the problems lies.. Commented Dec 14, 2014 at 20:12

Just follow the algorithm. First you have to do a zag-zag-rotation, which gives you

0
\
1
\
4
/
3
/
2


Then you have to do another zag-zag-rotation and you obtain as the result of splay(4) the tree

    4
/
1
/ \
0   3
/
2

• That's also how i Imagined it would look like, but I have a hard time understanding how the rotations from the first to the second is performed.. Commented Dec 14, 2014 at 20:13
• Just follow the rules (see wikipedia) and keep the subtrees hanging off the three nodes that are involved fixed. Commented Dec 14, 2014 at 20:17