/************************************************
*作者：陈新
*时间：2014 6.3
*邮箱：cx2pirate@gmail.com
* **********************************************/ #ifndef _HEADER_BTREE_
#define _HEADER_BTREE_ #define N 5 //b-tree的度
#define TRUE 1
#define FALSE 0 typedef int BOOL;
typedef int Key; typedef struct btree_node{
int count;
BOOL is_leaf;
Key key[ * N - ];
struct btree_node *child[ * N];
}btree_node,*btree_node_ptr; typedef struct btree_root{
struct btree_node *node;
int height;
}btree_root,*btree_root_ptr; typedef struct btree_search_res{ //查询结果
btree_node *node;
int pos;
}btree_search_res; btree_root *btree_create();
btree_search_res btree_search(btree_node *node,Key key);
void btree_insert(btree_root *root,Key key);
void btree_delete(btree_root *root,Key key); #endif
#include "btree.h"
#include <stdio.h>
#include <stdlib.h> //分配一个btree_node节点
btree_node *btree_node_alloc()
{
btree_node *node = (btree_node *)malloc(sizeof(btree_node));
if(node == NULL){
return NULL;
}
for(int i =;i < * N - ;i++){
node ->key[i] = ;
}
for(int i = ;i < * N;i++){
node ->child[i] = NULL;
}
node ->count = ;
node ->is_leaf = true;
return node;
} void btree_node_free(btree_node *node)
{
free(node);
} btree_root *btree_create()
{
btree_root *root = (btree_root *)malloc(sizeof(btree_root));
root ->node = btree_node_alloc();
return root;
} int btree_split_child(btree_node *parent,int pos,btree_node *child)
{
btree_node *new_child = btree_node_alloc();
if(new_child == NULL){
return -;
}
new_child ->is_leaf = child ->is_leaf;
new_child ->count = N - ; for(int i = ;i < N - ;i++){
new_child ->key[i] = child ->key[i + N];
}
if(!child ->is_leaf){
for(int i = ;i < N;i++){
new_child ->child[i] = child ->child[i + N];
}
}
child ->count = N - ; for(int i = parent ->count;i > pos;i--){
parent ->child[i + ] = parent ->child[i];
}
parent ->child[pos + ] = new_child; for(int i = parent ->count - ;i >= pos;i--){
parent ->key[i + ] = parent ->key[i];
}
parent ->key[pos] = child ->key[N - ];
parent ->count++; return ;
} void btree_insert_nonfull(btree_node *node,int key)
{
if(node ->is_leaf){ //case1:插入叶子节点
int pos = node ->count;
while(pos >= && key < node ->key[pos - ]){
node ->key[pos] = node ->key[pos - ];
pos--;
}
node ->key[pos] = key;
node ->count++;
}
else{ //case2:递归插入
int pos = node ->count;
while(pos > && key < node ->key[pos - ]){
pos--;
}
if(node ->child[pos] ->count == * N - ){
btree_split_child(node,pos,node ->child[pos]);//分裂
if(key > node ->key[pos]){ //选择新节点还是还是老节点
pos++;
}
}
btree_insert_nonfull(node ->child[pos],key);
}
} void btree_insert(btree_root *root,int key)
{
if(root ->node == NULL){
return;
} if(root ->node ->count == * N - ){ //分裂根节点
btree_node *old_root = root ->node;
root ->node = btree_node_alloc();
root ->node ->is_leaf = FALSE;
root ->node ->count = ;
root ->node ->child[] = old_root;
btree_split_child(root ->node,,old_root);
}
btree_insert_nonfull(root ->node,key);
}
/***************************************************
*删除部分
*
* ************************************************/
Key btree_maximum(btree_node *node)
{
btree_node *p = node;
while(!p ->is_leaf){
p = p ->child[p ->count];
}
return p ->key[p ->count - ];
} Key btree_minimum(btree_node *node)
{
btree_node *p = node;
while(!p ->is_leaf){
p = p ->child[];
}
return p ->key[];
} /*pos左右两个孩子都只有N - 1个关键字，
*把第pos个关键字，和两个孩子合并成一个
*新的节点
*/
void btree_merge(btree_node *parent,int pos)
{
btree_node *left_child = parent ->child[pos];
btree_node *right_child = parent ->child[pos + ]; left_child ->key[N - ] = parent ->key[pos];
//for(int i = 0;i < N;i++) //bug report
for(int i = ;i < N - ;i++) //竟然溢出覆盖了 ->child[0]
{
left_child ->key[N + i] = right_child ->key[i];
}
if(!right_child ->is_leaf){
for(int i = ;i < N;i++){
//left_child ->child[i] = right_child ->child[N + i]; //bug report
left_child ->child[N + i] = right_child ->child[i];
}
}
left_child ->count = * N - ; for(int i = pos + ;i < parent ->count;i++){
parent ->key[i - ] = parent ->key[i];
parent ->child[i] = parent ->child[i + ];
}
parent ->count--; btree_node_free(right_child);
} void shift_right_to_left(btree_node *parent,int pos)
{
btree_node *child = parent ->child[pos];
btree_node *right_child = parent ->child[pos + ]; child ->key[N - ] = parent ->key[pos];
parent ->key[pos] = right_child ->key[]; for(int i = ;i < right_child ->count - ;i++){
right_child ->key[i] = right_child ->key[i + ];
} if(!right_child ->is_leaf){
child ->child[N] = right_child ->child[];
for(int i = ;i < right_child ->count;i++){
right_child ->child[i] = right_child ->child[i + ];
}
} child ->count++;
right_child ->count--;
}
//
void shift_left_to_right(btree_node *parent,int pos)
{
btree_node *child = parent ->child[pos];
btree_node *left_child = parent ->child[pos - ]; //for(int i = 1;i <= child ->count;i++){ //bug report
for(int i = child ->count;i > ;i--){
child ->key[i] = child ->key[i - ];
}
//child ->key[0] = parent ->key[pos]; //bug report
//parent ->key[pos] = left_child ->key[left_child ->count - 1];
child ->key[] = parent ->key[pos - ];
parent ->key[pos - ] = left_child ->key[left_child ->count - ]; if(!left_child ->is_leaf){
for(int i = child ->count + ;i > ;i--){
child ->child[i] = child ->child[i - ];
}
child ->child[] = left_child ->child[left_child ->count];
} child ->count++;
left_child ->count--;
} //node至少含有N个关键字的删除情况
void btree_delete_noback(btree_node *node,Key key)
{
int pos = ;
while(pos < node ->count && node ->key[pos] < key){ //todo不存在的情况
pos++;
}
if(pos < node ->count && node ->key[pos] == key){ //case1 && case2
if(node ->is_leaf){ //case1
for(int i = pos;i < node ->count - ;i++){
node ->key[i] = node ->key[i + ];
}
node ->count--;
return;
} if(node ->child[pos] ->count >= N){ //case 2a
Key pre = btree_maximum(node ->child[pos]);
node ->key[pos] = pre;
btree_delete_noback(node ->child[pos],pre);
}
else if(node ->child[pos + ] ->count >= N){ //case 2b
Key suc = btree_minimum(node ->child[pos + ]);
node ->key[pos] = suc;
btree_delete_noback(node ->child[pos + ],suc);
}
else{ //case 2c
btree_merge(node,pos);
btree_delete_noback(node ->child[pos],key);
}
}
else{
if(node ->is_leaf){ //case1 特殊情况，不存在节点
return;
}
if(node ->child[pos] ->count == N - ){
btree_node *next = node ->child[pos];
if(pos > && node ->child[pos - ] ->count >= N){ //case 3a_1
shift_left_to_right(node,pos);
}
else if(pos < node ->count && node ->child[pos + ] ->count >= N){ //case 3a_2
shift_right_to_left(node,pos);
}
else if(pos > ){
btree_merge(node,pos - );
next = node ->child[pos - ];
}
else{
btree_merge(node,pos);
}
btree_delete_noback(next,key); //next may be wrong
}
}
} //删除时需要更新root的情况，参考算法导论
//case 2c 和 case 3b
BOOL is_root_change(btree_root *root)
{
return root ->node ->count == &&
root ->node ->child[] ->count == N - &&
root ->node ->child[] ->count == N - ;
} void btree_delete(btree_root *root,Key key)
{
if(is_root_change(root)){
btree_merge(root ->node,);
btree_node *old_root = root ->node;
root ->node = root ->node ->child[];
btree_node_free(old_root);
}
btree_delete_noback(root ->node,key);
} /****************************************************
*查找部分
*
* **************************************************/
//返回值...
btree_search_res btree_search(btree_node *node,int key)
{
int pos = ;
while(pos < node ->count && key > node ->key[pos]){
pos++;
}
if(pos < node ->count && key == node ->key[pos]){
return btree_search_res{node,pos}; //return node and pos
}
if(node ->is_leaf){
return btree_search_res{NULL,-};
}
return btree_search(node ->child[pos],key);
}