Answer to Question 37-1

Insertion using the basic algorithm yields the following tree.

The first node above 4 that is out of balance is the node containing 5. Its left subtree has height 2 and its right subtree has height 0. Two steps down from that node toward the higher subtree involves a left step then a right step. So this is a zig-zag and calls for a double-rotation. The resulting tree is as follows.

The root (10) is already height-balanced, so this is the final tree.