COSC 160: Data Structures

Homework 5
Fall 2020

Due: F 11/6 @ 11:59 PM
2 points

You must upload a single PDF document to Canvas. Feel free to use pencil and paper to do this homework. If you do, please do not submit a PDF document containing high-resolution digital photographs. Use a PDF scanner such as GeniusScan to produce black-and-white scans for a PDF document.

1. Insert the following keys into a red-black tree: e, h, m, p, d, f, o, s, q, r, t, u. Draw the tree after each insertion. Identify the cases involved in the insertion.
2. For the final red-black tree, draw an equivalent (2, 4) tree.
3. Remove the following keys from the red-black tree: m, u, t, f. Draw the tree after each removal. Identify the cases involved in the removal.

Copyright © 2020 Mark Maloof. All Rights Reserved. This material may not be published, broadcast, rewritten, or redistributed.