Computer Science 385
Analysis of Algorithms
Spring 2011, Siena College
Lecture 17: AVL Tree Wrapup; Introduction to Heaps
Date: Tuesday, March 22, 2011
Agenda
- Announcements
- resubmissions of problem 8 from exam 1 due now
- Exam 1 recap
- Problem set 3 recap
- Problem set 4 out
- Lecture assignment recap
- AVL tree wrapup
- Array representation of binary trees
- Priority queue (review)
- Heaps
Lecture Assignment 17
Due at the start of class, Thursday, March 24.
Please submit answers to these questions
either as a hard copy (typeset or handwritten are OK) or by email to
jteresco AT siena.edu by the start of class. Please use a clear subject line
when submitting by email (e.g., CS 385 Lecture
Assignment 17, Joe Student). We will discuss these
questions at the start of class, so no late submissions are
accepted.
- Levitin Exercise 7.2.7, p. 264.
- 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.