IC 312 Fall 2022 / HWs

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

Homework 06: AVL rotations

Name: _____________________________________________ Alpha: ___________________

Describe help received: ________________________________________________________

Print this page
  • Due before class on Friday, October 7
  • This is a written homework - be sure to turn in a hard-copy of your completed assignment at the beginning of class on the deadline.

  1. In the following tree, annotate each node with the HEIGHT of that node.

  2. Is the tree for the previous question an AVL tree? Why or why not?

    If not, what rotation(s) are needed to make it an AVL tree?

    (You don’t have to actually do the rotations, but be specific about what kind of rotation(s) and at which node(s).)

  1. Rebalance the following tree by performing a single rotation at node 34.

  1. Rebalance the following tree by performing a double rotation at node 76.

  1. Starting with an initially empty tree, draw the AVL tree that results after inserting the following keys, one at a time, in this order:

    P, R, U, C, B, Q, D, F.

    Besides showing the final tree, you must also re-draw the tree and clearly indicate every time a rotation occurs.

  1. Starting with the following AVL tree, draw the tree that results after removing node 36 and rebalancing appropriately.