C++ 数据结构 算法B+树实现

C++ 数据结构 算法B+树 实现。 实现了 B+树的初始化 插入 遍历 删除

#include “BPlusTree.h“
#include 
#include 
#include 

int  M_WAY = 3;
int  NODE_CAPACITY = M_WAY+1;

////////////////////////////////////////////////////

LeaveNode::LeaveNode（）
{
    m_next = NULL;
    m_prev = NULL;

    m_value  = new double[NODE_CAPACITY];
}
LeaveNode::~LeaveNode（）
{
}

void LeaveNode::Insert（int key double value）
{
    assert（m_currentSize < NODE_CAPACITY）;

    for （int i = 0; i < m_currentSize; ++i）
    {
        if （key <= m_key[i]） //找到插入点
        {
            //后续所有节点后移一个下标对应指针同步操作
            for （int j = m_currentSize - 1; j >= i; --j）
            {
                m_key[j + 1] = m_key[j];
                m_value[j + 1] = m_value[j];
            }

            m_key[i] = key;
            m_value[i] = value;

            m_currentSize++;

            return;
        }
    }

    m_key[m_currentSize] = key;
    m_value[m_currentSize] = value;

    m_currentSize++;
}

void LeaveNode::Split（Node* &_left Node* &_right）
{
    assert（m_currentSize == NODE_CAPACITY）;
    
    LeaveNode* pNew = new LeaveNode;

    int leftCount = （int）ceil（（M_WAY+1）/2.0）;
    int rightCount = m_currentSize - leftCount;
    
    int index = 0;
    while（index < leftCount）
    {
        pNew->Insert（m_key[index] m_value[index]）;

        index++;
    }

    //原节点剔除分裂到新节点的数据后，继续保留，充当分裂的第二节点
    while（index < m_currentSize）
    {
        m_key[index-leftCount] = m_key[index];
        m_value[index-leftCount] = m_value[index];

		++index;
    }
    //更新m_currentSize值
    m_currentSize = rightCount;

    //更新双向链表指针
	if（this->GetPrev（） != NULL）
	{
		this->GetPrev（）->SetNext（this）;
	}	

	pNew->SetPrev（this->GetPrev（））;
    pNew->SetNext（this）;

    this->SetPrev（pNew）;

    _right = this;
    _left = pNew;
}

Node* LeaveNode::GetMinLeaveNode（）
{
	return this;
}

bool LeaveNode::Search（int key double &value Node *&_valueNode）
{
    for （int i = 0; i < m_currentSize; ++i）
    {
        if （key == m_key[i]） 
        {
            value = m_value[i];
            _valueNode = this;

            return true;
        }
        else if （key < m_key[i]）
        { //进入此逻辑，说明查无此KEY
            break;
        }
    }

    return false;
}

bool LeaveNode::Search（int key1 int key2 double* result int& size）
{
    bool bFind = false;
    for （int i = 0; i < m_currentSize; ++i）
    {
        if （m_key[i] >= key1 && m_key[i] <= key2）
        {
            result[size] = m_value[i];
            size++;

            if（!bFind）
            {
                bFind  = true;
            }
        }
    }

    return bFind;
}

bool LeaveNode::Delete（int key）
{
    for （int i = 0; i < m_currentSize; ++i）
    {
        if （key == m_key[i]）//找到待删除元素
        {
            //后续所有节点前移一个下标对应指针同步操作
            for （int j = i; j            {
                m_key[j] = m_key[j+1];
                m_value[j] = m_value[j+1];
            }

            m_currentSize--;

            return true;
        }
        else if （key < m_k

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2019-04-16 16:38  B+Tree\
     目录           0  2019-04-16 16:35  B+Tree\data\
     文件         311  2019-04-16 16:35  B+Tree\data\input.txt
     文件         513  2019-04-16 16:38  B+Tree\Delete Redundant Files.bat
     目录           0  2019-04-16 16:39  B+Tree\project\
     文件        3683  2019-04-16 16:39  B+Tree\project\project_v100.vcxproj
     文件        1166  2019-04-16 16:39  B+Tree\project\project_v100.vcxproj.filters
     文件         870  2019-04-16 16:35  B+Tree\project\Solution_v100.sln
     目录           0  2019-04-16 16:38  B+Tree\src\
     文件        9430  2019-04-16 16:38  B+Tree\src\BPlusTree.cpp
     文件        3626  2019-04-16 16:38  B+Tree\src\BPlusTree.h
     文件         470  2019-04-16 16:38  B+Tree\src\input.txt
     文件         665  2019-04-16 16:38  B+Tree\src\makefile
     文件        3644  2019-04-16 16:38  B+Tree\src\Test.cpp