24小时全年无休客服
本公司旗下写手皆为公司直聘 网络写手勿扰
案例中心
CMSC 420: Coding Project
Coding Project
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CMSC 420: Coding Project 3
B-Trees
1 Due Date and Time
Due to Gradescope by Sunday 29 October at 11:59pm. You can submit as many times as you wish
before that.
2 Get Your Hands Dirty!
This document is intentionally brief and much of what is written here will be more clear once you
start looking at the provided files and submitting.
3 Assignment
We have provided the template btree.py which you will need to complete. More specifically you
will fill in the code details to manage insertion, deletion, and search for a very slight modification
of a B-tree. This modification is clarified in the Order of Operations section below.
As a slight change from the previous two projects we have implemented a Btree class as well as
a Node class. The Btree class stores only the m value as well as a pointer to the root Node. The
insert, delete, and search functions are then implemented as methods of the btree class.
As is noted in the btree.py template you are welcome to make minor augmentations to the Node
class. For example we have included a parent pointer but you can delete this if you don’t use it.
Please look at this file as soon as possible.
4 Details
The functions should do the following:
• def insert(self, key: int, value: str):
Insert the key-value pair into the tree and rebalance as per instructions below. The key is
guaranteed not to be in the tree.
• def delete(self, key: int):
Delete the key-value pair associated to the key from the tree and rebalance as per instructions
below. The key is guaranteed to be in the tree.
1
• def search(self, key: int):
Calculate the list of child indices followed on the path from the root to the node which includes
the key with the associated value appended at the end. If the key is in the root, return a list
containing just the associated value. The key is guaranteed to be in the tree.
5 Order of Operations
For insertion, follow these steps when correcting an overfull node. Note that the first two are a bit
different from a standard B-tree:
1. First see if a left sibling exists and has space. If so then let T be the total number of keys in
the overfull node plus the left sibling and left rotate until the overfull node is down to dT /2e
keys.
2. Second see if a right sibling exists and has space. If so then let T be the total number of keys
in the overfull node plus the right sibling and right rotate until the overfull node is down to
dT /2e keys.
3. Split.
For deletion, follow these steps when correcting an underfull node: Note that the first two are a bit
different from a standard B-tree:
1. First see if a left sibling exists and has space. If so then let T be the total number of keys in
the underfull node plus the left sibling and right rotate until the underfull node is up to bT /2c
keys.
2. Second see if a right sibling exists and has space. If so then let T be the total number of keys
in the underfull node plus the right sibling and left rotate until the underfull node is up to
bT /2c keys.
3. Merge with left sibling if possible.
4. Merge with right sibling if possible.
6 Additional Functions
You will probably want some helper functions as well as Btree class methods to handle the rotations,
merging, and splitting.
7 What to Submit
You should only submit your completed btree.py code to Gradescope for grading. We suggest that
you begin by uploading it as-is (it will run!), before you make any changes, just to see how the
autograder works and what the tests look like. Please submit this file as soon as possible.