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.

Example

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.

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.)

If you were using a Java-enabled Web browser, you would see a binary search tree instead of this paragraph.

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.

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.

If you were using a Java-enabled Web browser, you would see a binary search tree instead of this paragraph.

In a rotation, the middle node switches sides in the tree.

Internal rotations

Things are only slightly more complicated when the rotation occurs inside the tree.

If you were using a Java-enabled Web browser, you would see a binary search tree instead of this paragraph.

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.

Example

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.

If you were using a Java-enabled Web browser, you would see a binary search tree instead of this paragraph.