COSC 2010: Data Structures

Homework 4
Fall 2023

Due: W 11/1 @ 11:59 PM
Optional

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 © 2023 Mark Maloof. All Rights Reserved. This material may not be published, broadcast, rewritten, or redistributed.