B树 （插入操作）

时间：2022-01-29 13:10:01

B树

B树的特性

一颗m阶的B树满足一下特性

(一)  树中的每个结点至多有m颗子树，至少有颗子树。（除根结点和叶子结点外），其中表示m/2向上取整。（）

(二)  树中的每个结点至少有个关键字，至多m-1个关键字。

当结点的关键字个数满时，那么该结点就需要分裂，如何分裂？

假设*p结点已经有m-1个关键字，当再插入一个关键字后，其关键字个数为m，超标了！分裂开始，将*p结点分裂成两个结点，分别是*p，*。其中*p结点有个关键字，分别为，其中C表示孩子指针，K表示关键字，下表是个数。那么*结点有个关键字，分别为。关键字和指针*一起插入到*p的双亲结点中，如下图所示。

B树 （插入操作）

假设是4阶B树，*p结点已经有3个关键字，当再插入一个关键字Q时，*p结点关键字个数超标，需要分裂，分裂结果如下。

B树 （插入操作）

分析，因为是4阶B树，所以。

其中*p结点有=1个关键字，对应为结点H。

*结点有个关键字，对应N,Q。

关键字和指针*一起插入到*p的双亲结点中。

再通俗点讲就是，当在叶子结点插入一个元素时，判断叶子结点空间是否已满？

1.       当叶子结点空间未满时，只需要将叶子结点中关键字大于插入元素的位置都向后移动一位，留下的那个空位就放这个新插入的元素。

2.       当叶子结点空间已满时，就需要分裂，将该叶子结点个元素分裂到其相邻的右结点中，第个元素上跳到双亲结点中，并在适当的位置插入，当然，插入后双亲结点原先的元素及指针位置都要往后移动一位。（如果，此时双亲结点的空间也满了，那么也要做分裂操作）。

3.       如果是在根结点中插入元素，跟结点的空间满了，那么需要将第个元素上跳给新的根结点，这样树的高度就增加1。



 

// B-Tree.cpp : Defines the entry point for the console application.
/*-----CODE FOR FUN--------------- 
-------CREATED BY Dream_Whui------ 
-------2015-3-22-------------------------*/  
//B树（插入及遍历）

#include "stdafx.h"
#include <iostream>

typedef int KeyType;//定义键值类型

#define ORDER4//阶数
#define BTree_D2//[OREDR/2]向上取整

typedef struct BTNode
{
int keynum;//键的个数
KeyType key[ORDER-1];//结点关键字个数[BTree_D-1，ORDER-1]
BTNode *child[ORDER];//结点孩子数[BTree_D，ORDER]（除根节点与叶子节点）
bool isLeaf;//是否为孩子结点
}BTNode, *BTree;

void Tree_split_child(BTree &parent, int index, BTree &node);

void BTree_insert_nonfull(BTree &node, KeyType key)//在node中插入关键字key
{
int i;
if(node->isLeaf)//若是叶子结点，则直接插入
{
i = node->keynum-1;
while(i>=0 && key<node->key[i])
{
node->key[i+1] = node->key[i];
i--;
}
node->key[i+1] = key;
node->keynum++;
}
else//不是叶子结点，先找到插入的位置i
{
i = node->keynum-1;
while(i>=0 && key<node->key[i])
i--;

i++;
if(node->child[i]->keynum == (ORDER-1))//判断插入的位置i，其孩子结点的关键字个数是否已满
{
Tree_split_child(node, i, node->child[i]);//满了，则分裂
if(key > node->key[i] )//分裂完成后，重新判断key与node->key[i]的大小，决定应该插入带第i个孩子结点还是第i+1个孩子结点
i++;
}
BTree_insert_nonfull(node->child[i], key);  
}
}

void Tree_split_child(BTree &parent, int index, BTree &node)
{
BTree newNode = (BTree)malloc(sizeof(BTNode));//产生一个新结点newNode，存放node的最后ORDER-BTree_D个关键字
if(!newNode)
return;
newNode->isLeaf = node->isLeaf;//newNode与node在同一层，因此两者叶子节点属性相同
newNode->keynum = BTree_D -1;//新结点关键字个数为BTree_D -1
for(int i=0; i<ORDER; i++)//新结点的孩子初始化为空
newNode->child[i] = NULL;
int i;
for(i=0; i<newNode->keynum; i++)//赋值新结点的关键字为node最后ORDER-BTree_D个关键字
{
newNode->key[i] = node->key[BTree_D + i];
node->key[BTree_D + i] = 0;
}
if(!node->isLeaf)//如果不是叶子结点，是内部结点
{
for(i=0; i<BTree_D; i++)//
{
newNode->child[i] = node->child[BTree_D + i];
node->child[BTree_D + i] = NULL;
}
}
node->keynum = BTree_D -1;//node关键字个数为BTree_D -1
for (i = parent->keynum; i > index; --i) //因为不是在parent末尾插入关键字，因此从第i个孩子开始都网后移动一个位置
{  
        parent->child[i + 1] = parent->child[i];  
    }
parent->child[index+1] = newNode;//因为第index个孩子发生了分裂，因此第index+1个孩子指向新的结点

for (i = parent->keynum - 1; i >= index; --i) //同理，parent从第index个关键字也往后移动一个位置
{  
        parent->key[i + 1] = parent->key[i];  
    }  

parent->key[index] = node->key[BTree_D-1];//移动完后，第index个位置上的元素为node的第BTree_D-1关键字
parent->keynum++;

node->key[BTree_D-1] = 0;
}

void BTree_Insert(BTree &tree, KeyType key)//在B树中插入关键字key
{
BTree node;
BTree root = tree;
if(NULL == root)//根节点空，即第一次插入关键字
{
root = (BTree)malloc(sizeof(BTNode));
if(!root)
return;
root->keynum = 1;//键个数为1
root->isLeaf = true;//根节点又是叶子节点
root->key[0] = key;//第一个键值为key
for(int i=0; i<ORDER; i++) //它的孩子结点初始化为空
root->child[i] = NULL;
tree = root;
return;
}

if(root->keynum == (ORDER-1))//根结点的关键字个数已满，即要分裂
{
node = (BTree)malloc(sizeof(BTNode));//产生一个新结点，作为根结点
if(!node)
return;
tree = node;
node->keynum = 0;//新的根节点关键字个数初始化为0个
node->isLeaf = false;//非叶子节点
node->child[0] = root;//其左孩子是原先的根结点

Tree_split_child(node, 0, root);//分裂
BTree_insert_nonfull(node, key);
}
else//根结点的关键字个数未满
BTree_insert_nonfull(root, key);
}

void Tree_Print(BTree tree, int layer=1)//B树遍历
{
BTree node = tree;
int i;
if(node)
{
printf("第 %d 层， %d node : ", layer, node->keynum);  
for(i=0; i<node->keynum; i++)
{
printf("%d", node->key[i]);
}
printf("\n");

layer++;
for(i=0; i<=node->keynum; i++)
{
if(node->child[i])
Tree_Print(node->child[i], layer);
}
}
else
{
printf("树为空。\n");  
}
}

int _tmain(int argc, _TCHAR* argv[])
{
BTree tree = NULL;
BTree_Insert(tree,1);
BTree_Insert(tree,2);
BTree_Insert(tree,3);
BTree_Insert(tree,4);
BTree_Insert(tree,5);
BTree_Insert(tree,6);
BTree_Insert(tree,7);
BTree_Insert(tree,8);
BTree_Insert(tree,9);
BTree_Insert(tree,10);
Tree_Print(tree);
return 0;
}



标签：

相关文章