## CSE 247 Module 11: Searching Graphs

### Studio

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:
• How are they different from red black trees?
• How is their asymptotic performance different?
• The article above claims they are faster. If so, why do most libraries implement red-black instead of AVL trees?

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.

• If there is a file for you to complete in studiowriteups, please respond to the questions and supply any requested information.
• You must commit and push all of your work to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.