Computer Science 210

Data Structures

Fall 2016, Siena College

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)

- Construct a Huffman tree based on these frequencies. (8 points)
- Encode the substring "sea shore shells" using the code specified by your tree. (6 points)
- 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)
- 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