This lecture will continue with our discussion of AVL Trees.  Last week, the process of balancing an AVL tree after it become un-balanced" due to a removal or insertion were described.  In this lecture, the algorithm described in the book will be discussed briefly as will the AVL Tree implementation.  Hash Tables will then be discussed for the remainder of the lecture.

NOTE: Hashing is covered sparingly in the first edition book.  If you are using the first edition book, take a look at the material related to hash tables in the second edition book (section 8.3).  In addition, see the lecture notes regarding Hash Tables.

Here are the sections of the textbook:

• 1st edition book:

• 2nd edition book

Additional Material:

• Proof of Proposition 7.2 (first edition) Proposition 9.2 (second edition) (PDF format) (written by Professor Franck van Breugel).
• Implementation of a Dictionary using a Hash Table (PDF format) (written by Professor Franck van Breugel).