COSC 160: Data Structures

Homework 4
Fall 2020

Due: F 10/9 @ 11:59 PM
2 points

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