CSE 247 Module 11: Searching Graphs


The following exercises are for your work in studio. Try to solve them and consult the TAs as needed for help.
    Using this red black visualizer, perform the following exercises. Record your answers in the studio11.txt file in the studiowriteups folder.
  1. Devise a sequence of insertions of 15 integers so that no rotations are ever necessary.
  2. Insert the following into the tree. Before each insertion, predict what should happen and then observe the colorings and rotations. Try to become better at predicting when coloring alone suffices and when rotations are necessary. (no need to write anything on this in the writeup file)
    Insert: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
  3. Run the above insertions again, and record in the write-up file the black-height of the tree after each insertion. Remember the black height includes all nodes but the root including the NIL nodes even if they are not shown.
  4. What condition in a red-black tree triggers any of the cases for rebalancing?
  5. Spend about 15 minutes investigating AVL trees, recording answers to the following questions in the write-up file:
    The slides on depth-first search begin here
  6. Consider the pseudocode for the depth-first search algorithm:
    and the following slide from lecture:
    In what order where vertices shirt, watch, undershorts, and socks considered by the depth-first search code at line 5 of the left panel above?
  7. Suppose instead that line 5 considered the nodes in the following order
    watch, socks, undershorts, shirt
    Draw the corresponding depth-first spanning tree and show the on-entry and on-finish values assigned to each vertex (the time values in the code).

    Where you have other choices for which way to explore the tree, decide on your own which way to go.

  8. Perform a right-to-left preorder traversal of your tree to list the nodes in toplogical order.
  9. How does your order compare with the one I showed on the slides?
    The answers to the above questions are hidden in this file. The username for access is cse247. The password can be given to you by the TAs.

  10. Define the listing of a tree as the order in which nodes are acted upon by a tree traversal algorithm. For preorder, nodes are acted upon before visiting their children. For postorder, nodes are acted upon after visiting their children.

    Prove that the reverse of a postorder listing of a tree is the same as the right-to-left preorder listing of a tree.

    Hint: Consider complete trees only if that helps, and use induction on the height of a tree.

Submitting your work (read carefully)

Last modified 14:54:22 CDT 31 October 2016
When you done with this studio, you must be cleared by the TA to receive credit.

This demo box is for studio 11
Last name WUSTL Key Propagate?
(NOT your numeric ID) Do not propagate
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others
3 Copy from 3 to all others
4 Copy from 4 to all others

TA: Password: