CSC 378 tutorial on Binary Search Tree rotations
In this tutorial, we discuss the ``rotation'' operation in Binary
Search Trees (BSTs).
Click here for a review of binary
search trees and the ``BST property.''
A rotation operation restructures a BST while maintaining the BST
property. Restructuring is useful to maintain a short or ``well
balanced'' tree in which searching for a key takes little time.
Click here for a review of searching.
In this tree, a search will, in the worst case, traverse a
root-to-leaf path of seven nodes (e.g. when searching for 5). However,
we can restructure the tree so that we only have to traverse four
nodes in the worst case.
Now, the longest root-to-leaf path contains four nodes, not seven (e.g
when searching for 5 or 82). In the worst case, a search will have to
traverse four nodes, which takes only about half the time that it did
in the original tree.
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.)
Right and left rotations
In moving nodes to the right, you performed a right rotation.
Similarly, moving nodes to the left involved a left rotation.
Note that the BST property is maintained by the rotation operation:
For any node n , all keys in the left subtree of n
are less than the key of n and all keys in the right subtree
of n are greater than the key of n. This property
remains true after the rotation.
Things get a bit more complicated when there's a node between
the two nodes being rotated.
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 a rotation, the middle node switches sides in the tree.
Things are only slightly more complicated when the rotation occurs
inside the tree.
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?
In a rotation, the link above the topmost node also switches sides.
Finally, here's a puzzle: Show that the following tree can be
perfectly balanced using left and right rotations. Each root-to-leaf
path should have exactly four nodes when you're done.
Hint: One approach is to construct a tree with a single, long, left
path. Then balance it about the root and recurse on the subtrees. There
are faster approaches, too.
the BST property,
Java source code
(Other applets by James Stewart)