Skip to content

Instantly share code, notes, and snippets.

@viz3 viz3/btree.c
Created Aug 27, 2012

Embed
What would you like to do?
B木 B-Tree C言語によるアルゴリズム辞典 P.316
/**
* C言語によるアルゴリズム辞典
* P.316
* B木 B-Tree
*/
#include <stdio.h>
#include <stdlib.h>
/* 1ページのデータ数の上限の半分 */
#define M 2
/* 探索キーの型 */
typedef int keytype;
/* FALSE=0, TRUE=1 */
typedef enum {FALSE, TRUE} boolean;
/* ページの定義 */
typedef struct page {
/* データ数 */
int n;
/* キー */
keytype key[2 * M];
/* 他ページへのポインタ */
struct page *branch[2 * M + 1];
} *pageptr; /* pageptr はページへのポインタ型 */
/* B 木の根 */
pageptr root = NULL;
/* キー */
keytype key;
/* 論理型の変数 */
boolean done, deleted, undersize;
/* insert() の生成した新しいページ */
pageptr newp;
/* 関数の返すメッセージ */
char *message;
/* 新しいページの生成 */
pageptr newpage(void)
{
pageptr p;
if ((p = malloc(sizeof *p)) == NULL) {
printf("メモリ不足.\n");
exit(EXIT_FAILURE);
}
return p;
}
/* キー key を B 木から探す */
void search(void)
{
pageptr p;
int k;
p = root;
while (p != NULL) {
k = 0;
while (k < p->n && p->key[k] < key) k++;
if (k < p->n && p->key[k] == key) {
message = "見つかりました";
return;
}
p = p->branch[k];
}
message = "見つかりません";
}
/* key を p->key[k] に挿入する */
void insertitem(pageptr p, int k)
{
int i;
for (i = p->n; i > k; i--) {
p->key[i] = p->key[i - 1];
p->branch[i + 1] = p->branch[i];
}
p->key[k] = key;
p->branch[k + 1] = newp;
p->n++;
}
/* key を p->key[k] に挿入し、ページ p を割る */
void split(pageptr p, int k)
{
int j, m;
pageptr q;
m = (k <= M) ? M : M + 1;
q = newpage();
for (j = m + 1; j <= 2 * M; j++) {
q->key[j - m - 1] = p->key[j - 1];
q->branch[j - m] = p->branch[j];
}
q->n = 2 * M - m;
p->n = m;
if (k <= M) {
insertitem(p, k);
} else {
insertitem(q, k - m);
}
key = p->key[p->n - 1];
q->branch[0] = p->branch[p->n];
p->n--;
/* 新しいページを newp に入れて戻る */
newp = q;
}
/* ページ p から木を再帰的にたどって挿入する */
void insertsub(pageptr p)
{
int k;
if (p == NULL) {
done = FALSE;
newp = NULL;
return;
}
k = 0;
while (k < p->n && p->key[k] < key) k++;
if (k > p->n && p->key[k] == key) {
message = "もう登録されています";
done = TRUE;
return;
}
insertsub(p->branch[k]);
if (done) {
return;
}
if (p->n < 2 * M) {
/* ページが割れない場合 */
insertitem(p, k);
done = TRUE;
} else {
/* ページが割れる場合 */
split(p, k);
done = FALSE;
}
}
/* キー key を B 木に挿入する */
void insert(void)
{
pageptr p;
message = "登録しました";
insertsub(root);
if (done) {
return;
}
p = newpage();
p->n = 1;
p->key[0] = key;
p->branch[0] = root;
p->branch[1] = newp;
root = p;
}
/* p->kkey[k], p->branch[k+1] を外す。ページが小さくなりすぎたら undersize フラグを立てる。 */
void removeitem(pageptr p, int k)
{
while (++k < p->n) {
p->key[k - 1] = p->key[k];
p->branch[k] = p->branch[k + 1];
}
undersize = --(p->n) < M;
}
/* p->branch[k-1] の最右要素を p->key[k-1] 経由で p->branch[k] に動かす */
void moveright(pageptr p, int k)
{
int j;
pageptr left, right;
left = p->branch[k - 1];
right = p->branch[k];
for (j = right->n; j > 0; j--) {
right->key[j] = right->key[j - 1];
right->branch[j + 1] = right->branch[j];
}
right->branch[1] = right->branch[0];
right->n++;
right->key[0] = p->key[k - 1];
p->key[k - 1] = left->key[left->n - 1];
right->branch[0] = left->branch[left->n];
left->n--;
}
/* p->branch[k] の最左要素を p->key[k-1] 経由で p->branch[k-1] に動かす */
void moveleft(pageptr p, int k)
{
int j;
pageptr left, right;
left = p->branch[k - 1];
right = p->branch[k];
left->n++;
left->key[left->n - 1] = p->key[k - 1];
left->branch[left->n] = right->branch[0];
p->key[k - 1] = right->key[0];
right->branch[0] = right->branch[1];
right->n--;
for (j = 1; j <= right->n; j++) {
right->key[j - 1] = right->key[j];
right->branch[j] = right->branch[j + 1];
}
}
/* p->branch[k-1], p->branch[k] を統合する */
void combine(pageptr p, int k)
{
int j;
pageptr left, right;
right = p->branch[k];
left = p->branch[k-1];
left->n++;
left->key[left->n - 1] = p->key[k - 1];
left->branch[left->n] = right->branch[0];
for (j = 1; j <= right->n; j++) {
left->n++;
left->key[left->n - 1] = right->key[j - 1];
left->branch[left->n] = right->branch[j];
}
removeitem(p, k - 1);
free(right);
}
/* 小さくなりすぎたページ p->branch[k] を修復する */
void restore(pageptr p, int k)
{
undersize = FALSE;
if (k > 0) {
if (p->branch[k - 1]->n > M) {
moveright(p, k);
} else {
combine(p, k);
}
} else {
if (p->branch[1]->n > M) {
moveleft(p, 1);
} else {
combine(p, 1);
}
}
}
/* ページ p から再帰的に木をたどり削除する */
void deletesub(pageptr p)
{
int k;
pageptr q;
if (p == NULL) {
/* 見つからなかった */
return;
}
k = 0;
while (k < p->n && p->key[k] < key) k++;
if (k < p->n && p->key[k] == key) {
/* 見つかった */
deleted = TRUE;
if ((q = p->branch[k + 1]) != NULL) {
while (q->branch[0] != NULL) q = q->branch[0];
p->key[k] = key = q->key[0];
deletesub(p->branch[k + 1]);
if (undersize) {
restore(p, k + 1);
}
} else {
removeitem(p, k);
}
} else {
deletesub(p->branch[k]);
if (undersize) {
restore(p, k);
}
}
}
/* キー key を B 木から外す */
void delete(void)
{
pageptr p;
deleted = undersize = FALSE;
/* 根から再帰的に木をたどり削除する */
deletesub(root);
if (deleted) {
if (root->n == 0) {
/* 根が空になった場合 */
p = root;
root = root->branch[0];
free(p);
}
message = "削除しました";
} else {
message = "見つかりません";
}
}
/* デモ用に B 木を表示する */
void printtree(pageptr p)
{
static int depth = 0;
int k;
if (p == NULL) {
printf(".");
return;
}
printf("("); depth++;
for (k = 0; k < p->n; k++) {
printtree(p->branch[k]); /* 再帰呼び出し */
printf("%d", p->key[k]);
}
printtree(p->branch[p->n]); /* 再帰呼び出し */
printf(")"); depth--;
}
#include <ctype.h>
int main()
{
char s[2];
for (;;) {
printf("挿入 In, 検索 Sn, 削除 Dn (n:整数) ? ");
if (scanf("%1s%d", s, &key) != 2) {
break;
}
switch (s[0]) {
case 'I':
case 'i':
insert();
break;
case 'S':
case 's':
search();
break;
case 'D':
case 'd':
delete();
break;
default:
message = "???";
break;
}
printf("%s\n\n", message);
printtree(root);
printf("\n\n");
}
return EXIT_SUCCESS;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.