Homework 3 Clarifications

Updated 1-27-2015

• Problem 2

A few folks have been confused by the statement that you should "assume nothing about the height of Y while talking about the height of X" and vice versa. This was meant to be a simplification, but if you would instead would like to explicitly discuss the 8 possibilities of values of h-1, h, and h+1 for both X and Y that will be plenty sufficient for our purposes (no need to mention X=h and Y=h). You definitely do not need to go so far as to consider all possible values for X while considering the values of h-1 and h+1 for Y (or vice versa).

Updated 1-24-2015

• Problem 1

The problem is asking you to throw an exception of your choice if one of the properties is violated. You do *NOT* need to fix any problem you find.

You may assume that there are no duplicate keys.

If you like, you may assume that keys are ints, and use int.min and int.max if that is useful.

Full points will be given for solutions that use only one pass through the tree. Significant (e.g. max -1) points if your solution uses more than one pass. Edit: Doing this in multiple passes, if each pass linear, it is fine, as long as there are a constant number of passes. Whatever you do I recommend thinking carefully about whether your solution has linear running time and is correct!

• Problem 2

Here are some things that are true to keep in mind:

1. The original tree is balanced
2. Z originally had height = h
3. Insertion @ Z caused an imbalance to be detected at node a (and only at node a) causing a case 4 rotation to be the appropriate solution (i.e. another "case" was not chosen as the appropriate solution)

You need to show your reasoning why you think:

1. Original height of Y cannot be h-1
2. Original height of Y cannot be h+1
3. Original height of X cannot be h-1
4. Original height of X cannot be h+1

You should argue them by showing how each of those violates the conditions given in the problem