3
\$\begingroup\$

I made a B+Tree example for C++. I tested it a lot. I didn't get any errors or mistakes but i can't be sure it is really works (without any bug) or I don't know it is suitable for use (Memory problems, optimization etc.). I want your comments, test results and suggestions.

    /*
 * C++ Program to Implement B+ Tree
 */
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include <stdlib.h>
#include <fstream>
#include <sstream>
#include <unistd.h>
using namespace std;

struct Student{
    int number;
    int failCount;
    string name;
    string surname;
    string field;
};

struct less_than_key
{
    inline bool operator() (const Student& struct1, const Student& struct2)
    {
        return (struct1.number < struct2.number);
    }
};

const int numberofdatas = 4;
const int numberofkeys = numberofdatas+1;

struct BTreeNode
{
    BTreeNode* parent;
    vector<BTreeNode*> childLeafs;
    vector<Student> datas;
    BTreeNode(){
        parent = NULL;
    }
} * BTreeRoot = new BTreeNode;


void BTreeOpt(BTreeNode* tree){
    if(!tree->childLeafs.empty()){
        for(int i = 0; i < tree->childLeafs.size();i++){
            tree->childLeafs[i]->parent = tree;
        }
        for(int i = 0; i < tree->childLeafs.size();i++){
            BTreeOpt(tree->childLeafs[i]);
        }
    }
}

// Search in B+Tree and return last leaf
BTreeNode* BTreeSearch(BTreeNode* tree, int key){
    BTreeOpt(BTreeRoot);
    while(!tree->childLeafs.empty()){
        if(key < tree->datas[0].number){
            if(!tree->childLeafs.empty())
            tree = tree->childLeafs[0];
        }
        if(tree->datas.size() > 1)
        for(int i =0; i < tree->datas.size()-1; i++){
            if(key >= tree->datas[i].number && key < tree->datas[i+1].number){
                if(!tree->childLeafs.empty())
                tree = tree->childLeafs[i+1];
            }
        }
        if(key > tree->datas.back().number){
            if(!tree->childLeafs.empty())
            tree = tree->childLeafs[tree->datas.size()];
        }
    }
    return tree;
}

void BTreeSplitT(BTreeNode* node){
    BTreeNode * Parent, * Right = new BTreeNode, *Left = new BTreeNode;
    // Control if node has Parent
    if(node->parent != NULL){
        Parent = node->parent;
    }else{
        Parent = new BTreeNode;
    }
    int middleInt = node->datas.size()/2;
    Student middle = node->datas[middleInt];
    // Load Left Node
    for(int i=0; i< middleInt;i++){
        Left->datas.push_back(node->datas[i]);
        if(!node->childLeafs.empty()){
            Left->childLeafs.push_back(node->childLeafs[i]);
        }
    }
    // Load childLeafs
    if(!node->childLeafs.empty()){
        Left->childLeafs.push_back(node->childLeafs[middleInt]);
        middleInt++;
        Right->childLeafs.push_back(node->childLeafs[middleInt]);
    }
    // Load Right Node
    for(int i=middleInt; i< node->datas.size();i++){
        Right->datas.push_back(node->datas[i]);
        if(!node->childLeafs.empty()){
            Right->childLeafs.push_back(node->childLeafs[i+1]);
        }
    }
    if(Parent->datas.empty()){
        Parent->datas.push_back(middle);
        Parent->childLeafs.push_back(Left);
        Parent->childLeafs.push_back(Right);
        Right->parent = Left->parent = Parent;
        BTreeRoot = Parent;
    }else{
        int n = 0;
        if(middle.number < Parent->datas[0].number){
            n = 0;
        }
        for(int i =0; i < Parent->datas.size()-1; i++){
            if(middle.number >= Parent->datas[i].number && middle.number < Parent->datas[i+1].number){
                n = i+1;
            }
        }
        if(middle.number > Parent->datas.back().number){
            n = Parent->datas.size();
        }
        if(n == Parent->datas.size()){
            Parent->childLeafs.pop_back();
            Parent->datas.push_back(middle);
            Parent->childLeafs.push_back(Left);
            Parent->childLeafs.push_back(Right);
            Left->parent = Right->parent = Parent;
        }else{
            Parent->datas.insert(Parent->datas.begin()+n, middle);
            Parent->childLeafs.insert(Parent->childLeafs.begin()+n+1, Right);
            Parent->childLeafs[n] = Left;
            Left->parent = Right->parent = Parent;
        }
        if(Parent->datas.size() > numberofdatas){
            BTreeSplitT(Parent);
        }
    }
}



// Insert to BTreeRoot
void BTreeInsert(Student student){
    BTreeNode* temp = BTreeSearch(BTreeRoot, student.number);
    temp->datas.push_back(student);
    std::sort(temp->datas.begin(), temp->datas.end(), less_than_key());
    if(temp->datas.size() >= numberofkeys){
        BTreeSplitT(temp);
    }

}

// Print B+Tree datas
void BTreePrint(BTreeNode* tree){
    if(tree->childLeafs.size() != 0)
    for(int i = 0; i < tree->childLeafs.size();i++){
        BTreePrint(tree->childLeafs[i]);
    }
    if(tree->childLeafs.size() == 0)
    for(int i = 0; i < tree->datas.size();i++){
        cout << tree->datas[i].number << " -> ";
    }
}

// Print B+Tree visual
void BTreePrint2(BTreeNode* tree){
    for(int i = 0; i < tree->datas.size();i++){
        cout << tree->datas[i].number << " -> ";
    }
    cout << endl;
    if(tree->childLeafs.size() != 0)
    for(int i = 0; i < tree->childLeafs.size();i++){
        BTreePrint2(tree->childLeafs[i]);
    }
}
int main()
{
    Student ogr;
    string line;
    int no;
    ifstream menuFile ("numbers.txt");
    if (menuFile.is_open()){
        while ( getline (menuFile,line) ){
            std::istringstream os(line);
            os >> no;
            ogr.number = no;
            printf("Adding: %d\n",no);
            BTreeInsert(ogr);
            BTreePrint2(BTreeRoot);
            printf("---------------------------\n");
        }
        menuFile.close();
    }
    else cout << "Menu Dosyası Bulunamadı.";
    return 0;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Nitpicking: data is already plural (datum being singular). \$\endgroup\$ – vnp Nov 27 '18 at 1:54
2
\$\begingroup\$

Avoid using namespace std;.

You're not deleting any of the memory you allocate.

The operator() in less_than_key is defined inline, so you can omit the inline keyword.

BTreeRoot is a global variable, which should be avoided. It would be better off being declared in main (where you use it), with all the BTree functions being members of BTreeNode. If you keep it as a global variable, declare it as the type (BTreeNode BTreeRoot), rather than as a pointer that you immediately allocate.

Instead of tree->childLeafs.size() != 0, use !tree->childLeafs.empty(). Calling size on a vector may require a computation, while empty does not.

In BTreeSearch, replace tree->datas[tree->datas.size()-1] with tree->datas.back(). This can be a bad access if datas is empty. The for loop with i can start indexing at 1, with appropriate changes in the condition and body, which will simplify some of the code (by not needing to subtract 1 from the size all the time).

All #include directives should be a the top of the file, rather than having some in the middle where they are hard to find (and makes it more likely that you'll include something twice).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.