Fall 2016, Siena College

Lecture 35: Binary Search Trees
Date: Monday, December 5, 2016

Agenda

• Announcements
• Exam 2 graded but holding off returning
• Good times for a final exam review? Evening of reading day?
• Lab 10: Huffman Trees continues
• Binary Search Trees
• BST implementations
• Balanced Search Trees
• AVL Trees

Due at the start of class, Friday, December 9.

Please submit answers to these questions by the start of class. zyBook activities should be done right in your zyBook, and all others should be submitted to Blackboard under "Lecture 35 Assignment" . We will discuss these questions at the start of class, so no late submissions can be accepted.

In addition to the questions below, you can complete the activities in your zyBook from Chapter 17 sections 3 through 11 for up to 25 bonus lecture assignment points, any time before the end of the semester.

Ignoring case, the string

```She sells sea shells down by the sea shore.
```

has the following character frequencies:

(s,8), (h,4), (e,7), (_,8), (l,4), (a,2), (d,1), (o,2), (w,1), (n,1), (b,1), (y,1), (r,2), (.,1)

1. Construct a Huffman tree based on these frequencies. (8 points)
2. Encode the substring "sea shore shells" using the code specified by your tree. (6 points)
3. 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. (4 points)
4. Now, starting with the original tree, insert 32 then 31. Show any rotations needed to maintain the AVL condition. (4 points)

Terminology

• binary search tree
• balanced tree/balance condition
• red-black trees
• AVL trees/AVL condition/single rotation/double rotation