0
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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    
$\endgroup$
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
    Commented Dec 14, 2014 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
    Commented Dec 14, 2014 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.