B树的C语言实现
B树是2-3-4树的延伸，或者说2-3-4树是B树的一种情况。
所以B树的基本操作与2-3-4树相同。2-3-4树其实还是挺重要的一种数据结构，理解2-3-4树更理解了B树和红黑树。前两篇文章作2-3-4树分析时画过图，B树便不再画了，画图其实挺累的。
B树的查询，插入，删除的时间复杂度都是O(lgn)
B树的定义：
- 每个节点最多有m个元素(m + 1个孩子)
- 每个非叶节点(除根节点)有最少m/2个元素(m/2 + 1个孩子)
- 如果根不时叶节点，则根至少有1个元素(2个孩子)
- 有k个元素的非叶节点包含k+1个孩子节点
- 所有叶子节点在同一层
B树的插入操作
B树的插入也有两种方法，一种是从上到下分裂，即遍历过程中，每次遇到等于m的节点时都分裂节点，这样保证插入后不再需要分裂节点。 另一种是从下到上分裂，查找到节点后插入元素，然后再向上循环分裂保证B树的性质。算法导论采用的是第一种方法，从上到下分裂。
我这里采用的是第二种方法，从下到上分裂
插入步骤：
- 查找到需要插入的节点，这个节点必然是在叶节点
- 插入元素到节点
- 检查节点，如果节点不满，插入完成
- 如果节点已满，分裂节点
- 以m/2处的元素为分割点，分成两个节点
- 把分割点元素插入父节点，可能造成父节点再次分裂
- 如果父节点是根节点，创建新的父节点
- 重新从步骤3开始循环直到完成
以下为实现代码
static int
_b_tree_insert(b_tree_pt tree, b_node_pt node, Item element)
{
Item temp;
b_node_pt parent, node2;
int i, mid;
/* 插入叶子节点 */
for (i=node->keynum; i>0 && item_cmp(node->data[i-1].key, element.key) > 0; i--) {
node->data[i] = node->data[i - 1];
}
node->data[i] = element;
node->keynum++;
while (node->keynum > tree->max) {
/* 分裂节点 */
if (node->child == NULL) {
/* 叶子节点分裂 */
node2 = b_node_new_leaf(tree->max);
}
else {
/* 内部节点分裂 */
node2 = b_node_new_internal(tree->max);
}
if (node2 == NULL) {
return 0;
}
/* 拷贝数据 */
mid = node->keynum/2;
temp = node->data[mid];
node2->keynum = node->keynum - mid - 1;
memcpy(node2->data, node->data + mid + 1, sizeof(Item)*(node2->keynum));
if (node->child != NULL) {
memcpy(node2->child, node->child + mid + 1, sizeof(b_node_pt)*(node->keynum - mid));
/* 重设父指针 */
for (i=0; i<=node2->keynum; i++) {
node2->child[i]->parent = node2;
}
}
node->keynum = mid;
/* 插入父节点 */
parent = node->parent;
if (parent == NULL) {
/* 生成新的树根节点 */
parent = b_node_new_internal(tree->max);
if (parent == NULL) {
return 0;
}
parent->child[0] = node;
node->parent = parent;
tree->root = parent;
}
/* 增加数据和右子树 */
for (i=parent->keynum; i>0 && item_cmp(parent->data[i-1].key, temp.key) > 0; i--) {
parent->data[i] = parent->data[i - 1];
parent->child[i + 1] = parent->child[i];
}
parent->data[i] = temp;
parent->child[i + 1] = node2;
parent->keynum++;
node2->parent = parent;
node = parent;
}
return 1;
}
int
b_tree_insert(b_tree_pt tree, Item element)
{
b_node_pt node;
int ret, index;
if (tree->root == NULL) {
node = b_node_new_leaf(tree->max);
if (node == NULL) {
return 0;
}
tree->root = node;
}
node = tree->root;
/* 查找到叶节点 */
while (node->child != NULL) {
ret = binary_search(node->data, element.key, 0, node->keynum - 1, &index);
/*
* 如果不允许插入相同
* 检查ret == 1
*/
node = node->child[index];
}
ret = binary_search(node->data, element.key, 0, node->keynum - 1, &index);
/*
* 如果不允许插入相同
* 检查ret == 1
*/
_b_tree_insert(tree, node, element);
return 1;
}
B树的删除操作
B树的删除也同样有两种方法，一种是从上到下合并，即遍历过程中，每次遇到小于等于m/2的节点时都从兄弟拆借元素或合并节点，这样保证删除后不再需要合并节点。 另一种是从下到上合并，查找到节点后删除元素，然后再向上循环拆借元素或合并保证B树的性质。算法导论采用的是第一种方法，从上到下合并。
我这里采用的还是是第二种方法，从下到上合并
- 查找到删除元素所在的节点
- 如果是内部节点，则与其右子树的最左元素进行交换，交换后删除元素在叶子节点
- 检查节点，如果节点大于等于m/2，删除完成
- 如果节点小于m/2，查看其兄弟节点的大小
- 如果兄弟节点大于m/2，从兄弟节点借一个元素过来，跟二叉树的旋转类似
- 如果兄弟节点也小于等于m/2，则当前节点与兄弟节点及对应的父节点中的元素合并
- 以父节点为当前节点，从步骤3开始检查循环直到完成
以下为实现代码
static void
_b_tree_delete(b_tree_pt tree, b_node_pt node, int index)
{
b_node_pt parent, sibling;
int ret, i;
/* 删除叶节点指定值 */
for (i=index; i<node->keynum - 1; i++) {
node->data[i] = node->data[i + 1];
}
node->keynum--;
parent = node->parent;
while (node->keynum < tree->min && parent != NULL) {
/* 寻找当前节点在父节点的位置 */
for (index=0; index<=parent->keynum && parent->child[index] != node; index++);
if (index > parent->keynum) {
printf("Didn't find node in parent's children array!\n");
return;
}
if (index == 0) {
/*
* 节点是父第0个子节点，兄弟是第1个子节点
* 中间的分隔元素是父中的第0个元素
*
*/
sibling = parent->child[1];
if (sibling->keynum > tree->min) {
/* 从兄弟迁移数据 */
_b_node_left_rotate(parent, 0);
}
else {
/* 合并兄弟 */
_b_node_merge(parent, 0);
}
}
else {
/*
* 节点是父中第index个子节点，兄弟是第index - 1个子节点
* 中间的分隔元素是父中的第index - 1个元素
*
*/
sibling = parent->child[index - 1];
if (sibling->keynum > tree->min) {
/* 从兄弟迁移数据 */
_b_node_right_rotate(parent, index - 1);
}
else {
/* 合并兄弟 */
_b_node_merge(parent, index - 1);
}
}
node = parent;
parent = node->parent;
}
if (tree->root->keynum == 0 && tree->root->child != NULL) {
node = tree->root;
tree->root = node->child[0];
free(node->data);
free(node->child);
free(node);
}
}
void
b_tree_delete(b_tree_pt tree, KEY key)
{
b_node_pt node = tree->root, node2;
int ret = 0, index;
if (node == NULL) {
return;
}
/* 查找到删除数据的节点 */
ret = binary_search(node->data, key, 0, node->keynum - 1, &index);
while (ret == 0 && node->child != NULL) {
node = node->child[index];
ret = binary_search(node->data, key, 0, node->keynum - 1, &index);
}
if (ret == 0) {
return;
}
/* 在内部节点 */
if (node->child != NULL) {
node2 = node->child[index + 1];
while (node2->child != NULL) {
node2 = node2->child[0];
}
node->data[index] = node2->data[0];
node = node2;
index = 0;
}
_b_tree_delete(tree, node, index);
return;
}
完整源码
/* b_tree.h */
#ifndef B_TREE_H
#define B_TREE_H
typedef int KEY;
typedef int VALUE;
typedef struct {
KEY key;
VALUE data;
} Item;
typedef struct b_node_s* b_node_pt;
typedef struct b_node_s {
int keynum;
Item *data; /* 数据，最大max+1个,最小min个 */
b_node_pt *child; /* 子节点，最大max+2个，最小min+1个 */
b_node_pt parent;
} b_node_t;
typedef struct b_tree_s* b_tree_pt;
typedef struct b_tree_s {
b_node_pt root;
int max;
int min;
} b_tree_t;
int b_tree_create(b_tree_pt *_tree, int m);
int b_tree_insert(b_tree_pt tree, Item element);
Item *b_tree_search(b_tree_pt tree, KEY key);
void b_tree_delete(b_tree_pt tree, KEY key);
void b_tree_destroy(b_tree_pt tree);
void b_tree_print(b_tree_pt tree);
void b_tree_export_dot(b_tree_pt tree, char *filename, char *label);
#endif
b_tree.h
/* b_tree.c */
/*
* =====================================================================================
*
* Filename: b_tree.c
*
* Description: B树实现
*
* Version: 1.0
* Created: 2016-12-05 21:43
* Revision: none
* Compiler: gcc
*
* Author: simon
*
* =====================================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "b_tree.h"
/*
* a==b，返回0, a>b，返回正数，a<b 返回负数
*
*/
#define item_cmp(a, b) ((a) - (b))
static b_node_pt b_node_new_leaf(int m);
static b_node_pt b_node_new_internal(int m);
static int binary_search(Item *data, KEY key, int left, int right, int *index);
static int _b_tree_insert(b_tree_pt tree, b_node_pt node, Item element);
static void _b_node_left_rotate(b_node_pt node, int index);
static void _b_node_right_rotate(b_node_pt node, int index);
static void _b_node_merge(b_node_pt node, int index);
static void _b_tree_delete(b_tree_pt tree, b_node_pt node, int index);
static void _b_node_destory(b_node_pt node);
int
b_tree_create(b_tree_pt *_tree, int m)
{
b_tree_pt tree = (b_tree_pt)malloc(sizeof(b_tree_t));
if (tree == NULL) {
return 0;
}
tree->root = NULL;
tree->max = m;
tree->min = m/2;
*_tree = tree;
return 1;
}
/*
* Name: b_node_new_leaf
* Description: 创建新的叶子节点
*
*/
static b_node_pt
b_node_new_leaf(int m)
{
b_node_pt node = (b_node_pt)malloc(sizeof(b_node_t));
if (node == NULL) {
return NULL;
}
node->parent = NULL;
node->keynum = 0;
node->data = (Item *)malloc(sizeof(Item)*(m + 1));
if (node->data == NULL) {
free(node);
return NULL;
}
node->child = NULL;
return node;
}
/*
* Name: b_node_new_internal
* Description: 创建新的内部节点
*
*/
static b_node_pt
b_node_new_internal(int m)
{
b_node_pt node = (b_node_pt)malloc(sizeof(b_node_t));
if (node == NULL) {
return NULL;
}
node->parent = NULL;
node->keynum = 0;
node->data = (Item *)malloc(sizeof(Item)*(m + 1));
if (node->data == NULL) {
free(node);
return NULL;
}
node->child = (b_node_pt *)malloc(sizeof(b_node_pt)*(m + 2));
if (node->child == NULL) {
free(node);
free(node->data);
return NULL;
}
return node;
}
/*
* Name: binary_search
* Description: 二分查找，找到数组中指定key的位置，如果存在，返回1, 否则返回0
* 如果找到索引为该值位置，否则返回右邻值位置(child的位置)
*
*/
static int
binary_search(Item *data, KEY key, int left, int right, int *index)
{
int mid;
while (left <= right) {
mid = (left + right)/2;
if (item_cmp(data[mid].key, key) > 0) {
right = mid - 1;
}
else if (item_cmp(data[mid].key, key) < 0) {
left = mid + 1;
}
else {
*index = mid;
return 1;
}
}
*index = left;
return 0;
}
/*
* Name: _b_tree_insert
* Description: 元素插入及分裂操作
*
*/
static int
_b_tree_insert(b_tree_pt tree, b_node_pt node, Item element)
{
Item temp;
b_node_pt parent, node2;
int i, mid;
/* 插入叶子节点 */
for (i=node->keynum; i>0 && item_cmp(node->data[i-1].key, element.key) > 0; i--) {
node->data[i] = node->data[i - 1];
}
node->data[i] = element;
node->keynum++;
while (node->keynum > tree->max) {
/* 分裂节点 */
if (node->child == NULL) {
/* 叶子节点分裂 */
node2 = b_node_new_leaf(tree->max);
}
else {
/* 内部节点分裂 */
node2 = b_node_new_internal(tree->max);
}
if (node2 == NULL) {
return 0;
}
/* 拷贝数据 */
mid = node->keynum/2;
temp = node->data[mid];
node2->keynum = node->keynum - mid - 1;
memcpy(node2->data, node->data + mid + 1, sizeof(Item)*(node2->keynum));
if (node->child != NULL) {
memcpy(node2->child, node->child + mid + 1, sizeof(b_node_pt)*(node->keynum - mid));
/* 重设父指针 */
for (i=0; i<=node2->keynum; i++) {
node2->child[i]->parent = node2;
}
}
node->keynum = mid;
/* 插入父节点 */
parent = node->parent;
if (parent == NULL) {
/* 生成新的树根节点 */
parent = b_node_new_internal(tree->max);
if (parent == NULL) {
return 0;
}
parent->child[0] = node;
node->parent = parent;
tree->root = parent;
}
/* 增加数据和右子树 */
for (i=parent->keynum; i>0 && item_cmp(parent->data[i-1].key, temp.key) > 0; i--) {
parent->data[i] = parent->data[i - 1];
parent->child[i + 1] = parent->child[i];
}
parent->data[i] = temp;
parent->child[i + 1] = node2;
parent->keynum++;
node2->parent = parent;
node = parent;
}
return 1;
}
int
b_tree_insert(b_tree_pt tree, Item element)
{
b_node_pt node;
int ret, index;
if (tree->root == NULL) {
node = b_node_new_leaf(tree->max);
if (node == NULL) {
return 0;
}
tree->root = node;
}
node = tree->root;
/* 查找到叶节点 */
while (node->child != NULL) {
ret = binary_search(node->data, element.key, 0, node->keynum - 1, &index);
/*
* 如果不允许插入相同
* 检查ret == 1
*/
node = node->child[index];
}
ret = binary_search(node->data, element.key, 0, node->keynum - 1, &index);
/*
* 如果不允许插入相同
* 检查ret == 1
*/
_b_tree_insert(tree, node, element);
return 1;
}
Item *
b_tree_search(b_tree_pt tree, KEY key)
{
b_node_pt node = tree->root;
int ret = 0, index;
if (node == NULL) {
return NULL;
}
ret = binary_search(node->data, key, 0, node->keynum - 1, &index);
while (ret == 0 && node->child != NULL) {
node = node->child[index];
ret = binary_search(node->data, key, 0, node->keynum - 1, &index);
}
if (ret == 0) {
return NULL;
}
return &node->data[index];
}
/*
* Name: _b_node_left_rotate
* Description: 节点值左旋转，把右节点的第一个值移到父节点，父节点的对应值移到左节点
*
*/
static void
_b_node_left_rotate(b_node_pt node, int index)
{
int i;
b_node_pt left, right;
left = node->child[index];
right = node->child[index + 1];
left->data[left->keynum] = node->data[index];
if (right->child != NULL) {
left->child[left->keynum + 1] = right->child[0];
}
left->keynum++;
node->data[index] = right->data[0];
for (i=0; i<right->keynum - 1; i++) {
right->data[i] = right->data[i + 1];
}
if (right->child != NULL) {
for (i=0; i<right->keynum; i++) {
right->child[i] = right->child[i + 1];
}
}
right->keynum--;
}
/*
* Name: _b_node_right_rotate
* Description: 节点值右旋转，把左节点的最后一个值移到父节点，父节点的对应值移到右节点
*
*/
static void
_b_node_right_rotate(b_node_pt node, int index)
{
int i;
b_node_pt left, right;
left = node->child[index];
right = node->child[index + 1];
for (i=right->keynum; i>0; i--) {
right->data[i] = right->data[i - 1];
}
right->data[0] = node->data[index];
if (right->child != NULL) {
for (i=right->keynum + 1; i>0; i--) {
right->child[i] = right->child[i - 1];
}
right->child[0] = left->child[left->keynum];
}
right->keynum++;
node->data[index] = left->data[left->keynum - 1];
left->keynum--;
}
/*
* Name: _b_node_merge
* Description: 合并节点元素的左右两个子节点
*
*/
static void
_b_node_merge(b_node_pt node, int index)
{
int i;
b_node_pt left, right;
left = node->child[index];
right = node->child[index + 1];
/* 修改左子节点 */
left->data[left->keynum] = node->data[index];
memcpy(left->data + left->keynum + 1, right->data, sizeof(Item)*(right->keynum));
if (left->child != NULL) {
for (i=0; i<=right->keynum; i++) {
right->child[i]->parent = left;
left->child[left->keynum + i + 1] = right->child[i];
}
}
left->keynum = left->keynum + right->keynum + 1;
/* 修改父节点 */
for (i=index; i<node->keynum - 1; i++) {
node->data[i] = node->data[i + 1];
}
for (i=index + 1; i<node->keynum; i++) {
node->child[i] = node->child[i + 1];
}
node->keynum--;
/* 释放右节点 */
free(right->data);
free(right->child);
free(right);
}
/*
* Name: _b_tree_delete
* Description: 数据删除
*
*/
static void
_b_tree_delete(b_tree_pt tree, b_node_pt node, int index)
{
b_node_pt parent, sibling;
int ret, i;
/* 删除叶节点指定值 */
for (i=index; i<node->keynum - 1; i++) {
node->data[i] = node->data[i + 1];
}
node->keynum--;
parent = node->parent;
while (node->keynum < tree->min && parent != NULL) {
/* 寻找当前节点在父节点的位置 */
for (index=0; index<=parent->keynum && parent->child[index] != node; index++);
if (index > parent->keynum) {
printf("Didn't find node in parent's children array!\n");
return;
}
if (index == 0) {
/*
* 节点是父第0个子节点，兄弟是第1个子节点
* 中间的分隔元素是父中的第0个元素
*
*/
sibling = parent->child[1];
if (sibling->keynum > tree->min) {
/* 从兄弟迁移数据 */
_b_node_left_rotate(parent, 0);
}
else {
/* 合并兄弟 */
_b_node_merge(parent, 0);
}
}
else {
/*
* 节点是父中第index个子节点，兄弟是第index - 1个子节点
* 中间的分隔元素是父中的第index - 1个元素
*
*/
sibling = parent->child[index - 1];
if (sibling->keynum > tree->min) {
/* 从兄弟迁移数据 */
_b_node_right_rotate(parent, index - 1);
}
else {
/* 合并兄弟 */
_b_node_merge(parent, index - 1);
}
}
node = parent;
parent = node->parent;
}
if (tree->root->keynum == 0 && tree->root->child != NULL) {
node = tree->root;
tree->root = node->child[0];
free(node->data);
free(node->child);
free(node);
}
}
void
b_tree_delete(b_tree_pt tree, KEY key)
{
b_node_pt node = tree->root, node2;
int ret = 0, index;
if (node == NULL) {
return;
}
/* 查找到删除数据的节点 */
ret = binary_search(node->data, key, 0, node->keynum - 1, &index);
while (ret == 0 && node->child != NULL) {
node = node->child[index];
ret = binary_search(node->data, key, 0, node->keynum - 1, &index);
}
if (ret == 0) {
return;
}
/* 在内部节点 */
if (node->child != NULL) {
node2 = node->child[index + 1];
while (node2->child != NULL) {
node2 = node2->child[0];
}
node->data[index] = node2->data[0];
node = node2;
index = 0;
}
_b_tree_delete(tree, node, index);
return;
}
/*
* Name: _b_node_destory
* Description: 节点递归删除
*
*/
static void
_b_node_destory(b_node_pt node)
{
int i;
if (node == NULL) {
return;
}
if (node->child != NULL) {
for (i=0; i<=node->keynum; i++) {
_b_node_destory(node->child[i]);
}
free(node->child);
}
free(node->data);
free(node);
}
void
b_tree_destroy(b_tree_pt tree)
{
_b_node_destory(tree->root);
free(tree);
}
static void
b_node_printnode(Item *element, int h)
{
int i;
for (i=0; i < h; i++) {
printf(" ");
}
if (element == NULL) {
printf("*\n");
}
else {
printf("{%d: %d}\n", element->key, element->data);
}
}
static void
b_node_show(b_node_pt node, int h)
{
int i;
if (node == NULL) {
return;
}
if (node->child != NULL) {
b_node_show(node->child[0], h + 1);
}
for (i=0; i<node->keynum; i++) {
b_node_printnode(&node->data[i], h);
if (node->child != NULL) {
b_node_show(node->child[i + 1], h + 1);
}
}
}
void
b_tree_print(b_tree_pt tree)
{
b_node_show(tree->root, 0);
}
/* 打印节点计数变量 */
static int node_num = 0;
static void
export_dot(FILE *fp, b_node_pt node, char *last_label, int field)
{
int i;
/* 打印节点 */
char node_name[10] = {0};
sprintf(node_name, "n%d", node_num);
fprintf(fp, "%s[label=\"", node_name);
if (node->child != NULL) {
fprintf(fp, "<f0>");
for (i=0; i<node->keynum; i++) {
fprintf(fp, " | %d", node->data[i].key);
fprintf(fp, " | <f%d>", i + 1);
}
}
else {
fprintf(fp, "%d", node->data[0].key);
for (i=1; i<node->keynum; i++) {
fprintf(fp, " | %d", node->data[i].key);
}
}
fprintf(fp, "\"];\n");
node_num++;
/* 打印边 */
if (last_label != NULL) {
fprintf(fp, "%s:f%d->%s;\n", last_label, field, node_name);
}
if (node->child == NULL) {
return;
}
/* 打印子节点 */
for (i=0; i<=node->keynum; i++) {
export_dot(fp, node->child[i], node_name, i);
}
}
void b_tree_export_dot(b_tree_pt tree, char *filename, char *label)
{
FILE *fp;
fp = fopen(filename, "w");
fprintf(fp, "digraph g{\nnode[shape=record];\nlabel=\"%s\";\nlabeljust=l;\nlabelloc=t;\nsplines=line;\n", label);
export_dot(fp, tree->root, NULL, -1);
fprintf(fp, "}\n");
fclose(fp);
}
b_tree.c
/* b_tree_test.c */
#include <stdlib.h>
#include <stdio.h>
#include "b_tree.h"
#define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) )
int
main(int argc, char *argv[])
{
int i, ret;
b_tree_pt tree;
Item temp;
ret = b_tree_create(&tree, 5);
printf("== B树中依次添加: \n");
for (i=0; i<30; i++) {
temp.key = i;
temp.data = 1;
b_tree_insert(tree, temp);
}
printf("\n");
printf("== B树生成: \n");
b_tree_print(tree);
b_tree_export_dot(tree, "btree.dot", "B树生成");
b_tree_delete(tree, 28);
b_tree_delete(tree, 26);
printf("== B树删除元素28,26后: \n");
b_tree_print(tree);
b_tree_export_dot(tree, "btree2.dot", "B树删除后");
b_tree_destroy(tree);
return 0;
}
b_tree_test.c
测试程序的运行结果
== B树中依次添加:
== B树生成:
{0: 1}
{1: 1}
{2: 1}
{3: 1}
{4: 1}
{5: 1}
{6: 1}
{7: 1}
{8: 1}
{9: 1}
{10: 1}
{11: 1}
{12: 1}
{13: 1}
{14: 1}
{15: 1}
{16: 1}
{17: 1}
{18: 1}
{19: 1}
{20: 1}
{21: 1}
{22: 1}
{23: 1}
{24: 1}
{25: 1}
{26: 1}
{27: 1}
{28: 1}
{29: 1}
== B树删除元素28,26后:
{0: 1}
{1: 1}
{2: 1}
{3: 1}
{4: 1}
{5: 1}
{6: 1}
{7: 1}
{8: 1}
{9: 1}
{10: 1}
{11: 1}
{12: 1}
{13: 1}
{14: 1}
{15: 1}
{16: 1}
{17: 1}
{18: 1}
{19: 1}
{20: 1}
{21: 1}
{22: 1}
{23: 1}
{24: 1}
{25: 1}
{27: 1}
{29: 1}
最后生成dot标记文件，然后使用工具可以生成下图
转载文章请注明出处： http://mingnote.com