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$
  • 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
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$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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