CSSE 230
Data Structures and Algorithm Analysis

Homework 6  -  40 points

Don't forget that you should be making notes about your team and team members, for eventual use in the EditorTrees team evaluation.

To Be Turned In

Questions 1 and 2 should be submitted to the drop box and the coding question(s) should be committed to your SVN repository.  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?
  3. (20 points) Checkout the PreorderBuildTree project from your SVN repository. In this problem, you'll create another Binary Tree constructor, one that constructs a Tree with Character data from two pre-order lists: a string of data and a string of children. For example, t = BinaryTree("abc", "200") would create a full tree of height 1 with root = a and two children b and c, and t = BinaryTree("cbad", "2L00") would create the minimum height-balanced tree of height 2, with an in-order traversal of "abcd".

    As a larger example, this tree was built from the strings, "ARGEDFKJHWS" and "R22200LL0L0":

    This format should sound familiar - see HW3 and its solution for more details. Note that this can construct any binary tree of characters, not just BSTs. I am posting two hints here, but I strongly suggest that you try to develop an algorithm first before referring to them.

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