I have the assignment of BTree. I have done the most coding already. it compiles
ID: 3684670 • Letter: I
Question
I have the assignment of BTree. I have done the most coding already. it compiles but does not passes the test. If someone can take a look at it. Thanks
_____________________________btree.cpp______________________________________________
#include <string>
#include "btree.h"
// The default BTreeNode constructor
BTreeNode::BTreeNode() {
// TODO
isLeaf = false;
numKeys = NULL;
}
// The overloaded BTreeNode constructor
BTreeNode::BTreeNode(bool isLeaf, int numKeys) {
// TODO
this->isLeaf = isLeaf;
this->numKeys = numKeys;
}
/*
The BTreeNode destructor
Hint: Make sure to release any memory reserved in the heap to avoid memory leaks.
*/
BTreeNode::~BTreeNode() {
// TODO
isLeaf = NULL;
numKeys = 0;
}
/*
The BTree search function
Hint: Notice there are two return arguments, 1) returnNode, 2) returnIndex.
If the given key does not exist in the BTree, you should return the following.
returnNode = NULL
returnIndex = -1
*/
void bTreeSearch(BTreeNode *root, char key, BTreeNode *&returnNode, int &returnIndex) {
// TODO
int index = 0;
while ((index <= root->numKeys) && (key > root->keys[index]))
{
index++;
}
if ((index <= root->numKeys) && (key == root->keys[index]))
{
returnIndex = index;
returnNode = root;
return;
}
else if(root->isLeaf == true)
{
returnNode = NULL;
returnIndex = -1;
return;
}
else
{
bTreeSearch(root->children[index], key, returnNode, returnIndex);
}
}
/*
The BTree insert function
Hint: Note that root is passed-by-reference in order to accommodate the situations
in which the BTree height is increased.
*/
void bTreeInsert(BTreeNode *&root, char key) {
// TODO
if(root == NULL)
{
root = new BTreeNode(true,MINSIZE);
root->keys[0]= key;
root->numKeys = 1;
}
else if (root->numKeys == (2*T-1))
{
BTreeNode *r = new BTreeNode(false, MINSIZE);
r->children[0] = root;
bTreeSplitChild(r, 0);
int i = 0;
if(r->keys[0] < key)
{
i++;
//bTreeInsertNonfull(r->children[1], key);
}
else
{
bTreeInsertNonfull(r->children[i], key);
//bTreeInsertNonfull(r->children[0], key);
}
root = r;
}
else
{
bTreeInsertNonfull(root, key);
}
}
// The BTree insert non-full function
void bTreeInsertNonfull(BTreeNode *root, char key) {
// TODO
int index = root->numKeys;
if (root->isLeaf)
{
while((index >= 1) && (key < root->keys[index]))
{
root->keys[index+1] = root->keys[index];
index = index-1;
}
root->keys[index+1] = key;
root->numKeys = root->numKeys + 1;
}
else
{
while ((index >= 0) && (key < root->keys[index]))
{
index = index - 1;
}
//index = index - 1;
if(root->children[index]->numKeys == (2*T - 1))
{
bTreeSplitChild(root, index+1);
if (key > root->keys[index])
{
index = index + 1;
}
}
bTreeInsertNonfull(root->children[index], key);
}
}
// The BTree split child function
void bTreeSplitChild(BTreeNode *root, int index) {
// TODO
BTreeNode *z;
BTreeNode *y;
y = root->children[index];
z->isLeaf = y->isLeaf;
z->numKeys = T-1;
for (int j=0; j < (T-1) ;j++)
{
z->keys[j] = y->keys[j+T];
}
if(!y->isLeaf)
{
for(int j = 0; j < T; j++)
{
z->children[j] = y->children[j+T];
}
}
y->numKeys = T-1;
for(int j = (root->numKeys-1); j > (index); j--)
{
root->children[j+1] = root->children[j];
}
root->children[index] = z;
for (int j = root->numKeys-1; j >= index; j--)
{
root->keys[j+1] = root->keys[j];
}
root->keys[index] = y->keys[T];
root->numKeys = root->numKeys+1;
}
/*
The BTree delete function
Hints: 1) Make sure to "delete" BTreeNode objects appropriately when they
are no longer needed.
2) When you have a choice to make, ALWAYS go from left to right.
Otherwise, your function may produce a different btree than
the one constructed in the grading program.
3) Note that root is passed-by-reference in order to accommodate the
situations in which the BTree height is decreased.
4) Make sure to handle the case when the given key does not exist in BTree.
*/
void bTreeDelete(BTreeNode *&root, char key) {
// TODO
int index = 0;
//find key
while(index < root->numKeys && root->keys[index] < key)
index++;
if(index < root->numKeys && key == root->keys[index])
{
if(root->isLeaf)
{
//remove from a leaf
for(int i = index+1; i < root->numKeys; i++)
root->keys[i-1] = root->keys[i];
root->numKeys--;
return;
}
else
{
//remove from internal
}
}
else
{
if(root->isLeaf) return;
bool flag;
if(index == root->numKeys) flag = true;
else flag = false;
if(root->children[index]->numKeys < T)
{
//take care of filling it
if(index!=0 && root->children[index-1]->numKeys >= T)
{
//borrow from previous
BTreeNode *x = root->children[index];
BTreeNode *y = root->children[index-1];
for(int i = x->numKeys-1; i >=0 ; i--)
{
x->keys[i+1] = x->keys[i];
}
if(!x->isLeaf)
{
for(int i = x->isLeaf; i>=0; i--)
{
x->children[i+1] = x->children[i];
}
}
x->keys[0] = root->keys[index-1];
if(!root->isLeaf)
{
x->children[0] = y->children[y->numKeys];
}
root->keys[index-1] = y->keys[y->numKeys-1];
x->numKeys++;
y->numKeys--;
}
else if(index!=0 && root->children[index+1]->numKeys >= T)
{
//borrow from next
BTreeNode *x = root->children[index];
BTreeNode *y = root->children[index+1];
x->keys[x->numKeys] = root->keys[index];
if(!x->isLeaf)
{
x->children[x->numKeys+1] = y->children[0];
}
root->keys[index] = y->keys[0];
for(int i = 1;i< y->numKeys;i++)
{
y->keys[i-1] = y->keys[i];
}
if(!y->isLeaf)
{
for(int i =1; i<-y->numKeys; i++)
{
y->children[i-1] = y->children[i];
}
}
x->numKeys++;
y->numKeys--;
}
else
{
if(index!=root->numKeys)
{
//merge two leafs(index)
BTreeNode *x = root->children[index];
BTreeNode *y = root->children[index+1];
x->keys[T-1] = x->keys[index];
for(int i = 0; i <= y->numKeys; i++)
{
x->keys[i+T] = y->keys[i];
}
if(!x->isLeaf)
{
for(int i = 0; i<= y->numKeys ;i++)
{
x->children[i+T] = y->children[i];
}
}
for(int i = index+1; i< root->numKeys; i++)
{
root->keys[i-1] = root->keys[i];
}
for(int i = index+2; i<= root->numKeys; i++)
{
root->children[i-1] = root->children[i];
}
x->numKeys += y->numKeys+1;
root->numKeys--;
}
else
{
//merge two leafs(index-1)
BTreeNode *x = root->children[index-1];
BTreeNode *y = root->children[index];
x->keys[T-1] = x->keys[index-1];
for(int i = 0; i <= y->numKeys; i++)
{
x->keys[i+T] = y->keys[i];
}
if(!x->isLeaf)
{
for(int i = 0; i<= y->numKeys ;i++)
{
x->children[i+T] = y->children[i];
}
}
for(int i = index; i< root->numKeys; i++)
{
root->keys[i-1] = root->keys[i];
}
for(int i = index+1; i<= root->numKeys; i++)
{
root->children[i-1] = root->children[i];
}
x->numKeys += y->numKeys+1;
root->numKeys--;
}
}
}
if(flag && index > root->numKeys)
bTreeDelete(root->children[index-1], key);
else
bTreeDelete(root->children[index], key);
}
return;
}
// Converts a BTree to a human-readable string.
string bTreeToString(BTreeNode *node, string edgeString, int level) {
string output = "";
string edge = "";
for (int i = 0; i < level; i++)
edge += edgeString;
if (node->isLeaf) {
for (int i = node->numKeys - 1; i >= 0; i--) {
output += edge + node->keys[i] + " ";
}
} else {
output += bTreeToString(node->children[node->numKeys], edgeString, level + 1);
for (int i = node->numKeys - 1; i >= 0; i--) {
output += edge + node->keys[i] + " ";
output += bTreeToString(node->children[i], edgeString, level + 1);
}
}
return output;
}
______________________________________btree.h________________________________________
#ifndef BTREE_H_
#define BTREE_H_
#define T 3
#define MAXSIZE (2 * T) - 1
#define MINSIZE T - 1
using namespace std;
// The BTree node struct
struct BTreeNode {
bool isLeaf;
int numKeys;
char keys[MAXSIZE];
BTreeNode *children[MAXSIZE + 1];
BTreeNode();
BTreeNode(bool, int);
~BTreeNode();
};
// BTree functions
void bTreeSearch(BTreeNode *, char, BTreeNode *&, int &);
void bTreeInsert(BTreeNode *&, char);
void bTreeInsertNonfull(BTreeNode *, char);
void bTreeSplitChild(BTreeNode *, int);
void bTreeDelete(BTreeNode *&, char);
string bTreeToString(BTreeNode *, string, int);
#endif /* BTREE_H_ */