B树 (插入操作)

时间:2022-12-20 09:53:28

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 ORDER		4		//阶数
#define BTree_D	2		//[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;
}