This lecture will continue where we left off in Tuesday's lecture, discussing AVL Trees.  We will continue with the restructuring an AVL after an insertion/deletion cause it to lose its balance property.   The sections covered in Tuesday's lecture apply to this lecture as well.  In addition, Proposition 7.2 (first edition) / 9.2 (second edition) will be examined.  See Additional Material below.

Here are the sections of the textbook:

• 1st edition book:

• 2nd edition book

Additional Material:

• Implementation of a dictionary with a binary search tree in pseudocode (PDF format). (written by Professor Franck vanBreugel).
• Proof of Proposition 7.2 (first edition) Proposition 9.2 (second edition) (PDF format) (written by Professor Franck van Breugel).