B树
一、B树的定义
1、节点至少有两个孩子
2、每个非根节点至少有M/2(上取整)个孩子,并且以升序排列
3、每个非根节点至少有M/2-1(上取整)个关键字,并且以升序排列
4、key[i]和key[i+1]之间的孩子节点的值介于key[i]和key[i+1]之间
5、所有的叶子节点都在同一层
二、B树的创建过程
三、实现源码:
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include<iostream>
#include<stdio.h>
using namespace std;
template<class K,int M>
struct BTreeNode
{
typedef BTreeNode<K, M> Node;
K _keys[M]; //先多给一个位置为了先插入方便分裂
Node* _sub[M + 1];
Node* _parent;
size_t _size; // 记录关键字的个数
BTreeNode()
:_parent(NULL)
,_size(0)
{
for (size_t i = 0; i < M; ++i)
{
_keys[i] = K();
_sub[i] = 0;
}
_sub[M] = 0;
}
};
template<class K,int M>
class BTree
{
typedef BTreeNode<K, M> Node;
public:
BTree()
:_pRoot(NULL)
{}
void Inorder()
{
_inorder(_pRoot);
}
~BTree()
{
_Destroy(_pRoot);
}
bool Insert(const K& key)
{
if (NULL == _pRoot)
{
_pRoot = new Node();
_pRoot->_keys[0] = key;
_pRoot->_size++;
return true;
}
pair<Node*, size_t> temp=_Find(key);
if (temp.second != -1)
{
return false;
}
Node* pCur = temp.first;
Node* sub = NULL;
K newKey = key;
while (1)
{
_InsertKey(pCur, newKey, sub);
if (pCur->_size < M)
{
return true;
}
while (pCur->_size >= M)
{
size_t mid = pCur->_size / 2;
Node* NewNode = new Node();
for (size_t i = mid + 1; i < pCur->_size; ++i)
{
int j = 0; //新节点的下标
NewNode->_keys[j] = pCur->_keys[i];
NewNode->_size++;
pCur->_keys[i] = K(); //复制完成后对应的原位置key置为初始值
j++;
}
int j = 0;
for (size_t i = mid + 1; i < pCur->_size + 1; i++)
{
NewNode->_sub[j] = pCur->_sub[i];
if (NewNode->_sub[j])
{
NewNode->_sub[j]->_parent = NewNode;
}
j++;
pCur->_sub[i] = NULL;
}
//把最中间的提上去到父节点
if (pCur == _pRoot)
{
Node* temp = new Node();
temp->_keys[0] = pCur->_keys[mid];
pCur->_keys[mid] = K();
pCur->_size = mid;
temp->_size++;
temp->_sub[0] = pCur;
pCur->_parent = temp;
temp->_sub[1] = NewNode;
NewNode->_parent = temp;
_pRoot = temp;
return true;
}
newKey = pCur->_keys[mid];
pCur->_keys[mid] = K();
pCur->_size = mid;
sub = NewNode;
}
pCur = pCur->_parent;
}
}
protected:
pair<Node*, size_t> _Find(const K& key)
{
Node* pCur = _pRoot;
Node* parent = NULL;
while (pCur)
{
size_t i = 0;
while (i < pCur->_size)
{
if (pCur->_keys[i] < key)
i++;
else if (pCur->_keys[i] > key)
break;
else
return pair<Node*, size_t>(pCur, i);
}
parent = pCur;
pCur = pCur->_sub[i];
}
return pair<Node*, size_t>(parent, -1);
}
void _InsertKey(Node* pCur, const K& Key, Node* sub)
{
int i = pCur->_size - 1;
while (i >= 0)
{
if (pCur->_keys[i] > Key)
{
//移动关键字
pCur->_keys[i + 1] = pCur->_keys[i];
//移动子树位置
pCur->_sub[i + 2] = pCur->_sub[i + 1];
i--;
}
else
break;
}
pCur->_keys[i + 1] = Key;
pCur->_sub[i + 2] = sub;
if (sub)
sub->_parent = pCur;
pCur->_size++;
}
void _Inorder(Node* _pRoot)
{
if (NULL == _pRoot)
return;
size_t i = 0;
for (; i < _pRoot->_size; i++)
{
_Inorder(_pRoot->_sub[i]);
cout << _pRoot->_keys[i] << " ";
}
_Inorder(_pRoot->_sub[i]);
}
void _Destory(Node* _pRoot)
{
if (NULL == _pRoot)
return;
size_t i = 0;
for (; i < _pRoot->_size; ++i)
{
_Destory(_pRoot->_sub[i]);
delete _pRoot->_sub[i];
}
_Destory(_pRoot->_sub[i]);
delete _pRoot->_sub[i];
}
private:
Node* _pRoot;
};
void TestBTree()
{
BTree<int, 3> t;
t.Insert(10);
t.Insert(30);
t.Insert(20);
t.Insert(40);
t.Insert(70);
t.Insert(90);
t.Insert(60);
t.Insert(80);
}
int main()
{
TestBTree();
system("pause");
return 0;
}