Question: * Complete method insertBTree() in bTree.h * Compile and run exercise1.cpp ONLY PLACE CODE WHERE IT SAYS CODE HERE, DO NOT PLACE CODE ANYWHERE ELSE
* Complete method insertBTree() in bTree.h * Compile and run exercise1.cpp
ONLY PLACE CODE WHERE IT SAYS "CODE HERE", DO NOT PLACE CODE ANYWHERE ELSE OR CHANGE ANY OTHER CODE
Will rate generously and swiftly for correct answer.
Main:
#include
#include "bTree.h"
using namespace std;
int main(){
bTree
int list[] = {40, 30, 70, 6, 16, 82, 95, 100, 73, 54, 99, 37, 25, 62, 81, 150, 78, 202};
int length = sizeof(list) / sizeof(int);
for(int i = 0; i < length; i++){
b.insert(list[i]);
b.inOrder();
cout << " ";
}
/*
() 40 ()
() 30 () 40 ()
() 30 () 40 () 70 ()
() 6 () 30 () 40 () 70 ()
(() 6 () 16 () ) 30 (() 40 () 70 () )
(() 6 () 16 () ) 30 (() 40 () 70 () 82 () )
(() 6 () 16 () ) 30 (() 40 () 70 () 82 () 95 () )
(() 6 () 16 () ) 30 (() 40 () 70 () ) 82 (() 95 () 100 () )
(() 6 () 16 () ) 30 (() 40 () 70 () 73 () ) 82 (() 95 () 100 () )
(() 6 () 16 () ) 30 (() 40 () 54 () 70 () 73 () ) 82 (() 95 () 100 () )
(() 6 () 16 () ) 30 (() 40 () 54 () 70 () 73 () ) 82 (() 95 () 99 () 100 () )
(() 6 () 16 () ) 30 (() 37 () 40 () ) 54 (() 70 () 73 () ) 82 (() 95 () 99 () 100 () )
(() 6 () 16 () 25 () ) 30 (() 37 () 40 () ) 54 (() 70 () 73 () ) 82 (() 95 () 99 () 100 () )
(() 6 () 16 () 25 () ) 30 (() 37 () 40 () ) 54 (() 62 () 70 () 73 () ) 82 (() 95 () 99 () 100 () )
(() 6 () 16 () 25 () ) 30 (() 37 () 40 () ) 54 (() 62 () 70 () 73 () 81 () ) 82 (() 95 () 99 () 100 () )
(() 6 () 16 () 25 () ) 30 (() 37 () 40 () ) 54 (() 62 () 70 () 73 () 81 () ) 82 (() 95 () 99 () 100 () 150 () )
(() 6 () 16 () 25 () ) 30 (() 37 () 40 () ) 54 (() 62 () 70 () ) 73 (() 78 () 81 () ) 82 (() 95 () 99 () 100 () 150 () )
((() 6 () 16 () 25 () ) 30 (() 37 () 40 () ) 54 (() 62 () 70 () ) ) 73 ((() 78 () 81 () ) 82 (() 95 () 99 () ) 100 (() 150 () 202 () ) )
*/
return 0;
}
Header:
#include
using namespace std;
template
struct bTreeNode {
int recCount;
recType list[bTreeOrder - 1];
bTreeNode *children[bTreeOrder];
};
template
class bTree {
public:
bool search(const recType& searchItem);
void insert(const recType& insertItem);
void inOrder();
bTree();
~bTree();
protected:
bTreeNode
void searchNode(bTreeNode
void recInorder(bTreeNode
void splitNode(bTreeNode
void insertNode(bTreeNode
void insertBTree(bTreeNode
void recDestroy(bTreeNode
};
template
bTree
{
root = NULL;
}
template
void bTree
{
bool isTaller = false;
recType median;
bTreeNode
insertBTree(root, insertItem, median, rightChild, isTaller);
//the tree is initially empty or the root was split by the function insertBTree
if(isTaller){
bTreeNode
tempRoot = new bTreeNode
tempRoot->recCount = 1;
tempRoot->list[0] = median;
tempRoot->children[0] = root;
tempRoot->children[1] = rightChild;
root = tempRoot;
}
}
/*
The function insertBTree recursively inserts an item into a B-tree.
If a node is to be split, this function splits it, sets isTaller to true, and
sends the median key, median, and a pointer, rightChild, of the right child
of median to the caller.
current : a pointer to the B-tree in which to insert an item,
insertItem : item to be inserted in the B-tree,
median : to return the median key,
rightChild : pointer to the right child of median,
isTaller : to indicate if the height of a B-tree is to be increased.
*/
template
void bTree
if(current == NULL){
// Either the B-tree is empty or the search ends at an empty subtree.
// Set median to insertItem
// Set rightChild to NULL
// Set isTaller to true
/* CODE HERE */
}
else{
bool found = false;
int location;
// Call function searchNode to search the current node
/* CODE HERE */
if(found){
cout << "Error ";
}
else{
// call the function insertBTree with appropriate parameters
/* CODE HERE */
if(isTaller){
// if current node is not full
// insert item into current node
// else
// call the function splitNode to split the node
/* CODE HERE */
}
}
}
}
template
void bTree
{
rightNode = new bTreeNode
int mid = (bTreeOrder - 1) / 2;
if(insertPosition <= mid){
//new item goes in the first half of the node
int index = 0;
int i = mid;
while (i < bTreeOrder - 1){
rightNode->list[index] = current->list[i];
rightNode->children[index + 1] =
current->children[i + 1];
index++;
i++;
}
current->recCount = mid;
insertNode(current, insertItem, rightChild,
insertPosition);
(current->recCount)--;
median = current->list[current->recCount];
rightNode->recCount = index;
rightNode->children[0] =
current->children[current->recCount + 1];
}
else{
//new item goes in the second half of the node
int i = mid + 1;
int index = 0;
while (i < bTreeOrder - 1){
rightNode->list[index] = current->list[i];
rightNode->children[index + 1] =
current->children[i + 1];
index++;
i++;
}
current->recCount = mid;
rightNode->recCount = index;
median = current->list[mid];
insertNode(rightNode, insertItem, rightChild, insertPosition - mid - 1);
rightNode->children[0] = current->children[current->recCount + 1];
}
}
template
void bTree
{
int index;
for (index = current->recCount; index > insertPosition; index--){
current->list[index] = current->list[index - 1];
current->children[index + 1] = current->children[index];
}
current->list[index] = insertItem;
current->children[index + 1] = rightChild;
current->recCount++;
}
template
void bTree
{
location = 0;
while(location < current->recCount && item > current->list[location]){
location++;
}
if(location < current->recCount && item == current->list[location]){
found = true;
}
else{
found = false;
}
}
template
void bTree
{
recInorder(root);
}
template
void bTree
{
if(current != NULL){
cout << "(";
recInorder(current->children[0]);
cout << ") ";
for(int i = 0; i < current->recCount; i++){
cout << current->list[i] << " ";
cout << "(";
recInorder(current->children[i + 1]);
cout << ") ";
}
}
}
template
bTree
{
recDestroy(root);
}
template
void bTree
{
if(current != NULL){
for(int i = 0; i <= current->recCount; i++){
recDestroy(current->children[i]);
}
delete current;
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help