Homework 3 Clarifications

Last updated Mon 1-28-2013

• Problem 1
• For the AVL tree insertions you are asked to show the tree after each insertion. If there is no change to the tree after an insertion (no rotations) it will be o.k. to just circle or otherwise highlight the new additions rather than redrawing the tree. If you choose to do this you run the risk of not being completely clear, so I would urge you to add a comment that describes fully what you are doing in that step.
• Problem 2
• For Problem 2 you are asked to write pseudo code. It is hard to give a precise definition of pseudo code, as it is by definition "pseudo". The point is to make it clear that you do not have to write full on Java with class definitions, import statements, all semicolons in the right place, etc. For our class, when in doubt about how much detail to provide, provide MORE detail. I say this because the most common mistake students make is to NOT provide enough detail. The way to be sure you are providing enough detail is to go almost to the level of Java. As a matter of correctness this means you should include some checking for edge or boundary cases (e.g. nulls). We won't necessarily care if you handle them by raising an exception or returning a special value (unless that is part of the specification), but we will care that you show that you are taking them into account. And although we won't be sticklers about semi-colons, details like the right number of closing braces or right indentation, or = vs. == can be important just for determining control flow and correctness of an algorithm - so don't be totally sloppy there either or you risk having your algorithm be misinterpreted. If you are assuming anything in your pseudo code, it is also important to state that. It is fine to write helper methods - don't feel constrained to write only one method. Also don't hesitate to put comments in your pseudo code if you think it is useful.
• You are asked to provide a linear time algorithm. That is the only running time bound we will be looking for - we won't care about constant factors. As long as your algorithm is linear time, that is good enough.
• Key means the key as in (key, value) pair used for dictionaries. The key is what is referred to when we say that you must have a binary SEARCH tree - the keys must be ordered. Data refers to the value in the key value pair.
• You can assume that you have access to the overall root of the tree.
• [2013-01-28] - You can assume that there are no duplicate keys in the tree. (As you would expect with any dictionary.)
• Problem 3
• This question is trying to get you to look more closely at the diagrams from lecture that demonstrate what happens in the general case of a AVL rotations (and that the particular type of rotation does in fact convert something that is an AVL tree of a certain height before the insertion into an AVL tree of the same height after the insertion). Each triangle is assumed to be a subtree that is AVL balanced. Each triangle is labeled with its height so you can clearly see that after the rotation is applied, the resulting entire tree will be AVL balanced.

  What is in question here is not whether the particular rotation proposed does the right thing. Instead it is getting you to think a bit about something that might have occured to you when looking at the diagrams - why is subtree X labeled as height h? or why is subtree Z labeled as h+1? Does it have to be that way? Your arguments on why the subtrees listed cannot have heights other than those given is not based on an argument like "because then the rotation will not work". Your arguments should be based on things in the state of each tree prior to the insertion and after the insertion but before the rotation.

  Base your answer on what you know about the current situation: You know that an insertion has taken place in subtree Z, that node a is where an imbalance was detected, that subtree Z has height h before the insertion and height h+1 after the insertion. You also know that the entire tree and each of its subtrees were AVL trees before the insertion (all subtrees in an AVL tree must also be AVL trees).

• It is sufficient to state what the problems are with the two height cases of h-1 and h+1 for both x and y. You don't need to specifically address what happens when x and y are > h+1 or < h+1.
• It is sufficient to give a verbal argument (a sentence or two for each item is fine). A proof is not required.
• If there is more than one reason why x, y, or z cannot have a particular height, it is sufficient to only give one of the reasons.
• Problem 4

[2013-01-28] In case someone read the problem before I added in the comma between 12 and 17, notice that there is now a comma between the 12 and the 17! :-)