In-Lab 4--Rotations with AVL trees

Due: at the end of lab, October 7, 2004

Objective:
Practice doing rotations with balanced BSTs

AVL rotations


• References: if you need help in the way AVL rotations work, any of the following references should help you. A couple of them are applets that will build the AVL tree for you.
  • Hunter's lecture on AVL trees and rotations
  • An applet that builds trees, when you give the input
  • Another applet
  • Another Applet that is working today
  • Defintions and explanations
• Build these AVL trees using single rotations. You should add the values to a BST in the order given, then when the tree becomes out of balance, balance it. Be sure that the tree is balanced each time before you do an insertion.
  1. 1, 2, 3, 4, 5, 6, 7
  2. 8, 5, 12, 3, 2, 1

     Build these trees using double rotations

  3. 30, 20, 40, 35, 37
  4. 82, 75, 98, 60, 79, 80

     Build these trees using whatever rotations are necessary

  5. 4, 2, 6, 1, 3, 5, 7, 16, 15, 14, 13, 12, 8, 10
  6. 48, 76, 27, 52, 87, 50, 51, 92, 49, 52

Hand in:


Hand in your diagrams of trees, showing the rotations, reasonably neat. It is expected that every diagram will be correct, since you can check it with the applets. Just be aware you will not have the applets available on an exam :-)(You have two hours to do this, so don't get too impatient)