Computer Science 210
Data Structures

Fall 2016, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

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

Agenda

Lecture 35 Assignment

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