CSSE 230
Data Structures and Algorithm Analysis

Homework 7 - 20 points

To Be Turned In

Upload your solution to the Moodle assignment. 

You may earn a late day by submitting all parts early, or use a late day if you submit any part late.

  1. (10 points) On paper, start with this red-black tree:

    (If it is hard to see, the two children of the root are red.) Insert the following nodes using the top-down insertion algorithm and show what happens (both rotations and re-colorings): 20, 10, 25, 27, 40. Please denote the red nodes very clearly, using red (best) or a key (acceptable). Work carefully - it will be hard to give partial credit if your answer is incorrect.

  2. (10 points) Let maxNNDepth(T) and minNNDepth(T) denote the number of (non-NULL) nodes on the longest and shortest (respectively) paths from the root to a NULL_NODE in tree T. Note that maxNNDepth(T) = 1 + h(T), where h(T) is the height.

    1. (6 points) Explain why maxNNDepth(T) ≤ 2*minNNDepth(T) for any red-black tree T, using properties of red-black trees.
    2. (0 points) Nothing to do, just an observation: it can be shown that maxNNDepth(T) ≤ 2*minNNDepth(T) for any height-balanced (AVL) tree T, as well. [If you're curious and have time, you might try proving this by induction over the height. NO bonus points for this, just for fun. Suggestion: you might find it easier to prove that h(T) ≤ 2*minNNDepth(T) - 1. Also, in the general case, you may "assume without loss of generality" that (say) h(TL) ≤ h(TR).]
    3. (4 points) What can we conclude about the asymptotic best-case running time of an unsuccessful search on either type of tree?

Other problems for your consideration

6.31[6.17], 6.37[6.22], 7.3[7.3], 7.4[7.4], 7.23[7.19], 7.29