C++代写：CS204B-tree

Introduction

这次需要代写的作业是用C++实现一个 B-tree
，给了基本的框架代码，以及给定的输入和输出样式。
虽然不难写，但是这种作业稍微有一个Bug，就会导致排查相当麻烦。

Files to hand in are

BTree.cpp
InternalNode.cpp
InernalNode.h
LeafNode.cpp
LeafNode.h
authors.csv

Files

BTreeDriver.cpp
BTreeDebugDriver.cpp
BTree.cpp
BTree.h
BTreeNode.cpp
BTreeNode.h
InternalNode.cpp
InernalNode.h
LeafNode.cpp
LeafNode.h
Makefile (uses BTreeDebugDriver.cpp to produce BTree)
Makefile2 (uses BTreeDriver.cpp to produce BTree2)
QueueAr.cpp
QueueAr.h
vector.h
vector.cpp
dsexceptions.h

Description

Your program will read a file that contains a series of integers that it will
insert into a BTree, and then print to the screen a breadth first traversal of
the BTree. Your task will be to provide the implementation code for the BTree,
InternalNode, and LeafNode classes. Since the insert methods for the nodes
will be quite long, you should add new methods so that no method is more than
30 lines long. We will not grade on style, but the TAs and I will be of little
help with poor quality code. You may only alter those files that will be
handed in. The program will take three command line parameters: 1) filename;
2) M, the number of children that internal nodes have; and 3) L, the number of
integers each leaf node holds. The input file will not include more than 1000
integers. Since only integers will be stored in the BTree class, I did not
implement it as a template. When a node splits, the new node created will
always contain at least as many entries as the remaining old node, and will
contain the larger values. The output must match that shown in the sample.
There is one change in the data structure from the book’s; the internal nodes
should keep track of the minimum value for every child. You will find this
easier than not having the minimum for the first child.
How did I write this code so fast? I used procedural abstraction. I thought
about the tasks, their subtasks, and the subtasks of those subtasks. (You
should write them down.) If I could state a subtask, then I planned on writing
a separate function to do just that subtask. I found that the tasks of the
InternalNode class matched that of the LeafNode class, so I postponed as much
work on the InternalNode class as long as possible so that I could learn from
my LeafNode mistakes. I worked top down with stubs for the subtasks, and got
that iteration to compile without warnings! This avoids making the same
mistake repeatedly—the compiler is a very good teacher. When I could do even
minimal testing, I did it. What I learned from debugging kept me from
duplicating those mistakes in later code, and reminded me of issues that I had
forgot about. Sometimes when I addressed a new issue in a method I discovered
that I had to add a lot of code. If there is a whole lot of new code, the
issue deserved its own method with an appropriate name. It is a simple matter
of cutting and pasting, and keeps each method short, and understandable. By
the time I was done my LeafNode class had nine methods, and no method has more
than 30 lines. Once the LeafNode class worked perfectly, I copied the LeafNode
class methods as InternalNode class methods, and did a search and replace from
values to keys! Though there are child sibling and parent issues for the
InternalNode class, the basic LeafNode code provided a great starting point.
In the end my InernalNode class had 13 methods. In comparison to the first
time I wrote this with long insert functions a few years ago, the debugging
was much faster this time because of the small methods
Here is a good progression of parameters for testing using
BTreeDebugDriver.cpp. You should compare your output to that of

File	Description
BTree1.dat 3 3	To check if LeafNode insertion works at all!
BTree2.dat 3 3	To check if ordering LeafNode ordering works.
BTree5.dat 3 5	To check proper ordering in a single LeadNode.
BTree5.dat 3 3	To check split of LeafNode with odd leafSize, and then
check creation of Internal Node.
BTree5.dat 3 2	To check passing to left leaf sibling, ordering in
InternalNode, and Internal key maintenance.
BTree12.dat 8 2	To check passing to right leaf sibling; and correct
LeafNode leftSibling, rightSibling, and parent maintenance. Once this works,
copy the LeafNode methods to InternalNode.
BTree5.dat 2 2	To check split of InternalNode class with even
internalSize.
BTree12.dat 3 2	To check split of InternalNode class with even
internalSize.
BTree12.dat 2 2	To check passing to left internal node, and parent
maintenance during InternalNode splitting.
BTree25.dat 3 2	Final check #1. (I found a bug during this run)
BTree25.dat 4 3	Final check #2. (No bugs found yet.)