CS 112

CS 112 Summer 2, 2020 -- Homework Five

Due Friday, August 17th @ midnight with 24-hour grace period

The submission time for the entire assignment is the submission time of the last file submitted.

Introduction

You must observe the following requirements (for all homework submitted in this course):

All programs should be literate, i.e., easily understandable by a human (say, your grader) and follow the Java Style Guidelines for CS112 posted on the class web site;
All files for this homework should be submitted using WebSubmit, following the instructions on the class web site;
You may not use data structure libraries such as ArrayList, since we are learning to write Java from the ground up and you must learn how these libraries are built; however, you are free to use (unless specifically directed otherwise) the basic libraries String, Character, Scanner, and Math; for this assignment, you may also use Double.parseDouble(....);
You may freely use code from the class web site, the textbook, or lecture (unless specifically directed otherwise) as long as you cite the source in your comments; but you may NEVER use code from the web or other students' programs---this will be considered plagiarism and penalized accordingly.

Part A: Analytical Problems (10 points)

Before getting started on the remaining problems, review the lecture and textbook materials on binary search trees and recursion. The following problems have to do with the BST in this diagram:

1. (5 parts): For this tree, give the (a) size, (b) depth of the node 31, (c) height, (d) length of the path from 11 to 49, and (e) list of all leaf nodes.

Solution: (a) 11 (b) 3 (c) 3 (d) 3 (e) 5, 10, 17, 31, 49

2. (2 parts) (a) Draw the result of inserting the keys 15, 7, 16, 12, & 13 into this tree; (b) assuming we can only insert integers, and no duplicates, into the original tree, what keys could possibly be inserted to the left of 31?

Solution: (a) Sideways printout:

(b) The only non-duplicate integers would have to be bigger than 19 and smaller than 31, so: 20, 21, ...., 29, 30.

3. (2 parts) (a) Draw the result of taking the tree in the diagram and deleting the root three times using the deletion algorithm from lecture (on 3/13); (b) suppose we do not wish to unbalance the tree by deleting from the same side each time, and we decide that we will alternately delete from the right, left, right, left, etc. (starting with the right); delete the root of the tree in the diagram 4 times using this new strategy and show the resulting tree.

Solution: (a)

(b)

4. (2 parts) Let us call a tree "perfect" if it is a perfect triangle, i.e.,

Suppose H is the height of a perfect binary tree, and N the number of nodes; (a) express H as a function of N, and (b) N as a function of H.

Solution: Clearly there is some relationship between N and 2^H and between H and log₂(H); always a good idea to try a few examples in order to understand the details:

  H      N      2^H      log2(N)
 ---    ---    -----    ---------
  0      1       1        0
  1      3       2        1.56
  2      7       4        2.81       
  3     15       8        3.91
  4     31      16        4.95

Thus, we have (a) H = floor(log₂(N)) and (b) N = 2^(H+1) - 1

, where floor(K) = (largest integer <= K) (same as "(int) K" in Java).

5. (2 parts): Suppose we are going to insert the letters A, B, C, and D, into an initially empty BST. If we insert them in order, we get a pathological tree which is really just a linked list (and whose worst case time to find a node is linear, i.e., O(N)). But there are many different worst cases! (a) List 5 more of the the possible worst cases (hint: there are 8 in all!). Now suppose we have the letters A, B, C, D, E, F, and G. We would like to have a perfect tree which has the shape of a perfect triangle: for example, we could insert in the order D, B, F, A, C, E, G. (b) List 5 more of the possible insertion orders that would give you a complete binary search tree.

Solution: (a) The worst cases occur if each time you pick an extreme value (largest or smallest) of those that remain:: ABCD, ABDC, ADCB, ADBC, DCBA,DCAB, DABC, DACB. (b) For a perfect tree, you must pick the median to be the root of the subtree each time, so any order which has D at the beginning, B before A and C, and F before E and G:

D...(any ordering of BF).... (any ordering of ACEG): DBFACEG, DBFGECA, DFBGECA, etc.

DB... (anything other than E or G) .... F....: DBACFEG, DBCFAEG, etc.

DF... (anything other than A or C) .... B....: DFGBAEC, DFEBCAE, etc.

6. Insert the following sequence of keys into an intially empty 2-3 tree. You should write all the trees down as you do the transformations (this is what would be expected on an exam) but for the purposes of grading this exercise you can just draw the final tree that results. 15, 25, 20, 10, 12, 4, 19, 6

Solution: The tree created (written sideways) would be:

7. Consider the following 2-3 tree:

Suppose we count ONLY comparisons between two keys. (i) How many comparisons would necessary to find the key 10? (ii) How about 140? (iii) How about 60? (iv) Which key(s) occurring at leaf nodes would require a minimum number of comparisons? State which and how many comparisons. (v) Which key(s) would require a maximum number of comparisons? State which and how many comparisons. (vi) What is the average number of comparisons to find the keys in this tree (count for all and then divide by the size of the tree).

Solution: (i) 3 (ii) 6 (iii) 4 (iv) the minimum number of comparisons occurs with 10 and 30, which each require 3 comparisons (v) 140 requires 6 comparisons (vi) summing in level order: (1+2+2+3+3+4+3+3+4+4+4+4+5+5+6+5)/16 = 58/16 = 3.625.