COSC 2010: Data Structures

Homework 3
Fall 2023

Due: W 10/4 @ 11:59 PM
Optional

You must upload a 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. Using Cormen et al.'s algorithm, insert the following keys into a B-tree with a minimum degree of t = 2, which is a (2, 4) tree: e, h, m, p, d, f, o, s, q, r, t, u. Draw the tree after each insertion.
2. Remove the following keys from the (2, 4) tree drawn in the previous question: s, d, h, q, m, f, r. Draw the tree after each removal. Identify the cases involved in the removal.
3. Using Cormen et al.'s algorithm, insert the following keys into a B-tree of minimum degree t = 3: e, h, m, p, d, f, o, s, q, r, t, u. Draw the tree after each insertion.
4. Remove the following keys from the B-tree tree drawn in the previous question: p, h, f, d, u, e, t, r. 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.