Lecture 16 Objectives

KNOW:

• That a BST has linear worst-case performance for operations that involve searching for an element
• That an AVL tree is a BST with the additional invariant that the tree is height-1 balanced
• That an AVL tree can guarantee logarithmic worst-case performance for searching

BE ABLE TO:

• Identify a binary search tree as either satisfying or not satisfying the AVL tree invariant
• Show the result of adding an element to an AVL tree

Sample Exam Question:

Here's an AVL tree:

                      44
                     /  \
                    /    \
                  32      96
                 /  \     
               30    40  

• Identify the pivot node
• Explain why a single rotation is needed
• Draw the AVL tree that would result from adding 20