Computer Science 431

Algorithms

Spring 2013, The College of Saint Rose

Agenda

- Announcements
- Problem Set 4 due now
- Balanced trees
- AVL trees

Due at the start of class, Tuesday, March 26.

Please submit answers to these questions
either as a hard copy (typeset or handwritten are OK) or by email to
*terescoj AT strose.edu* by the start of class. Please use a clear subject line
when submitting by email (*e.g.*, CSC 431 Lecture
Assignment 17, Joe Student). We will discuss these
questions at the start of class, so no late submissions are
accepted.

This is a much longer than usual lecture assignment, so please plan accordingly.

- Levitin Exercise 4.5.7, p. 166. (4 points)
- Levitin Exercise 4.5.8, p. 166. (4 points)
- Start with a complete AVL tree containing the values 10, 20, 30, 40, 50, 60, and 70. Insert the values 31, then 32, showing any rotations needed to maintain the AVL condition. (5 points)
- Now, insert 32 then 31. Show any rotations needed to maintain the AVL condition. (5 points)
- Design an AVL tree of height 4 such that if one more value is inserted, the root is the first unbalanced node on the way back up the tree. Once you have such a tree, insert that value, perform the proper rotation(s) and verify that the AVL condition is once again met. (4 points)
- Levitin Exercise 6.3.7, p. 226 (5 points)