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?
$\begingroup$
$\endgroup$
-
1$\begingroup$ Strange title? Have a look at splay trees and their rotations at wikipedia. Then tell us what you don't understand. $\endgroup$ – Hendrik Jan Dec 14 '14 at 14:05
-
$\begingroup$ Sorry not for expression where the problems lies.. $\endgroup$ – James Dec 14 '14 at 20:12
$\begingroup$
$\endgroup$
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
-
$\begingroup$ 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.. $\endgroup$ – James Dec 14 '14 at 20:13
-
$\begingroup$ Just follow the rules (see wikipedia) and keep the subtrees hanging off the three nodes that are involved fixed. $\endgroup$ – A.Schulz Dec 14 '14 at 20:17
