算法导论之B树(B树)创建插入[C语言]

  In computer science, a B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of
a binary search tree in that a node can have more than two children (Comer 1979, p. 123). Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. It is commonly used in databases and filesystems.

  在计算机科学中，B树在查找、访问、插入、删除操作上时间复杂度为O（log2~n）（2为底数 n为对数），不像自平衡二叉查找树，其可以有效的优化系统对大块的数据读写的性能，其通常在数据库和文件系统中被使用。

  一棵m阶的B树，或为空树，或为满足下列特征的m叉树：

    ①、树中每个结点至多有m棵子树；

    ②、若根结点不是终端结点，则至少有2棵子树；

    ③、除根之外，所有非终端结点至少有棵子树；

    ④、所有的非终端结点中包含下列信息数据:

[n, C0, K0,
C1, K1, C2,
K2, ...., Kn-1,
Cn]

        其中：Ki[i=0,1，...，n-1]为关键字，且Kii&＃43;1[i=0,
1, ..., n-2]；Ci[i=0,1,...,n]为至上子树根结点的指针，且指针Ci所指子树中所有结点的关键字均小于Ki[i=0,1,...,n-1]，但都大于Ki-1[i=1,...,n-1]；

2.1 结构定义

  根据m阶B树的性质，B树的相关结构定义如下：

/* B树结点结构 */
typedef struct _btree_node_t
{
int num; /* 关键字个数 */
int *key; /* 关键字：所占空间为(max+1) */
struct _btree_node_t **child; /* 子结点：所占空间为（max+2） */
struct _btree_node_t *parent; /* 父结点 */
}btree_node_t;

代码1 结点结构

/* B树结构 */
typedef struct
{
int max; /* 单个结点最大关键字个数 - 也就是max阶 */
int min; /* 单个结点最小关键字个数 */
btree_node_t *root; /* B树根结点地址 */
}btree_t;

代码2 B树结构

2.2 创建B树

  此过程主要是完成btree_t中基本信息的设置，为后续处理创造条件。

/******************************************************************************
**函数名称: btree_creat
**功 能: 创建B树
**输入参数:
** _btree: B树
** max: 阶-单个结点的最大关键字个数(注：参数max的值不能小于2)
**输出参数: NONE
**返 回: 0:成功 -1:失败
**实现描述:
**注意事项:
** 注意：参数max的值不能小于2.
**作 者: # Qifeng.zou # 2014.03.12 #
******************************************************************************/
int btree_creat(btree_t **_btree, int max)
{
btree_t *btree = NULL;
if(max <2)
{
fprintf(stderr, "[%s][%d] Parameter ‘max‘ must geater than 2.\n", __FILE__, __LINE__);
return -1;
}
btree = (btree_t *)calloc(1, sizeof(btree_t));
if(NULL == btree)
{
fprintf(stderr, "[%s][%d] errmsg:[%d] %s!\n", __FILE__, __LINE__, errno, strerror(errno));
return -1;
}
btree->max= max;
btree->min = max/2;
if(0 != max%2)
{
btree->min++;
}
btree->min--;
btree->root = NULL;
*_btree = btree;
return 0;
}

2.3 插入操作

  B树是从空树起，逐个插入关键字而建立起来的，但由于B树结点中的关键字个数必须>=，因此，每次插入一个关键字不是在树中添加一个终端结点，而是首先在最底层的某个非终端结点中插入一个关键字，若该结点的关键字个数不超过m-1，则插入完成，否则要产生结点的“分裂”。假设现在需要构建一棵3阶B树，其插入操作的过程如下图所示：

  ① 插入关键字45

    刚开始为空树，因此插入成功后只有一个结点。

图1 插入结点

  ② 插入关键字24和53

    在图1的基础上，插入关键字24和53后，该结点关键字个数num仍未超过max，因此不会进行“分裂”处理。插入完成后，该结点关键字个数num=3已经达到临界&＃20540;max。

图2 插入结点

  ③ 插入关键字90

    在图2基础上，插入关键字90后，该结点关键字个数num=4超过max&＃20540;，需要进行“分裂”处理。

图3 分裂处理

    当结点关键字个数num达到max时，则需要进行“分裂”处理，分割序号为num/2。图3中的[4|
24, 45, 53, 90]的分割序号为num/2 = 4/2 = 2，序号从0开始计数，因此关键字53为分割点，分裂过程如下：

    1）以序列号idx=num/2为分割点，原结点分裂为2个结点A[2| 24, 45]和B[1| 90]；

    2）原结点无父结点，则新建一个结点P，并将关键字插入到新结点P中；

    3）将结点A和B作为结点P的子结点，并遵循B树特征④；

    4）因结点P的结点数未超过max，则分裂结束。

  ④ 插入关键字46和47

    在图3右图的基础上，插入关键字46和47后，得到图4左图，此时结点[4| 24, 45, 46, 47]已经达到分裂条件。

图4 分裂处理

    连续插入关键字46、47后，该结点[2| 24, 45]变为[4| 24, 45, 46, 47]，因此其达到了“分裂”的条件，其分裂流程如下：

    1）以序列号idx=num/2为分割点，结点[2| 24, 45, 46, 47]分裂为两个结点A[2| 24, 45]和B[1| 47]；

    2）分割点关键字46被插入到父结点P中，得到结点P[2| 46, 53]

    3）新结点B[1| 47]加入到结点P[2| 46, 53]的子结点序列中 - 遵循特征④

    4）因结点P[2| 46, 53]的关键字个数num为超过max，因为分裂结束。

  ⑤ 插入关键字15和18

    在图4右图的基础上，插入关键字15和18后，得到图5左图，此时结点[4| 15, 18, 24, 45]已经达到分裂条件。其处理过程同④，在此不再赘述。

图5 分裂处理

  ⑥、插入关键字48、49、50

    在图5右图的基础上插入48、49、50，可得到图6左图，此时结点[1| 47, 48, 49, 50]已达到分裂条件。

图6 分裂处理

    完成第一步分裂处理之后，父结点P[4| 24, 46, 49, 53]此时也达到了分裂条件。

图7 进一步分裂

  综合①~⑥的插入操作过程，因此可以实现：

/******************************************************************************
**函数名称: btree_insert
**功 能: 插入关键字（对外接口）
**输入参数:
** btree: B树
** key: 被插入的关键字
**输出参数: NONE
**返 回: 0:成功 -1:失败
**实现描述:
**注意事项:
**作 者: # Qifeng.zou # 2014.03.12 #
******************************************************************************/
int btree_insert(btree_t *btree, int key)
{
int idx = 0;
btree_node_t *node = btree->root;
/* 1. 构建第一个结点 */
if(NULL == node)
{
node = btree_creat_node(btree);
if(NULL == node)
{
fprintf(stderr, "[%s][%d] Create node failed!\n", __FILE__, __LINE__);
return -1;
}
node->num = 1;
node->key[0] = key;
node->parent = NULL;
btree->root = node;
return 0;
}
/* 2. 查找插入位置：在此当然也可以采用二分查找算法，有兴趣的可以自己去优化 */
while(NULL != node)
{
for(idx=0; idxnum; idx++)
{
if(key == node->key[idx])
{
fprintf(stderr, "[%s][%d] The node is exist!\n", __FILE__, __LINE__);
return 0;
}
else if(key key[idx])
{
break;
}
}
if(NULL != node->child[idx])
{
node = node->child[idx];
}
else
{
break;
}
}
/* 3. 执行插入操作 */
return _btree_insert(btree, node, key, idx);
}

/******************************************************************************
**函数名称: _btree_insert
**功 能: 插入关键字到指定结点
**输入参数:
** btree: B树
** node: 指定结点
** key: 被插入的关键字
** idx: 指定位置
**输出参数: NONE
**返 回: 0:成功 -1:失败
**实现描述:
**注意事项:
**作 者: # Qifeng.zou # 2014.03.12 #
******************************************************************************/
static int _btree_insert(btree_t *btree, btree_node_t *node, int key, int idx)
{
int i = 0;
/* 1. 移动关键字 */
for(i=node->num; i>idx; i--)
{
node->key[i] = node->key[i-1];
}
node->key[idx] = key; /* 插入 */
node->num++;
/* 2. 分裂处理 */
if(node->num > btree->max)
{
return btree_split(btree, node);
}
return 0;
}

/******************************************************************************
**函数名称: btree_split
**功 能: 结点分裂处理
**输入参数:
** btree: B树
** node: 需要被分裂处理的结点
**输出参数: NONE
**返 回: 0:成功 -1:失败
**实现描述:
**注意事项:
**作 者: # Qifeng.zou # 2014.03.12 #
******************************************************************************/
static int btree_split(btree_t *btree, btree_node_t *node)
{
int idx = 0, i = 0, total = 0;
btree_node_t *parent = NULL, *node2 = NULL;
while(node->num > btree->max)
{
/* 分裂指定结点node */
total = node->num;
idx = (total >> 1); /* Split index */
node2 = btree_creat_node(btree);
if(NULL == node2)
{
fprintf(stderr, "[%s][%d] Create node failed!\n", __FILE__, __LINE__);
return -1;
}
/* 数据拷贝 */
memcpy(node2->key, node->key+idx+1, (total-idx-1) * sizeof(int));
memcpy(node2->child, node->child+idx+1, (total-idx) * sizeof(btree_node_t *));
node2->num = (total - idx - 1);
node2->parent = node->parent;
node->num = idx;
/* 分割关键字插入父结点 */
parent = node->parent;
if(NULL == parent)
{
/* Split root node */
parent = btree_creat_node(btree);
if(NULL == parent)
{
fprintf(stderr, "[%s][%d] Create root failed!", __FILE__, __LINE__);
return -1;
}
btree->root = parent;
parent->child[0] = node;
node->parent = parent;
node2->parent = parent;
parent->key[0] = node->key[idx];
parent->child[1] = node2;
parent->num++;
}
else
{
/* Insert into parent node */
for(i=parent->num; i>0; i--)
{
if(node->key[idx] key[i-1])
{
parent->key[i] = parent->key[i-1];
parent->child[i+1] = parent->child[i];
}
else
{
parent->key[i] = node->key[idx];
parent->child[i+1] = node2;
node2->parent = parent;
parent->num++;
break;
}
}
if(0 == i)
{
parent->key[0] = node->key[idx];
parent->child[1] = node2;
node2->parent = parent;
parent->num++;
}
}
memset(node->key+idx, 0, (total - idx) * sizeof(int));
memset(node->child+idx+1, 0, (total - idx) * sizeof(btree_node_t *));
/* Change node2‘s child->parent */
for(idx=0; idx<=node2->num; idx++)
{
if(NULL != node2->child[idx])
{
node2->child[idx]->parent = node2;
}
}
node = parent;
}
return 0;
}

2.4 结果展示

算法导论 之 B-树(B树) - 创建 插入[C语言],布布扣,bubuko.com