Homework 6: AVL trees

This is the archived website of IC 312 from the Fall 2014 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

• Due before class on Wednesday, October 15

Remember to turn in a neat final draft of this homework on a separate sheet of paper.

Draw the trees that result from performing the following rotations.

1. Rotate left at the root node.
2. Rotate right at the node labeled 24.
3. Rotate left at the node labeled 13.
4. Rotate right at the root node.

Copy each of the following trees and write in the balance factor at every node. Then tell me whether it's an AVL tree, and why or why not.

For each of the following problems, start with an empty tree and insert each of the given nodes, in the order given. Rebalance the AVL tree after every insertion. You do not need to draw every single step separately, but you must draw the tree immediately before every rotation, and say what the rotations are.

For example, if the problem is to insert A, B, C, D, you could write:

1. L, E, U, R, O, C
2. C, G, E, R, V, J, O, S
3. O, R, C, B, V, X, G, U, P, H