This note focuses entirely on the topic of rotation operations in binary search trees (BSTs) and especially their use in partitioning a BST at the median to balance it.

Notes on the other questions on the Final are the other information page.

Since this topic arose very late in the course, I will be very explicit in telling you just what you need to know and do on this topic for the Final Exam. Below I give a number of color illustrations of the operations.

The rotation operation in the book is introduced in the section on "Insertion at the Root in BSTs", Sec. 12.8. You need only concentrate on understanding the rotation operation itself, as shown in Figures 12.12 and 12.13 and in Program 12.12, and you needn't concern yourself with the operation of insertion at the root.

Instead, we will concentrate on a simple series of rotations that can bring any chosen node up the tree to the root. To discuss this, let's be sure we understand the concept of the median. the median is the middle element of a set of ordered elements, the element for which half the remaining elements are less and half are greater. Thus, the median of 1, 3, 5, 7, and 9 is 5. The median of 1, 4, 5, 472, and 912 is also 5. The median of the set of numbers 700, 32, 4, 5, and 1 is also 5. If there are an even number of elements, the median is not precisely defined, so the median of 3, 7, 10, 14, 30, and 100 is somewhere between 10 and 14. But for large collections of numbers the median is quite a useful statistic.

If we do have a BST with an odd number of nodes, then bringing the median node to the root would lead to an equal number of nodes on both sides of the root. So with respect to the root, the BST is balanced. If this is repeated for every subtree then the entire tree becomes balanced and is therefore as shallow as possible so no search or insert operation should require more than lgN steps. This is illustrated in Figs. 1a and 1b below.

From the figures above, it is clear that if we could put the median of the root and the medians of every subtree at their respective roots, we'd have a fully balanced tree. This can be accomplished by rotations.

A simple right rotation is illustrated in Figures 2 and 3 below. The main point to note is that node 6 which is between the old and new root of the subtree is moved from being the right node of 5 to being the left node of 8, so 6 is still positioned between 5 and 8. A left rotation is very similar, but moves the left child to the root of the subtree, paying special attention again, to the node whose value is between the two nodes being moved.

To learn more about how a series of rotations can bring the median element to the root, study the example of partitioning in Fig. 12.17. If you don't like the letters used for keys in the example and prefer numbers, then you could replace them with A=1, C=2, E=3, H=4, M=5, R=6, S=7, T=8, and X=9. This also makes it clear that the M=5 key is the median node of the total of nine nodes.

Finally, you might ask, what do you need to know for the Final Exam? Basically, you have to be able to do the type of partitioning using the median as shown above and in Fig. 12.17 of your textbook. You can look at the code in Programs 12.15 and Program 13.1, but the question will simply be one of showing pictures of rotations and not trying to relate it to the recursive procedures in those two code examples.