CSCI 311 -- Algorithms and Data Structures

Homework 5 - Problem Set

12 Points
Due Wednesday 30 October 2019 5 p.m.

This problem set will give you practice on a variety of problems that might show up on the next exam. If you hand it on time I will grade it and get it back to you by next Friday.
  1. (5 points) Starting with an empty binary search tree, insert each of the following keys and rotate it to the root in the specified order:

    6   1   18   7   15

  2. (7 points) Starting with an empty red-black binary search tree, insert the following keys in order::

    12   5   23   9   19   2   21   18   7

    Show the tree immediately after you insert each key, and after each time you deal with one of the book's cases 1, 2, or 3 (that is, if dealing with one case leads to another, show the additional case as a separate step). You can rotate and recolor as part of a single step if you want; you don't need to draw the results separately unless it helps you.

Write up your answers and hand them in.