#include
using namespace std;
template
struct BTreeNode
{
K _keys[M];
BTreeNode* _subs[M + 1];
BTreeNode* _parent;
size_t _size;
BTreeNode(const K& key)
:_parent(NULL)
, _size(0)
{
for (int i = 0; i < M; ++i)
{
_keys[i] = 0;
}
for (int i = 0; i <= M; ++i)
{
_subs[i] = NULL;
}
_keys[_size++] = key;
}
~BTreeNode(){};
};
template
class BTree
{
public:
typedef BTreeNode Node;
BTree()
:_root(NULL)
{}
pair Find(const K& key)
{
if (_root == NULL)
{
return pair(NULL, -1);
}
Node* prev = NULL;
Node* cur = _root;
while (cur)
{
int i = 0;
for (; i < (int)cur->_size; )
{
if (key>cur->_keys[i])
++i;
else if (key < cur->_keys[i]){
break;
}
else
return pair(cur, i);
}
prev = cur;
cur = cur->_subs[i];
}
return pair(prev, -1);
}
bool Insert(const K& key)
{
if (_root == NULL)
{
_root = new Node(key);
return true;
}
pair ret = Find(key);
if (ret.second != -1)
return false;
Node* cur = ret.first;
Node* prev = NULL;
int i = cur->_size;
while (i > ret.second&&key_keys[i-1])
{
cur->_keys[i ] = cur->_keys[i-1];
--i;
}
cur->_keys[i] = key;
++cur->_size;
if (cur->_size < M)
return true;
int mid = M / 2;
//K newKey = key;
while (1){
Node* newNode = NULL;
//cout << M << endl;
while (mid < M - 1)
{
if (newNode == NULL)
newNode = new Node(cur->_keys[mid + 1]);
else
newNode->_keys[newNode->_size++] = cur->_keys[mid + 1];
cur->_keys[mid + 1] = 0;
newNode->_subs[newNode->_size - 1] = cur->_subs[mid+1];
if (cur->_subs[mid+1])
(cur->_subs[mid+1])->_parent = newNode;
cur->_subs[++mid] = NULL;
newNode->_subs[newNode->_size] = cur->_subs[mid+1];;
if (cur->_subs[mid+1])
(cur->_subs[mid+1])->_parent = newNode;
cur->_subs[mid+1] = NULL;
--cur->_size;
}
//cur->_subs[M / 2 + 1] = newNode;
prev = cur->_parent;
if (prev == NULL)
{
prev = new Node(cur->_keys[M / 2]);
cur->_keys[M / 2] = 0;
prev->_subs[0] = cur;
prev->_subs[1] = newNode;
cur->_parent = prev;
newNode->_parent = prev;
--cur->_size;
_root = prev;
return true;
}
i = prev->_size - 1;
while (i >= 0 && prev->_keys[i] > cur->_keys[M / 2])
{
prev->_keys[i + 1] = prev->_keys[i];
prev->_subs[i + 2] = prev->_subs[i+1];
--i;
}
prev->_keys[i + 1] = cur->_keys[M / 2];
prev->_subs[i + 2] = newNode;
newNode->_parent = prev;
cur->_subs[M / 2 + 1] = NULL;
cur->_keys[M / 2] = 0;
++prev->_size;
--cur->_size;
cur = prev;
prev = cur->_parent;
mid = M / 2;
if (cur->_size < M)
return true;
}
return true;
}
bool Remove(const K& key)
{
if (_root == NULL)
return false;
pair ret = Find(key);
if (ret.second == -1)
return false;
Node* cur = ret.first;
Node* prev = NULL;
int index = ret.second;
int pindex = 0;
K newKey = key;
while (cur)
{
prev = cur->_parent;//获取父节点
if (cur->_subs[index] == NULL)//叶子节点
{
if (cur->_size >= M / 2){//节点key 数量 >= M/2，直接删除
for (int i = index; i < (int)cur->_size; ++i)
{
cur->_keys[i] = cur->_keys[i + 1];
}
cur->_size--;
return true;
}
if (prev == NULL)//父为空 只有一个节点
{
if (cur->_size == 1)//只有一个key 删除后 释放节点 _root制空
{
_root = NULL;
delete cur;
}
else//否则删除 key 移动其他
{
for (int i = index; i < (int)cur->_size; ++i)
{
cur->_keys[i] = cur->_keys[i + 1];
}
}
return true;
}
else//父不为空
{
int dev = 0;
for (; dev <= (int)prev->_size; ++dev)//判断删除操作的节点在父节点的关键字的位置(0--m-1)
{
if (prev->_subs[dev] == cur)
break;
}
if (dev !=0 && (int)prev->_subs[dev - 1]->_size > M / 2)//cur不为prev最左sub 找左边替代
{
Node* tmp = prev->_subs[dev - 1];
cur->_keys[index] = prev->_keys[dev - 1];
prev->_keys[dev - 1] = tmp->_keys[tmp->_size-1];
tmp->_keys[tmp->_size - 1] = 0;
tmp->_size--;
return true;
}
if (dev != (int)prev->_size && (int)(prev->_subs[dev + 1]->_size) > M / 2)//不为最右 找右替代
{
Node* tmp = prev->_subs[dev + 1];
cur->_keys[index] = prev->_keys[dev ];
prev->_keys[dev ] = tmp->_keys[0];
tmp->_keys[tmp->_size - 1] = 0;
for (int i = 0; i <(int) tmp->_size; ++i)
{
tmp->_keys[i] = tmp->_keys[i + 1];
}
tmp->_size--;
return true;
}
for (int i = index; i < (int)cur->_size; ++i)
{
cur->_keys[i] = cur->_keys[i + 1];
}
cur->_size--;
//需要合并
Node* ppNode = NULL;
while (1){
if (dev != 0)
{
ppNode = prev->_parent;
Node* sub = prev->_subs[dev - 1];
sub->_keys[sub->_size++] = prev->_keys[dev - 1];
for (int i = 0; i <(int)cur->_size;++i)
{
sub->_keys[sub->_size++] = cur->_keys[i];
}
for (int i = dev - 1; i < (int)prev->_size; ++i)
{
prev->_keys[i] = prev->_keys[i + 1];
prev->_subs[i + 1] = prev->_subs[i + 2];
}
if (sub->_subs[0] == NULL){
delete cur;
}
else
{
sub->_subs[sub->_size] = cur;
cur->_parent = sub;
}
if ((int)prev->_size-- >1)
return true;
else
{
if (ppNode==NULL)
{
_root = sub;
sub->_parent = NULL;
delete prev;
return true;
}
else
{
sub->_parent = prev->_parent;
memcpy(prev, sub, sizeof(Node));
delete sub;
cur = prev;
prev = ppNode;
for (dev=0; dev <= (int)prev->_size; ++dev)//判断删除操作的节点在父节点的关键字的位置(0--m-1)
{
if (prev->_subs[dev] == cur)
break;
}
return true;
}
}
}
else
{
ppNode = prev->_parent;
Node* sub = prev->_subs[dev +1];
cur->_keys[cur->_size++] = prev->_keys[dev];
for (int i = 0; i <(int)sub->_size;++i)
{
cur->_keys[cur->_size++] = sub->_keys[i];
}
for (int i = dev ; i < (int)prev->_size; ++i)
{
prev->_keys[i] = prev->_keys[i + 1];
prev->_subs[i + 1] = prev->_subs[i + 2];
}
if (cur->_subs[0] == NULL){
delete sub;
}
else
{
cur->_subs[cur->_size] = sub;
sub->_parent = cur;
}
if ((int)prev->_size-- >1)
return true;
else
{
if (ppNode == NULL)
{
_root = cur;
cur->_parent = NULL;
delete prev;
return true;
}
else
{
cur->_parent = prev->_parent;
memcpy(prev, cur, sizeof(Node));
delete cur;
cur = prev;
prev = ppNode;
for (dev = 0; dev <= (int)prev->_size; ++dev)//判断删除操作的节点在父节点的关键字的位置(0--m-1)
{
if (prev->_subs[dev] == cur)
break;
}
return true;
}
}
}
}
}
}
else//不为叶子
{
if (cur->_subs[index + 1]->_size >0)//找右孩子最小替代删除
{
Node* sub = cur->_subs[index + 1];
while (sub->_subs[0])
{
sub = sub->_subs[0];
}
cur->_keys[index] = sub->_keys[0];
cur = sub;
index = 0;
}
else if (cur->_subs[index]->_size >0)//找左孩子最大替代
{
Node* sub = cur->_subs[index];
int size=sub->_size;
while (sub->_subs[0]){
size = sub->_size;
sub = sub->_subs[size];
}
cur->_keys[index] = sub->_keys[size - 1];
cur = sub;
index = (int)sub->_size;
}
else
{
delete cur->_subs[index];
delete cur->_subs[index + 1];
cur->_subs[index] = NULL;
cur->_subs[index] = NULL;
}
}
}
return true;
}
void Traverse()
{
_Traverse(_root);
cout << endl;
}
private:
void _Traverse(Node* root)
{
if (root == NULL)
return;
int i = 0;
for (; i <(int) root->_size; ++i)
{
if (i == 0)
_Traverse(root->_subs[0]);
cout << root->_keys[i]<<" ";
_Traverse(root->_subs[i+1]);
}
}
Node* _root;
};
分享文章：c++B-Tree的操作
本文URL：
http://cdxtjz.cn/article/jcoghe.html
