To restructure the tree, click on the node to the immediate left of the root. Then click on the node to immediate left of the new root. Do this until the tree is balanced. (If you put too many nodes on the right, they can be moved back by clicking on the node to the immediate right of the root.) |
Consider this tree, in which 12 is between 9 and 15. If we rotate 9 up to the root, where does 12 go? Try it with a right rotation on 9. Then see what happens if you do a left rotation on 15. |
In this tree, when you perform a right rotation on 15, what happens to
the link above 42, which is 15's parent? Try it.
Perform the opposite rotation on 42. What happens to the link above 15, which is now 42's parent? |
(Other applets by James Stewart)